Find the shortest route on an ASCII road

Question

You want to find the length shortest path between two points, on an 2d ASCII "map". The roads are made up of + characters, and the two endpoints are represented by #s (not counted in the length). This road can be arranged in any way, and any other characters can be ignored. You can assume the endpoints will always connect to each other through roads.

Examples:

Output: 1

#+#

Output: 5

   #+
+   +
++++++
   +
   #

Output: 8

++++#+++
+      +
+      +
++#+++++

Output: 4

#+++
++++
+++#

Output: 2

+++++
+   +
+#  +
+++#+
   +
 +++

Undefined output:

##

#   +++#
+    +

#+++#
    +
    +
    #

#++
  +

Rules:

• You can take input as a 2d array, matrix, string separated by newlines, etc.
• Output should be a number
• Can be a snippet, function, or full program
• You can represent one endpoint with a different character if necessary

Answer 1

Python 3, 163 bytes

def f(g,s=[]):w=len(g[0])+1;k=' '.join(g)+w*' ';*p,x=s or[k.find('#')];return' '<k[x]and{x}-{*p}and[min(f(g,s+[x+a])or len(k)for a in(-1,1,-w,w)),len(p)]['+'<k[x]]

Try it online!

Uses # for start and @ for end. Finds all paths along + and returns the shortest. Each path ends when either a space is encountered, the range is outside the box or a previous position is visited.

Answer 2

Python 3 (+ numpy), 183 bytes

Assuming the input can be passed in as a numpy character array, here is a different approach. It works by calculating a distance matrix from the start point by repeatedly 'diffusing' distances along roads. Uses '#' for start and '@' for end.

from numpy import*
def f(A):
 B=(A!=" ")-1+(A=="#")
 for _ in nditer(A):B=pad(B,1);B+=(B==0)*stack(roll(B+(B>0),n%3-1,n%2)for n in[0,2,3,5]).max(0);B=B[1:-1,1:-1]
 print(*B[A=="@"]-2)

Try it online! (11 bytes longer as the version of numpy on TIO requires an explicit mode parameter for pad, which is no longer the case)

Answer 3

JavaScript (ES7),  131  130 bytes

Takes input as a matrix of characters. Expects 1 for the starting point and 2 for the arrival.

m=>(M=g=(X,Y,n)=>m.map((r,y)=>r.map((c,x)=>(X-x)**2+(Y-y)**2^1?c^1||g(x,y,r[x]=g):1/c?c^2|M>n?0:M=n:r[g(x,y,r[x]=~-n),x]=c)))()|-M

Try it online!

Answer 4

Java 8, 421 408 403 bytes

int M[][],v[][],l,L;m->{int i=(l=m.length)*(L=m[0].length);for(M=m,v=new int[l][L];;)if(m[--i%l][i/l]==65)return f(i%l,i/l,-1>>>1,-1);};int f(int x,int y,int r,int d){if(M[x][y]>65)return r>d?d:r;d+=v[x][y]=1;r=v(x+1,y)?f(x+1,y,r,d):r;r=v(x,y+1)?f(x,y+1,r,d):r;r=v(x-1,y)?f(x-1,y,r,d):r;r=v(x,y-1)?f(x,y-1,r,d):r;v[x][y]=0;return r;}boolean v(int x,int y){return x<l&y<L&x>=0&y>=0&&M[x][y]>32&v[x][y]<1;}

-5 bytes thanks to @ceilingcat.

Input as a matrix of bytes, with A as start and B as finish.

Try it online.

Explanation:

int M[][],                // Matrix on class-level, starting uninitialized
    v[][],                // Visited matrix on class-level, starting uninitialized
    l,L;                  // x and y dimensions, starting uninitialized

m->{                      // Method with integer-matrix as input and integer as return
 int i=(l=m.length)       //  Set `l` to the amount of rows
       *(L=m[0].length);  //  Set `L` to the amount of columns
                          //  And set `i` to the product of the two
 for(M=m,                 //  Set `M` to the input-matrix
     v=new int[l][L];     //  Create the visited-matrix filled with 0s
     ;)                   //  Loop indefinitely:
   if(m[--i%l][i/l]==65)  //   If the current cell contains an 'A':
     return f(            //    Start the recursive method with:
       i%l,i/l,           //     The current cell as the starting x,y-coordinate
       -1>>>1,            //     Integer.MAX_VALUE as starting minimum-distance
       -1);}              //     And -1 as amount of steps

int f(int x,int y,int r,int d){
                          // Create the recursive method
  if(M[x][y]>65)          //  If the current cell contains 'B':
    return r>d?d:r;       //   Return the minimum of the min-distance and amount of steps
  d+=v[x][y]=1;           //  Mark the current cell as visited
  d++;                    //  And increase the amount of steps by 1 at the same time
  r=v(x+1,y)?             //  If we can travel south:
    f(x+1,y,r,d):r;       //   Set the min-distance to a recursive call southwards
  r=v(x,y+1)?             //  If we can travel east:
    f(x,y+1,r,d):r;       //   Set the min-distance to a recursive call eastwards
  r=v(x-1,y)?             //  If we can travel north:
    f(x-1,y,r,d):r;       //   Set the min-distance to a recursive call northwards
  r=v(x,y-1)?             //  If we can travel west:
    f(x,y-1,r,d):r;       //   Set the min-distance to a recursive call westwards
  v[x][y]=0;              //  Unmark the current cell as visited
  return r;}              // And return the amount of steps as result

boolean v(int x,int y){   // Method to check whether we can travel to the given cell
  return x<l&y<L&x>=0&y>=0//  If the x,y-coordinate is within the matrix boundaries
    &&M[x][y]>32          //   Check that the current cell does NOT contain a space
    &v[x][y]<1;}          //   And we haven't visited this cell yet