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

\$\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)

\$\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!

\$\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)
\$\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
\$\endgroup\$
0
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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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