Skip to main content
Code Golf

Return to Answer

slighlty more golfed... still too long
Source Link
ABridgeTooFar
ABridgeTooFar
  • 63
  • 8

Python 3, 766766 622 bytes

def f(s,W,H):
 I,o=([Z=enumerate;I=[("L",-1),("R",1),("D",1j),("U",-1j)],"");P];o="";P,M,T=map(lambda t:{x+y*1jfor y,l in enumerateZ(s)for x,c in enumerateZ(l)if c==t},'PMT');E=D={c:{dt:0}for d in[-1]for t,c in Z(T for d in[d+1])}
 while len(E):
  E={}
  for m,N in[(c+d,D[c])for c in D:
   for _,d in I:
 if not c+d m=c+d
in M]:
   if 0<=m.real<len(s[0])real<W and 0<=m.imag<len(s)and not m in Mimag<H:
     T={t:D[c][t]+1forN[t]+1for t in D[c]ifN if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0D[m]:
    G.discard(g)
  while elseD[m][g]:
     for i,d in I:
      if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

Python 3, 766 bytes

def f(s):
 I,o=([("L",-1),("R",1),("D",1j),("U",-1j)],"");P,M,T=map(lambda t:{x+y*1jfor y,l in enumerate(s)for x,c in enumerate(l)if c==t},'PMT');E=D={c:{d:0}for d in[-1]for c in T for d in[d+1]}
 while len(E):
  E={}
  for c in D:
   for _,d in I:
    m=c+d
    if 0<=m.real<len(s[0])and 0<=m.imag<len(s)and not m in M:
     T={t:D[c][t]+1for t in D[c]if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0:
    G.discard(g)
   else:
    for i,d in I:
     if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

Python 3, 766 622 bytes

def f(s,W,H):
 Z=enumerate;I=[("L",-1),("R",1),("D",1j),("U",-1j)];o="";P,M,T=map(lambda t:{x+y*1jfor y,l in Z(s)for x,c in Z(l)if c==t},'PMT');E=D={c:{t:0}for t,c in Z(T)}
 while len(E):
  E={}
  for m,N in[(c+d,D[c])for c in D for _,d in I if not c+d in M]:
   if 0<=m.real<W and 0<=m.imag<H:
    T={t:N[t]+1for t in N if not m in D or not t in D[m]}
    if any(T)or not m in D:
     E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  if m in D:
   for g in D[m]:
    while D[m][g]:
     for i,d in I:
      if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

plural
Source Link
ABridgeTooFar
ABridgeTooFar
  • 63
  • 8

Python 3, 766 bytes

def f(s):
 I,o=([("L",-1),("R",1),("D",1j),("U",-1j)],"");P,M,T=map(lambda t:{x+y*1jfor y,l in enumerate(s)for x,c in enumerate(l)if c==t},'PMT');E=D={c:{d:0}for d in[-1]for c in T for d in[d+1]}
 while len(E):
  E={}
  for c in D:
   for _,d in I:
    m=c+d
    if 0<=m.real<len(s[0])and 0<=m.imag<len(s)and not m in M:
     T={t:D[c][t]+1for t in D[c]if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0:
    G.discard(g)
   else:
    for i,d in I:
     if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasuretreasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

Python 3, 766 bytes

def f(s):
 I,o=([("L",-1),("R",1),("D",1j),("U",-1j)],"");P,M,T=map(lambda t:{x+y*1jfor y,l in enumerate(s)for x,c in enumerate(l)if c==t},'PMT');E=D={c:{d:0}for d in[-1]for c in T for d in[d+1]}
 while len(E):
  E={}
  for c in D:
   for _,d in I:
    m=c+d
    if 0<=m.real<len(s[0])and 0<=m.imag<len(s)and not m in M:
     T={t:D[c][t]+1for t in D[c]if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0:
    G.discard(g)
   else:
    for i,d in I:
     if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasure. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

Python 3, 766 bytes

def f(s):
 I,o=([("L",-1),("R",1),("D",1j),("U",-1j)],"");P,M,T=map(lambda t:{x+y*1jfor y,l in enumerate(s)for x,c in enumerate(l)if c==t},'PMT');E=D={c:{d:0}for d in[-1]for c in T for d in[d+1]}
 while len(E):
  E={}
  for c in D:
   for _,d in I:
    m=c+d
    if 0<=m.real<len(s[0])and 0<=m.imag<len(s)and not m in M:
     T={t:D[c][t]+1for t in D[c]if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0:
    G.discard(g)
   else:
    for i,d in I:
     if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

Source Link
ABridgeTooFar
ABridgeTooFar
  • 63
  • 8

Python 3, 766 bytes

def f(s):
 I,o=([("L",-1),("R",1),("D",1j),("U",-1j)],"");P,M,T=map(lambda t:{x+y*1jfor y,l in enumerate(s)for x,c in enumerate(l)if c==t},'PMT');E=D={c:{d:0}for d in[-1]for c in T for d in[d+1]}
 while len(E):
  E={}
  for c in D:
   for _,d in I:
    m=c+d
    if 0<=m.real<len(s[0])and 0<=m.imag<len(s)and not m in M:
     T={t:D[c][t]+1for t in D[c]if not m in D or not t in D[m]}
     if any(T) or not m in D:
      E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  G=set(D[m].keys()if m in D else[])
  while G:
   p={g:D[m][g]for g in G};g=[g for g in p if p[g]==min(p.values())][0]
   if p[g]==0:
    G.discard(g)
   else:
    for i,d in I:
     if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasure. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.