# Santa's Shortest Path Problem

Trying to be as time-efficient as possible Santa needs to plan his trips carefully. Given a 5X5 grid representing a map of villages it is your task to be Santa's flight controller. Show santa the shortest and therefor fastest route to fly his sleigh and give him a list of coördinates (or directions) to follow. Be carefull though, do not let Santa crash, nor get him arrested!

1. Examples ###### A2,B2,B3,B4,C4,D4,D3,D2,D1,E1 ###### B1,B2,C3,D2,D1,E1 ###### B1,B2,C2,D2,D1,D2,E2,E3,E4,E5,D5,C5,C4,B4,A4,A5 ###### A2,A3,B3,C3,D3,C3,C2,C3,C4 ###### B1,A1,A2,A3 ###### B1,A1,A2,A3,A4,A5,B5,A5,A4,A3,B3,C3,C2,C3,C4,C3,D3,E3,E2,E1,D1,E1,E2,E3,E4,E5,D5 ###### empty

2. Rules

• In the examples '□' represents a village on the map Santa has to visit;
• In the examples '■' represents a no-fly zone or obstacle (antenna, mountain etc.) Santa can't cross;
• Input is any representation of a 'grid' with villages and obstacles;
• POI's can be any given character to help you make a distinction between villages and obstacles (1's and 0's for example);
• Santa can only fly horizontally and vertically on this grid;
• Santa has to start at A1 on the grid. His starting position is excluded from the result;
• Santa can go back the way he came, meaning: he can visit the same coördinates multiple times;
• Return Santa an array (or concatenated string) of coördinates ranging from A1-E5 which represents a route that visits all villages in the shortest manner possible;
• Coördinates ranging from A1-E5 are prefered, but smart Santa could read any list of clues that could lead him as long as it takes him step-by-step through the grid, e.g: ^˅<>;
• In case of a tie, present Santa with a single option;
• One can assume all villages are reachable;
• This is , so shortest code wins!

I did come across some related posts:

But the tasks seem to be quite different.

Sandbox

• Two suggested test cases. Dec 8, 2022 at 13:58
• I've never, ever seen coordinate spelled as coördinate before. What amazes me is that it's apparently correct. Dec 8, 2022 at 14:51
• Well, whether "the idea of a 5x5 grid is maintiained" is perhaps open to interpretation. To encode it as an adjacency matrix, the input would become a 25x25 matrix. The idea of the 5x5 grid is still "in there", and the original grid could be recovered, etc. For reference, often adjacency matrix are allowed for these kinds of challenges but not always. Dec 8, 2022 at 17:34
• @Jonah, if the idea is still intact and Santa gets coordinates based on a 5*5 grid it's allowed.
– JvdV
Dec 8, 2022 at 18:06
• @Arnauld also "naïve". Basically, whenever you have two vowels that normally work together to spell one sound being instead pronounced individually – said to be "in hiatus" – you use the diaeresis on the second vowel to make the hiatus explicit. You also sometimes see a hyphen, as in "co-ordinate". Both conventions are somewhat archaic at this point, however. Dec 11, 2022 at 21:36

# Python3, 329 bytes:

E=enumerate
def f(b):
q=[(0,0,[],{(x,y)for x,J in E(b)for y,t in E(J)if t==1}-{(0,0)},{})]
while q:
x,y,p,m,M=q.pop(0)
if not m:return p
for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
if len(b)>(J:=x+X)>=0<=(K:=y+Y)<len(b)and b[J][K]!=2and(J,K)not in(u:=M.get((x,y),[])):q+=[(J,K,p+[(J,K)],m-{(J,K)},{**M,(x,y):u+[(J,K)]})]


Try it online!

• -6 bytes by changing the first part of the if-statement to if len(b)>(J:=x+X)>=0<=(K:=y+Y)<len(b)and b[J][K]!=2and. Dec 8, 2022 at 15:17
• @KevinCruijssen Very clever, updated :) Dec 8, 2022 at 15:19
• -3 bytes by changing if t==1}-{(0,0)} to if t%2*(x+y)} (PS: you may want to mention in your answer you're using 1/2 for house/obstacle respectively. :) Dec 8, 2022 at 15:35
• for X,Y in(1,0),(-1,0),(0,-1),(0,1): for -2 Dec 8, 2022 at 18:32

# JavaScript (ES7), 158 bytes

+1 to support a village at A1
-1 thanks to @l4m2

Expects a matrix of integers: 0 = empty cell, 1 = target, 2 = blocked.

f=(m,n=0)=>(g=(X,Y=0,p=[])=>/.1/.test(m)?m.some((r,y)=>r.some((v,x)=>p[n]||v&2|(x-X)**2+(y-Y)**2-1?0:g(x,y,[...p,[x,y]],r[x]=0)||v&&r[x]++)):o=p)?o:f(m,n+1)


Try it online!

### Commented

f = (                    // f is a recursive function taking:
m,                     //   m[] = input matrix
n = 0                  //   n = maximum number of moves - 1
) => (                   //
g = (                  // g is a recursive function taking:
X, Y = 0, p = []     //   (X, Y) = current position, p[] = path
) =>                   //
/.1/.test(m) ?         // if there's a village anywhere except at A1:
m.some((r, y) =>     //   for each row r[] at index y in m[]:
r.some((v, x) =>   //     for each value v at index x in r[]:
p[n] ||          //       if the max. number of moves is reached
v & 2 |          //       or this cell is an obstacle
(x - X) ** 2 +   //       or the squared Euclidean distance
(y - Y) ** 2     //       between (X, Y) and (x, y)
- 1 ?            //       is not equal to 1:
0              //         do nothing
:                //       else:
g(             //         do a recursive call to g:
x, y,        //           pass the new position
[ ...p,      //           append the new coordinates
[x, y] ],  //           to the path
r[x] = 0     //           set this cell to 0
)              //         end of recursive call
|| v && r[x]++ //         if v = 1, set the cell back to 1
)                  //     end of inner some()
)                    //   end of outer some()
:                      // else:
o = p                //   success: save the path in o
)                      // initial call to g with X zero'ish
? o                      // if successful, return the solution
: f(m, n + 1)            // or try again with an extra move

• Results in [[1,0],[0,0]] when there is a single house at A1. In addition, it seems to time out for my other suggested test case, but I'm not sure whether it just takes long or it's stuck in an infinite loop. Could you verify this test case works given enough time locally perhaps? Dec 8, 2022 at 15:07
• @KevinCruijssen I don't think it makes much sense to put a village at A1, but I've asked the OP. And yes, it's just running out of time for your test case. Only ~19 moves can be performed on TIO. Dec 8, 2022 at 16:56
• 158
– l4m2
Dec 18, 2022 at 10:21

# Charcoal, 99 bytes

⊞υ#Ｆ⁵⊞υ⁺Ｓ#≔ΣＥυＥ⌕Ａι@⟦κλ⟧θ≔⟦⟦Ｅ²¬ι⟧⟧ηＷ⬤η⁻θκ≔ΣＥηＥΦＥ⁴Ｅ§κ⁰⁺ξ∧⁼π＆μ¹⊖＆μ²⁻#§§υ§μ⁰§μ¹⁺⟦μ⟧κη✂Ｅ⮌⊟Φη¬⁻θι⁺§α⊟ι⊟ι¹


Attempt This Online! Link is to verbose version of code. Takes input as a 5×5 character grid where villages are marked with @ and obstacles with #. (In the link I've filled in the rest of the grid with ' as it's the least worst character I could find; most symbols have some sort of ligature that messes up the display.) Explanation:

⊞υ#


Start with an obstacle. Due to Charcoal's cyclic indexing, this prevents Santa from flying off the top or bottom of the grid.

Ｆ⁵⊞υ⁺Ｓ#


Input the grid, appending an obstacle to the right side. (But cyclic indexing also prevents Santa from flying off the left side.)

≔ΣＥυＥ⌕Ａι@⟦κλ⟧θ


Find the positions of all of the villages.

≔⟦⟦Ｅ²¬ι⟧⟧η


Start a breath-first search with Santa at A1.

Ｗ⬤η⁻θκ


Repeat until a route which reaches all of the villages is found.

≔ΣＥη


For all of the routes searched so far...

ＥΦＥ⁴Ｅ§κ⁰⁺ξ∧⁼π＆μ¹⊖＆μ²


... for all four possible next steps...

⁻#§§υ§μ⁰§μ¹


... which don't run into an obstacle...

⁺⟦μ⟧κη


... generate a route with the additional step.

✂Ｅ⮌⊟Φη¬⁻θι⁺§α⊟ι⊟ι¹


Output any route which reaches all of the villages, but remove the A1 at the start.

Note: ⁻#§§υ§μ⁰§μ¹ should be ⁻#§υμ but I haven't implemented multidimensional indexing in Charcoal yet.

• Very nicely done!
– JvdV
Dec 9, 2022 at 10:13

# Vyxal, 7579 76 bytes

Þ¾0£00"n^v*¨^(n+D→ Du>A[÷?ii:u≠[¾← c¬[&+|_]]|X]⅛)¥?f1O=)<>^v₈*Þ×vṖ1Þf¤pc


Try it Online!

Times out for solutions longer than 3 moves. Takes a list of lists where 0 represents a blank space, 1 represents a village and -1 represents an obstacle. Returns a string of ><^v if it does return a solution, indicating the directions to move.

Because it's 12:57am, I'll give a quick high-level explanation. The algorithm here is to:

• Generate all possible combinations of directions of all possible lengths less than or equal to 256 (<>^v256*Þ×vṖ1Þf)
• Find the first solution (which will be the first shortest) where (...)...c):
• After a little initalisation of some variables (Þ¾0£)
• And starting at [0, 0] (00")
• Moving around the grid in the directions provided by each string (^v*¨^(n+D→ Du>A[÷?ii)
• Making sure no obstacles are hit in the path (:u≠)
• And tallying the villages that have been visited ([¾← c¬[&+|_]])
• Results in visiting a number of villages that is equal to the count of villages in the input (¥?f1O=)

So basically, get the first solution by brute force from all possible solution strings.

• Even though it times out, this won't work for the new test case I commented on the challenge, which requires 27 moves to visit all houses (and I'm not 100% sure if this is the maximum or there is another 5x5 board that might require even more moves and backtracking). Although I guess changing the 25 to 30 or possibly even or a single-byte builtin for 100 if Vyxal has that, would fix that in theory without changing the byte-count? 🤷 Dec 8, 2022 at 14:02
• @KevinCruijssen that gives me an idea on how to fix it and have a byte shave too - use a constant for 256 lol. Now it's even less likely to time out in the life of the universe :p Dec 8, 2022 at 14:04
• I gave it a try with just the first array being [0,1,0,0,0]. It returned ><. This would lead Santa back to A1 (is that your intention or am I misreading this) which is unnecessary. Would that help ease computing?
– JvdV
Dec 8, 2022 at 14:23

r=[0..4];a#v=[[i,j]|i<-r,j<-r,a!!i!!j>=v]
a?p@([x,y]:_)=[k:p|k<-[[x+1,y],[x-1,y],[x,y+1],[x,y-1]],kelema#0]
g a=filter(\q->all(elemq)$a#1) s a=until((([])/=).g a)((a?)=<<)[[[0,0]]] f a=tail$reverse$head$g a\$s a


Attempt This Online!

# C++ (gcc), 429390380373370358341331 328 bytes

#import<map>
#define q(d)5&&k(g,i+d,r,v,c),i
#define S size()
#define z&(!b.S|r.S<b.S)
using m=std::map<int,int>;m b;int i,c;int k(m g,int i,m r,m v,int c){g[i]<50&r.S<20&3>v[i]z?v[r[r.S]=i]++,g[i]&1?c--,g[i]=0:0,b=!c z?r:b,~i%q(1)%q(-1)/q(-5)<4*q(5):0;}
#define f(o,s)m g;b=g;c=0;for(i=25;i--;c+=(g[i]=s[i])&1);k(g,0,b,b,c);o=b


Try it online!

• @c-- Nice golfing!
– jdt
Dec 11, 2022 at 0:59
• @c-- I didn't know that you can have optional arguments for macros. You should consider adding it to this or this
– jdt
Dec 11, 2022 at 1:37
• It seems like a very specific use case. Interesting, but maybe not good advice for golfing in general, if you feel like it's deserving of a tip here's the docs for reference.
– c--
Dec 11, 2022 at 2:34
• you can use b=g in f(o, s) for -1 byte
– c--
Dec 11, 2022 at 18:43
• @c-- nice! Have you attempted to do this in C? I made a pretty mess of it :-)
– jdt
Dec 11, 2022 at 19:11