18
\$\begingroup\$

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
Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ Shouldn't ## output 0? What should output for ##\n++? \$\endgroup\$
    – tsh
    Commented Oct 29, 2019 at 8:44
  • \$\begingroup\$ @tsh Assume they aren't touching \$\endgroup\$
    – rydwolf
    Commented Oct 29, 2019 at 12:33
  • \$\begingroup\$ May we use different ascii characters for start and end? \$\endgroup\$
    – Jitse
    Commented Oct 29, 2019 at 13:12
  • \$\begingroup\$ @Jitse Sure, I guess. I'll update the rules to allow that \$\endgroup\$
    – rydwolf
    Commented Oct 29, 2019 at 13:27
  • \$\begingroup\$ Can you include a test case where the end points are not on the edges? \$\endgroup\$
    – Jitse
    Commented Oct 30, 2019 at 10:36

9 Answers 9

Reset to default
7
\$\begingroup\$

Python 3, 146 bytes

def f(k,*s):w=k.find('\n')+1;*p,x=k.find('#'),*s;return len(k*(x in p or'#'>(k+w*' ')[x])or('+'<k[x])*s[1:])or min(f(k,*s,x+a)for a in(-1,1,-w,w))

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.

Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

J, 65 bytes

Takes the ASCII map with # and * for end goals.

1 i:~&,('*'i.~,){&,"2<@#@,((,-)#:i.3)&(*@]*[:>./|.!.0)3|' +# 'i.]

Try it online!

How it works

3|' +# 'i.       converts streets/goal to 1, start to 2, space to 0
((,-)#:i.3)      the 4 offsets + identity
(         |.!.0) shift the matrix in the directions,
     [:>./       join them by taking the greatest number,
 *@]*            and setting spaces back to 0
<@#@,            call the above function NxM times, 
                   building up the results
('*'i.~,){&,"2   flatten the results, taking the position of the goal
1 i:~&,          last place the goal was 1 (before being overwritten to 2)
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Java 8, 421 408 403 400 351 bytes

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

-57 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 on class-level, 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
     m[--i%l][i/l]!=65;); //  Loop as long as the current cell doesn't contain an 'A'
 return f(                //  Start the recursive method `f` 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 z(int x,int y,int r,int d){
                          // Method `z` 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          //  and that the current cell does NOT contain a space,
    &v[x][y]<1?           //  and we haven't visited this cell yet:
      f(x,y,r,d)          //   Return a call to the recursive method `f` with the same arguments
    :                     //  Else:
     r;}                  //   Return the row

int f(int x,int y,int r,int d){
                          // Create the recursive method `f`
  return M[x][y]>65?      //  If the current cell contains 'B':
     r>d?d:r              //   Return the minimum of the min-distance and amount of steps
    :                     //  Else:
     z(x,y-1,             //   Do a recursive `z`-call westward,
       z(x-1,y,           //   do a recursive `z`-call northward,
         z(x,y+1,         //   do a recursive `z`-call eastward,
           z(x+1,y,r,     //   do a recursive `z`-call southward,
             d+=v[x][y]=1),d),d),d)
                          //   after we've first marked the current cell as visited
     +(v[x][y]=0);}       //   And unmark the current cell as visited afterwards
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Python3, 268 bytes

E=enumerate
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 q=[(*i,[i])for i in d if'#'==d[i]][:1]
 for x,y,p in q:
  for X,Y in[(1,0),(-1,0),(0,-1),(0,1)]:
   if d.get(u:=(x+X,y+Y))and u not in p:
    if'#'==d[u]:return len(p)-1
    if'+'==d[u]:q+=[(*u,p+[u])]

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 31 28 27 bytes

Takes input as a list of lines. Incredibly slow.

œẹⱮ⁾+#ŒP;€¥/Œ!ạƝ§ṀƊ€ṂƊÞḢL_2

Try it online!

Comments (slightly outdated):

ạƝ§=1Ạ   -- helper function: is this a connected path?
ạƝ       -- element-wise absolute differences of adjacent coordinates
  §=1Ạ   -- do all differences sum to 1?

  Ɱ⁾+#   -- call with right arguments '+' and '#'
œẹ       --   multidimensional indices of right argument in inputs
    ¥/   -- call next two functions with '+'-indices on the left and '#'-indices on the right
ŒP       --   all subsets of the '+'-indices
  ;€     --   append '#'-indices to each subset

     ƊƇ  -- filter; keep subsets where the following three functions yield a thruthy result
Œ!       --   all permutations of the subsets
  ǀ     --   call the helper function for each subset
    Ẹ    --   is any result truthy?
Ḣ        -- take first (shortest) subset
 L_2     -- length - 2
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 102 bytes

f=A=>-/7/.test(A)||f(A.map((r,y)=>r.map((c,x)=>c|2&(+c&&r[x-1]|r[x+1]|A[y-!!y][x]|(A[y+1]||0)[x]))))+1

Try it online!

Spread 2 till cover 5

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

GNU AWK -F '', 299 294 286 285 bytes

NF>w{w=NF}{for(i=0;++i<=NF;){if(!r&&$i~/#/){$i=0;r=1}a[NR,i]=$i}h=NR}END{k=0;while(1){for(y=0;++y<=h;){for(x=0;++x<=w;){if(a[y,x]==""k){for(z=y-1;z<=y+1&&z<=h;z++){for(t=x-1;t<=x+1&&t<=w;t++){if(t>0&&z>0&&(t==x||z==y)){if(a[z,t]~/#/){print k;exit}if(a[z,t]=="+"){a[z,t]=k+1}}}}}}}k++}}

This can be run with awk -F '' -f ./route.awk ./road_map.txt.

Try it online! I wasn't able to figure out how to pass -F '' to the interpreter, so I just added BEGIN{FS=""} to the beginning.

Explanation:

NF>w{w=NF}             # Let w be the width of the largest line.
{for(i=0;++i<=NF;){    # On each line, for each field...
 if(!r && $i~/#/){     #   If we haven't already found the first #...
  $i=0;r=1}            #     Change that # to a 0 and set r ("found") to 1.
 a[NR,i]=$i}           #   In any case, load this field into an array a.
h=NR}                  # Let h be the height.
END{k=0;while(1){      # Now let's process the array using k as a counter.
 for(y=0;++y<=h;){     # For each y coordinate...
 for(x=0;++x<=w;){     # For each x coordinate...
  if(a[y,x]==""k){     #   If the cell at row y, column x is k (as a string)...
   for(z=y-1;          #   .
       z<=y+1&&z<=h;   #   .
       z++){           #   .   
   for(t=x-1;          #   .
       t<=x+1&&t<=w;   #   .
       t++){           #   .
    if(t>0&&           #   .
       z>0&&           #   .
       (t==x||         #   .
        z==y)){        #   Iterate over potential neighbors a[z,t].
      if(a[z,t]~/#/){  #     Does a[z,t] mark the end?
       print k;exit}   #       Wow, we found it!
      if(a[z,t]=="+"){ #     If not, if the neighbor is '+'...
       a[z,t]=k+1}     #       Set the neighbor to k+1.
        }}}}}}         #   Pay our debt.
    k++}}              # Go to the next iteration.
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.