Santa's Shortest Path Problem

Question

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 code-golf, so shortest code wins!

---

I did come across some related posts:

• Travelling Salesman
• What path will santa take?

But the tasks seem to be quite different.

---

Sandbox

Answer 1

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[0])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!

Answer 2

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

Answer 3

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.

Answer 4

Vyxal, 75 79 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.

Answer 5

Haskell, 214 bytes

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]],k`elem`a#0]
g a=filter(\q->all(`elem`q)$a#1)
s a=until((([])/=).g a)((a?)=<<)[[[0,0]]]
f a=tail$reverse$head$g a$s a

Attempt This Online!

Answer 6

C++ (gcc), ^{429 390 380 373 370 358 341 331} 328 bytes

• -47 bytes thanks to c--

• -19 bytes thanks to ceilingcat

#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!