20
\$\begingroup\$

The puzzle

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

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

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

\$\endgroup\$
  • \$\begingroup\$ Should the input be a string or an array? \$\endgroup\$ – apsillers Dec 23 '14 at 14:36
  • 3
    \$\begingroup\$ If there is a 1 (wall) at (n,m) should the code return 0? \$\endgroup\$ – trichoplax Dec 23 '14 at 15:17
  • 3
    \$\begingroup\$ (Same for a wall at (0,0)?) \$\endgroup\$ – Martin Ender Dec 23 '14 at 15:18
  • 3
    \$\begingroup\$ You say it's a n×m maze, but your indexing implies that it's an (n+1)×(m+1) maze. \$\endgroup\$ – Nick Matteo Dec 23 '14 at 20:33
  • 3
    \$\begingroup\$ I am looking forward to the regex solution=) \$\endgroup\$ – flawr Dec 23 '14 at 21:25

10 Answers 10

7
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ @Optimizer Thanks for that. But then I found a shorter way... \$\endgroup\$ – jimmy23013 Dec 23 '14 at 16:04
  • 1
    \$\begingroup\$ q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW= - 36. Although it assumes that the first three characters of the input will be [[0 \$\endgroup\$ – Optimizer Dec 23 '14 at 16:28
7
+100
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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/A$2A/s||s/0(.{@{+}})?A/A$1A/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/A$2A/s checks if a space is on the right or the bottom of a A, while s/0(.{@{+}})?A/A$1A/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)

\$\endgroup\$
  • \$\begingroup\$ For this test case, your code considers the maze solvable even if the final position is 1. \$\endgroup\$ – Jitse Nov 7 at 10:57
  • \$\begingroup\$ @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! \$\endgroup\$ – Dada Nov 7 at 11:17
  • \$\begingroup\$ Oh, right! Thanks for the clarification, I like this approach. \$\endgroup\$ – Jitse Nov 7 at 11:20
  • \$\begingroup\$ @Jitse thanks, that's one of my favorite golfs :) \$\endgroup\$ – Dada Nov 7 at 11:21
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Will this treat the maze as solvable if it already contains a 1 at (n,m)? \$\endgroup\$ – trichoplax Dec 23 '14 at 15:18
2
\$\begingroup\$

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:

......#;.....#.;....#..;#......
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Pavel Jan 5 '17 at 5:05
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

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