Can the maze be solved?

Question

Task

• Print 0 if an n*m maze cannot be solved
• Print 1 if an n*m maze can be solved (in 1 or more ways)

(so I'm not asking for paths but if it's possible to solve!!!)

Example

Input array(2d):

[[0,0,0,0,0,0,1],[0,0,0,0,0,1,0],[0,0,0,0,1,0,0],[1,0,0,0,0,0,0]]
XXXXXXXXX
XS XX
X X X
X X X
XX FX
XXXXXXXXX
0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line

Rule The start position is 0,0 and the end position is n,m You can only move horizontally and vertically Shortest code wins

• apsillers: Should the input be a string or an array?
• trichoplax is on Codidact now: If there is a 1 (wall) at (n,m) should the code return 0?
• Martin Ender: (Same for a wall at (0,0)?)
• Nick Matteo: You say it's a n×m maze, but your indexing implies that it's an (n+1)×(m+1) maze.
• flawr: I am looking forward to the regex solution=)

Answer 1

Dyalog APL, 27 characters

⊃⌽∨.∧⍨⍣≡1≥+/ ̈|∘.-⍨,(×ばつ⍳∘⍴)⎕

⎕ evaluated input. APL distinguishes between a matrix and a vector of vectors. This program assumes that the input is a matrix.

(×ばつ⍳∘⍴)A is a fork equivalent to (~A) ×ばつ ⍳⍴A. It's needed to avoid mentioning ⎕ twice or introducing a variable.

⍴A is the shape of A. For a 4-by-7 matrix the shape is 4 7.

⍳ is the index generator. ⍳4 is 1 2 3 4. ⍳4 7 is the vectors (1 1)(1 2)...(4 7) arranged in a 4-by-7 matrix.

~A flips the bits of A.

×ばつ by multiplying ⍳⍴A by the flipped bits, we preserve the coordinates of all free cells and turn all walls into 0 0.

, ravels the matrix of coordinate pairs, i.e. linearizes it into a vector. In this case the vector will consist of pairs.

∘.-⍨A or A∘.-A subtracts elements of A pairwise. Note that here the elements of A are themselves pairs.

| absolute value

+/ ̈ sum each pair of absolute values. This gives us the grid distances between every pair of cells in the maze, save for walls.

1≥ we are only intrested in neighbours at a distance no more than 1, this also excludes walls. Now we have a graph's adjacency matrix.

∨.∧⍨⍣≡ Floyd--Warshall's transitive closure algorithm

(f⍣n)A (not used here) where n is an integer is the power operator. It applies f to A n times: f f ... f A.

(f⍣g)A where g is a function, is the fixed point operator, a.k.a. "power limit". It keeps on computing the series A, f A, f f A, ... until ((f⍣i)A) g ((f⍣(i+1))A) returns true for some i. In this case we use match (≡) as g.

∨.∧⍨A or A∨.∧A is a step in Floyd's algorithm. f.g is a generalisation of matrix multiplication (×ばつ), here we use conjunction (∧) and disjunction (∨) in place of + and ×ばつ.

⊃⌽ After ⍣≡ has applied the step enough times and reached a stable state, we must look up the top-right corner of the matrix to get the result, so we flip it (⌽) and take the first, top-left item (⊃).

Visualization of ⍣≡'s steps

Answer 2

CJam, (削除) 42 (削除ここまで) (削除) 41 (削除ここまで) (削除) 39 (削除ここまで) (削除) 36 (削除ここまで) 35 bytes

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=

Based on the ideas in this answer.

4 bytes thanks to Optimizer.

Input format:

[[0 0 0 0 0 0 1] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0] [1 0 0 0 0 0 0]]

• jimmy23013: @Optimizer Thanks for that. But then I found a shorter way...
• Optimizer: q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW= - 36. Although it assumes that the first three characters of the input will be [[0

Answer 3

Python, 164 bytes

def s(a):
 d=[(0,0)]
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

I was reluctant to post this because it's practically how I'd normally do flood fill, just lightly golfed. But here it is anyway.

• Stef: (x,y) is in [(i-1,j),(i,j-1),(i+1,j),(i,j+1)] iff abs(x-i)+abs(y-j)<2, although I'm not sure if that can help

Answer 4

Perl, 73 bytes

69 bytes of code + 4 bytes for -n0E (not sure how the tags where counted in 2014, so I counted them for 4 instead of 2, but it doesn't matter a lot).

/.*/;s/(^0|A)(.{@{+}})?0/A2ドルA/s||s/0(.{@{+}})?A/A1ドルA/s?redo:say/A$/+0

Try it online! (and if you replace the 1111011 line with 1111111, the maze isn't solvable anymore, and the output will be 0 instead of 1 : Try it online!)

Explanations:

This code will find every reachable cell of the maze (and mark them with a A): if a cell touches a cell marked with a A, the it's reachable and we mark it with a A too; and we do that again (redo). That's done thanks to two regex: s/(^0|A)(.{@{+}})?0/A2ドルA/s checks if a space is on the right or the bottom of a A, while s/0(.{@{+}})?A/A1ドルA/s checks if a space is on the left or on top of a A. At the end, if the last cell contains a A it's reachable, otherwise it's not (that's what say/A$/+0 checks; the +0 is here to make sure the result will be 0 or 1 instead of empty string and 1).
Note that /.*/ will match an entire line, thus setting @+ to the index of the end of the first line, which happens to be the size of a line, which allow use to use .{@{+}} to match exactly as many character as there are on a line. (@{+} is equivalent to @+, but only the former can be used in regex)

• Jitse: For this test case, your code considers the maze solvable even if the final position is 1.
• Dada: @Jitse Good catch. Actually, it was because the TIO links were not using the right code (I guess it was some earlier version and I didn't spot it). The answer is still valid, and I've updated the TIO links. Your example works then fine: Try it online!
• Jitse: Oh, right! Thanks for the clarification, I like this approach.
• Dada: @Jitse thanks, that's one of my favorite golfs :)

Answer 5

Ruby, (削除) 133 (削除ここまで) (削除) 130 (削除ここまで) 129 characters

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==0}}
f[0,0]
p a[-1][-1]

Input on STDIN, outputs 1 or 0 on STDOUT.

Annoyingly long. It simply does a flood-fill of 1s from (0, 0), and then checks to see whether the "end" square is a 1.

• trichoplax is on Codidact now: Will this treat the maze as solvable if it already contains a 1 at (n,m)?

Answer 6

Java, 418 bytes

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

My first code golf. I don't know why I chose Java - it's so bad for golfing xD

Example maze would be inputted via stdin like this:

......#;.....#.;....#..;#......

• Pavel: Pro tip: name your class something one character long, ditch the space between String[] and a, and take input from command line arguments rather than StdIn, which is allowed.

Answer 7

Python 184 (削除) 188 (削除ここまで)

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

This got much longer than I thought it would be :( Anyway, I'll add an explanation once I can't golf it any longer.

Answer 8

J, 75 chars

Powering of the adjacency matrix (very time and memory inefficient). (Is it called powering in English?)

 ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Some test cases:

 m1=. 0 0 0 0 0 0 1,. 0 0 0 0 0 1 0,. 0 0 0 0 1 0 0,. 1 0 0 0 0 0 0
 m2=. 0 1 1 ,. 0 0 0
 m3=. 0 1 0 ,. 1 1 0
 m4=. 0 1 1 0 ,. 0 0 1 0
 ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0

Answer 9

Python 3, 136 bytes

def f(g,x=0,*p):w=len(g[0])+1;l=w*len(g);return~x%w*(-1<x<l)*~-(x in p)and any(g[x//w][x%w]and f(g,x+a,*p,x)for a in(1,-1,w,-w))or-~x==l

Try it online!

Uses 0 for wall, 1 for free space.

Port of my answer to Find the shortest route on an ASCII road.

Answer 10

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!