New answers tagged path-finding
5
JavaScript (ES6), 219 bytes
Takes input as a list of lists of characters.
a=>((g=(X,Y,D,n=o=0)=>!(a+0)[n++]|a.some((r,y)=>r.some((c,x)=>D=='975'[i='-| #+$'.indexOf(c),x-X+1]-'450'[y-Y+1]?i-3?i-2?i>3?[3,0,7,4].some(d=>D^d^4&&g(x,y,d,n)):~i&&i^D&1?0:g(x,y,D,n):0:o=-n:X+1|i<5?0:g(x,y,2))))(),~o)
Try it online!
How?
...
0
Python 3, 275 bytes
import sys
def q(g,s=[]):w=len(g[0])+1;k='@'.join(g)+w*'@';*p,x=s or[k.find('#')];return'@'>k[x]and{x}-{*p}and[p,min((q(g,s+[x+a])or k for a in(-1,1,-w,w)),key=len)]['*'>k[x]]
g=''.join(sys.stdin.read());s=q(g.split('\n'))
for i in range(len(g)):print(end=[g[i],'+'][i in s])
Try it online!
Port of my answer to Find the shortest ...
0
Python 3, 184 bytes
f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))
Try it online!
1
Python 3, 147 bytes
def f(g,s=[1]):w=len(g[0])+1;*p,x=s;return~-(x in p)*~-[j for i in g+[w*[1]]for j in[1]+i][x]and max(f(g,s+[x+a])for a in(-1,1,-w,w))or x==w*len(g)
Try it online!
Port of my answer to Find the shortest route on an ASCII road.
0
Ruby, 67 bytes
Starts from 0. I noticed GB's Ruby solution after I finished my own, but the approaches used are drastically different (recursive vs. non-recursive) so I decided to post anyways.
f=->n{r=n.digits.join.to_i;n<9?n:[f[n-1],n>r&&n%10>0?f[r]:n].min+1}
Try it online!
1
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[...
0
Ruby, 72 bytes
->i{*w=0;(0..i).find{[]==[i]-w=w.flat_map{|z|[z+1,z.digits.join.to_i]}}}
Try it online!
2
Perl 6, 26 25 bytes
{+(1,{1+$_|+.flip}...$_)}
Try it online!
Does pretty much as the question asks. Starting from 1, either increment the Junction of values or flip it, repeating this until we find the one value we're looking for. Then return the length of the sequence. This is zero-indexed (as in, 1 returns 1)
This times out for testcases with a larger ...
0
Python 3, 78 bytes
f=lambda n,s={1}:n in s or-~f(n,{int(str(i)[::-1])for i in s}|{i+1for i in s})
Try it online!
Uses 0-indexing. Note that in Python True == 1.
1
05AB1E (legacy), 15 13 bytes
1¸[ÐIå#ís>«}N
-1 byte and much faster thanks to @Jitse, which also opened an opportunity for a second -1 byte.
Try it online or verify the first 100 test cases (with added Ù -uniquify- to increase the speed).
Explanation:
1¸ # Push 1 and wrap it into a list: [1]
[ # Start an infinite loop:
Ð # ...
5
C++, 140 159 147 145 bytes
Edit: new solution without standard library, using a recursive function and pointer magic (constant 20 experimentally determined and not the same on other compilers)
Edit 2: -2 bytes thanks to ceilingcat
int*s,S,*G,x;int F(int Z,int*p=&x){int W=1,a=(*p)++,r=0;for(;r=r*10+a%10,a/=10;);G?W=r,p<=G?G=&W,S++,p=s:0:p=s=G=&...
0
Charcoal, 47 bytes
Ｎθ≔⁰ηＷ⊖θ«Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌ貫≦⮌θ≦⊕η»≦⊖θ≦⊕η»Ｉη
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input the target.
≔⁰η
Set the number of steps to zero.
Ｗ⊖θ«
Repeat until the target becomes 1.
Ｆ∧⁻⊖θＸχ⊖Ｌθ¬﹪⊖θＸχ÷⊕Ｌθ²
Look to see if the target is of the form xxx0001 or xxxx0001, but not 10..01. (This expression ...
1
C++ Recursive Solution:
int reverse(int n)//reverses the number
{
int rev=0;
while(n>0)
{
rev=rev*10+n%10;
n/=10;
}
return rev;
}
int sol(int n, int x)
{
if(n==x)// base case
return 0;
if(n>x)// base case
return 1e5;
if(reverse(n)<=n)// otherwise, recursion will happen infinitely
...
3
Jelly, 16 bytes
Recursion might well end up being less bytes.
ṚḌ;‘))Fṭ
1Ç¡ċ€ċ0
A monadic Link accepting a positive integer which yields a non-negative integer
Try it online!
Or try a faster, 17 byte version
How?
ṚḌ;‘))Fṭ - Helper Link: next(achievable lists)
) - for each (list so far):
) - for each (value, V, in that list):
Ṛ - ...
7
Haskell, 82 73 bytes
r=read.reverse.show
f 1=0
f a=1+(minimum$f(a-1):[f$r a|r a<a,mod a 10>0])
Try it online!
Simplest recursion method.
-9 bytes thanks to Christian Sievers
3
Javascript (ES6), 208 bytes
Recursive, depth-first search. A breadth-first approach would be probably faster, but less golfy.
Input: a multi line string, using 1 for ghosts, 4 for solid objects, 6 for Jimmy and 2 for empty space.
f=(s,l=-~s.search`
`,j=s.search(6),g=[...s],x=j%l)=>j<l|!g[j+l]|!x|x>l-3||(g[j]=6,![...g].some((a,i)=>a&1&&...
1
Jelly, 94 89 bytes
Ø.,U$;N$+®ŒṬ€×8+®ŒṬ¤+&7$Ç€Ẹ
&Ɱ8,2ŒṪ€Ḣ©_¥/Ṡ01¦Ạ¡€+ƲṪŒṬḤ+&13$ÑÇFṀ>8Ʋ?
|Ø.¦4Z$⁺FṀ=12ƲÇFṀ>8Ʋ?
Try it online!
A full program that takes an integer matrix as its argument, with 0 as space, 1 as wall, 2 as ghost and 8 as Jimmy. Returns 1 for escape and 0 for no escape.
6
Python 2, 199 bytes
def g(I,G,W,w,h):
u,v=I.real,I.imag;R=1-(w-1>u>0<v<h-1);H=[z+cmp(u,z.real)+cmp(v,z.imag)*(u==z.real)*1jfor z in G]
for d in(R<1>(I in H+W))*range(4):J=I+1j**d;R|=(J in W)<g(J,H,W+[I],w,h)
return R
Try it online!
Rewrite of Chas Brown's solution using complex numbers.
All the coordinates are represented as a ...
8
Python 2, 236 235 227 212 bytes
def f((x,y),G,M,U=[]):
R=1-(len(M[0])-1>x>0<y<len(M)-1);H=[(u+cmp(x,u),v+cmp(y,v)*(u==x))for u,v in G];d,e=0,1
for _ in' '*4*(R<1>((x,y)in H)):J=z,w=x+d,y+e;d,e=-e,d;R|=M[w][z]>(J in U)<f(J,H,M,U+[J])
return R
Try it online!
-15 bytes thx to Bubbler
As input, takes a tuple (x,y) as jimmy's ...
2
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!
4
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+=(...
5
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 ...
Top 50 recent answers are included
