| Bytes | Lang | Time | Link |
|---|---|---|---|
| 285 | GNU AWK F '' | 241112T180526Z | wobtax |
| 102 | JavaScript Node.js | 241204T005250Z | l4m2 |
| 268 | Python3 | 240808T175753Z | Ajax1234 |
| 146 | Python 3 | 191029T151352Z | Jitse |
| 027 | Jelly | 211013T114501Z | ovs |
| 351 | Java 8 | 191105T093349Z | Kevin Cr |
| 065 | J | 200619T174716Z | xash |
| 183 | Python 3 + numpy | 191029T210133Z | Uri Gran |
| 130 | JavaScript ES7 | 191030T091658Z | Arnauld |
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.
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
Spread 2 till cover 5
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])]
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))
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.
Jelly, 31 28 27 bytes
Takes input as a list of lines. Incredibly slow.
œẹⱮ⁾+#ŒP;€¥/Œ!ạƝ§ṀƊ€ṂƊÞḢL_2
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
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.
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
J, 65 bytes
Takes the ASCII map with # and * for end goals.
1 i:~&,('*'i.~,){&,"2<@#@,((,-)#:i.3)&(*@]*[:>./|.!.0)3|' +# 'i.]
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)
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)
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