23
\$\begingroup\$

Given a \$2\times N\$ maze, determine if you can get from the start top left corner to end bottom right corner using only up, down, left, and right moves.

Input

A \$2\times N\$ block (\$1 \le N \le 100\$) of your choice of two distinct characters, one representing walls and the other representing empty tiles that can be moved through. You may use any reasonable input format, ex. one string with newline, two strings, or two lists of characters, or a binary matrix.

It is guaranteed the start and end positions are empty tiles.

Output

Truthy or Falsey value indicating if the maze is solvable.

Examples

In these test cases, x represents wall and . represents empty tile.

True cases

.
.
..
x.
.x
..
...
...
..x
x..
....
..x.
.x...x...
...x...x.
...xx.....x
xx.....xx..

False cases

.x
x.
.x.
.x.
.xx
xx.
.xxx.
..x..
..x.
xxx.
.xx.x..
..xx...
.....x.x.
xxx.x....
....xx.xxx
.....xxx..
\$\endgroup\$
25
  • 15
    \$\begingroup\$ I think this is equivalent to "check that no two x's touch diagonally or vertically". \$\endgroup\$ – xnor Jul 10 '20 at 23:36
  • 1
    \$\begingroup\$ @xnor are you sure? \$\endgroup\$ – qwr Jul 10 '20 at 23:38
  • 1
    \$\begingroup\$ can we take the input as vertical format? (2 columns wide)? \$\endgroup\$ – Level River St Jul 11 '20 at 2:00
  • 1
    \$\begingroup\$ 3xn or 4xn might be interesting as a separate challenge, which is more complex than 2xn but it is still guaranteed to have a non-backtracking path on any solvable maze. \$\endgroup\$ – Bubbler Jul 11 '20 at 6:39
  • 1
    \$\begingroup\$ @LevelRiverSt sure \$\endgroup\$ – qwr Jul 11 '20 at 6:55

20 Answers 20

14
\$\begingroup\$

Python 2, 26 bytes

lambda m,n:m&(n/2|n|2*n)<1

Try it online!

Takes inputs as numbers representing bit sequences, which the challenge author okayed. Though I realized this representation is kind-of suspect because leading zeroes are ambiguous.

The idea is to check whether any 1 in the top number (x symbol in the top line) corresponds to a 1 in any of the three adjacent positions in the below number. We do this by "smearing" each bit the bottom number n in three positions as n/2|n|2*n, or-ing the number with its left and right shift.

It would also work to do (m|m*2)&(n|n*2)<1, but precedence means more parens are needed.

\$\endgroup\$
1
  • \$\begingroup\$ nice solution. I guess you could do the same in C with a 128 bit integer type. \$\endgroup\$ – qwr Jul 11 '20 at 0:32
13
\$\begingroup\$

APL (Dyalog Unicode), 8 bytes

∧/⍲⌿2∨/⎕

Try it online!

Takes input from stdin as a 2-row boolean matrix, where 1 is a wall and 0 is a space. Prints 1 for true, 0 for false (which are the only truthy/falsy values in APL).

How it works

Given a maze (1=wall, 0=space)

0 0 1 0 0 0 1
1 0 0 1 1 0 0

Think of putting a bar between every two horizontally adjacent cells, where at least one side must be a wall (1):

0   0 | 1 | 0   0   0 | 1
1 | 0   0 | 1 | 1 | 0   0
          ^

Then the maze has a solution if and only if no two bars align vertically, as pointed above.

∧/⍲⌿2∨/⎕
       ⎕  ⍝ Take input from stdin
    2∨/   ⍝ Compute the "bars" in the above diagram,
          ⍝ by ORing every two horizontally adjacent bits
  ⍲⌿      ⍝ Compute NAND of the two bars vertically;
          ⍝ each column is passable unless both rows are 1
∧/        ⍝ Reduce by AND; check if all columns are passable
\$\endgroup\$
1
  • 3
    \$\begingroup\$ That is a clever solution! I would think inserting the walls would take more code than it actually does. \$\endgroup\$ – qwr Jul 11 '20 at 6:55
11
\$\begingroup\$

Ruby, 29 28 bytes

->t,b{"#{t+2*b}"!~/45|54|6/}

Try it online!

Takes input as two integers, t and b, each representing a row of the maze, with digits 1 representing empty tiles and 2 representing walls. Returns false if t+2*b contains the digits 45 or 54 (two walls touch diagonally) or 6 (two walls touch vertically). Returns true otherwise.

It's possible to get down to 22 bytes by porting @xnor's very elegant Python 2 answer: Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Nice approach, though I don't think it enforces the rule start top left corner to end bottom right corner; e.g. I think "x\n." should fail, but it passes. \$\endgroup\$ – Digital Trauma Jul 11 '20 at 1:02
  • 1
    \$\begingroup\$ @DigitalTrauma That's not a valid maze for this challenge: 'It is guaranteed the start and end positions are empty tiles.' \$\endgroup\$ – Dingus Jul 11 '20 at 1:05
  • \$\begingroup\$ I love this approach. Well done. \$\endgroup\$ – Jonah Jul 11 '20 at 23:10
  • \$\begingroup\$ @Dingus - right - yes - sorry, I missed that bit \$\endgroup\$ – Digital Trauma Jul 12 '20 at 1:07
11
\$\begingroup\$

Regex (POSIX ERE / RE2 or better), 13 10 bytes

x(|
|.
.)x

Try it online! - POSIX ERE
Try it on regex101 - RE2
Try it online! - ECMAScript
Try it online! - .NET

The problem statement didn't say anywhere that there specifically had to be \$2\$ rows and \$N\$ columns rather than \$2\$ columns and \$N\$ rows, or that the input can't be taken in transposed form.

So here is a solution that works on virtually any regex engine. Like A username's answer, this matches iff the maze is not solvable. The wall character is x, and empty tiles can be represented by any other character.

Regex (POSIX ERE / RE2 or better), 33 30 27 bytes

^((''
|^)(('.
)*|(.'
)*))*$

Try it online! - POSIX ERE
Try it on regex101 - RE2
Try it online! - ECMAScript
Try it online! - .NET

This is version that matches solvable mazes and doesn't match unsolvable mazes. It was interesting to implement in a regex flavor that has no negative lookahead. The way it works is pretty much like actually walking through the maze and solving it.

The empty tile character is ', and walls can be represented by any other character. The input given to this regex must not begin with a newline, and must end with a single newline.

The version of POSIX ERE on TIO treats newlines incorrectly in this version, even though with REG_NEWLINE not set, newline is supposed to be treated like any normal character. So in the ERE test harness, I made it use ! as a line separator instead of newline. But when tested locally on my machine, it works with actual newlines.

Regex (GNU ERE or better), 29 24 bytes

^((''
|^)(.?'.?
)?\3*)*$

Try it online! - GNU implementation of POSIX ERE, old version
Try it on regex101 - ECMAScript
Try it online! - ECMAScript
Try it online! - .NET

The addition of backreferences allows for a more compact regex. But there doesn't seem to be a clear-cut standard that includes backreferences without lookaheads. The closest appears to be GNU ERE, used by egrep and sed -E, but there doesn't seem to be any library interface for it, and neither of those utilities support matching raw newlines.

The version of GNU libc on TIO enables backreferences in ERE, but with an up-to-date version of the libraries, they're only enabled in BRE, not ERE. The version on TIO has the newline bug, though, so same workaround for newlines is used in the TIO test harness.

The empty tile character is ', and walls can be represented by any other character. Matches iff the maze is solvable. The input given to this regex must not begin with a newline, and must end with a single newline.

Regex (ECMAScript or better + /s flag), 17 bytes

^(?!.*x(|
|.
.)x)

Try it on regex101 - ECMAScript 2018
Try it online! - ECMAScript 2018
Try it online! - .NET

With negative lookahead it is trivial to modify the 10 byte regex into one that matches iff the maze is solvable.

As in the regex it's based on, the wall character is x, and empty tiles can be represented by any other character.

Note that the /s flag was introduced in ECMAScript 2018 (JavaScript ES9).

Regex (Perl / Java / PCRE2 / .NET), 29 bytes

^(.(?=.*
(\2.|)))+x.*
\2.?.?x

Try it online! - Perl
Try it on regex101 - PCRE2
Try it online! - .NET

This takes the input in the form of \$2\$ rows of \$N\$ columns. The challenge just wouldn't be complete with that submitted only in .NET flavor and not PCRE as well. Matches iff the maze is not solvable. The wall character is x, and empty tiles can be represented by any other character.

The .NET balanced group method is still shorter (at 27 bytes), as expected.

This solution takes advantage of the fact that the upper-left corner will never be blocked. It would need to be modified otherwise, because it looks for a wall in the top row that has a wall diagonally or orthogonally below it. It starts this search at the second column from the left.

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

Snails, 7 bytes

Based on @xnor's observation, this checks if there are xs above (u), below (d) or diagonally from (y) another x. Returns 0 for solvable mazes a positive integer otherwise. I've wanted to use this language for so long!

\xudy\x

Try it online!

Explanation

Snails is a 2D pattern matching language that was created by @feresum which is not entirely unlike regex.

In this program, the \x matches a literal x, then looks above, below or diagonally to it (udy) for another literal x (\x).

\$\endgroup\$
1
  • \$\begingroup\$ As I remembered that challenge from years ago, I was looking for this language in the answers. \$\endgroup\$ – mbomb007 Apr 8 at 19:25
5
\$\begingroup\$

J, 19 17 bytes

0=1#.[:,*&#./;._3

Try it online!

-2 thanks to Bubbler for suggesting Max Cubes instead of subarrays.

A port of Bubbler's APL solution saves 1 byte:

2 e.[:+/2+./\"1]

but it seemed a shame not use J "Max Cubes" here, as the problem seems almost tailor-made for it.

How

Let's take the example:

0 1 1 1 0 0
0 0 0 0 1 0

v;._3 will apply the verb v to every 2x2 block. Eg, <;._3 will produce:

┌───┬───┬───┬───┬───┐
│0 1│1 1│1 1│1 0│0 0│
│0 0│0 0│0 0│0 1│1 0│
└───┴───┴───┴───┴───┘

In our case, we want a verb that detects "walls" (diagonal or vertical). */@:#. does the job. It converts each row from a binary number into an integer #., and then multiplies the resulting 2 integers together */@:. This result will always be 0 if there is no wall.

So now we can just sum all of the results 1#. and check if the result is 0 0=. If it is, there are no walls and we can get through. Otherwise, we're blocked.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 17 bytes for the top solution by using MaxCubes instead. \$\endgroup\$ – Bubbler Apr 8 at 3:35
  • \$\begingroup\$ @Bubbler thanks, updated. but why did you way "top solution"? there are still some others including yours quite a bit shorter, no? \$\endgroup\$ – Jonah Apr 9 at 13:24
4
\$\begingroup\$

MATL, 10 9 7 bytes

4&1ZI2<

Input is a binary matrix, with 1 for . and 0 for x.

Output is an array of ones (which is truthy) if the maze is solvable, or an array containing at least a zero (which is falsey) if not solvable.

Try it online! Or verify all test cases including check for truthyness or falsiness.

Explanation

Solvability is equivalent to full connectedness of all non-wall tiles

The maze is solvable if and only if all non-wall tiles are connected to each other using 4-neighbourhood.

Proof

All connected ⇒ solvable: this is clear.

Solvable ⇒ all connected. Let the maze be

A ··· SUWY
B ··· TVXZ

This maze is solvable by assumption. Consider its rightmost square of size 2:

WY
XZ

There are two ways that Z can be connected to the input:

  • Through tiles W and Y: this means that W and Y are non-wall. They are connected to Z. If X is non-wall it is connected to W, Y and Z too.
  • Through tile X: this means that X is non-wall. It is connected to Z. If W or Y are non-wall they are connected to X and Z too.

We now proceed from either W or X to the left, considering the square

UW
VX

By the same reasoning as above, all non-wall tiles in this square will be connected to each other, and to the tiles from the previous square.

This way we proceed until A is reached (which is possible by hypothesis), and all non-wall tiles are connected.

How the code works

The program checks that the image formed by considering wall tiles as background and non-wall tiles as foreground has a single connected component.

4      % Push 4
&1ZI   % Implicit input: binary matrix. Label connected components using
       % 4-neighbourhood. This assigns a different label to each connected
       % component of ones in the input. Labels are positive integers. The
       % result is a matrix of the same size as the input 
2<     % Less than 2? Element-wise. All comparisons will be true if and
       % only if there is a single connected component
       % Implicit diplay
\$\endgroup\$
4
\$\begingroup\$

R, 38 bytes

function(t,b)all(c(b[-1],T,b,T,b)[!t])

Try it online!

Checks that the bottom row is 'open' at position x-1, x and x+1 for every 'closed' position in the top row.

How?

  • consider matrix of 3 rows:
  1. remove first item from bottom row of maze + add 1 at the end
  2. bottom row of maze
  3. add 1 at the start of the bottom row of maze without last item
  • check that all elements are 1 in columns where top row of maze is 0

Golfing:

  • R 'recycles' logical indices, so we don't actually need to make a matrix, we can just list the elements
  • no need to remove the last item of the bottom row of maze since it's guaranteed to be true

R, a different approach, still 38 bytes

function(t,b)all(t&t[-1]|b&c(b[-1],1))

Try it online!

Completely different approach, but annoyingly the same number of characters. Checks that it's always possible to move rightwards, either on the top or on the bottom.

How?

top & top[-1] = logical AND of each element of top with it's neighbour to the right

| = logical OR

bot & bot[-1] = logical AND of each element of bot with it's neighbour to the right

The last element (that has no rightward neighbour) is a problem, because R 'wraps around' the longer vector, so if the last top element is 0 and the first bottom element is 0 then it will fail. We can fix this by forcing it to evaluate to TRUE, which we can do by adding a 1 at the end of the 'chopped-off' bottom row (since we know the last element of the full-length row must be 1).

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

Excel, 38 bytes

=AND(ISERROR(FIND({12,3,21},A1+2*A2)))

Input is 2 strings (1 for each row of the maze), in cells A1 and A2, with 1 for a Wall, and 0 for a space.

First, it adds the first row, and twice the second row together. This will convert each column to base-4 representation of whether it contains no walls (0), wall in the top row only (1), wall in the bottom row only (2), or wall in both rows (3)

We then try to FIND any examples where there are walls in both rows (3), or walls in different rows of adjacent columns (12 or 21)

If both of these return errors, then there is a clear path

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I love it when Excel is able to compete competitively against 'real' programming languages! Well done. \$\endgroup\$ – Dominic van Essen Jul 14 '20 at 9:33
  • 2
    \$\begingroup\$ @DominicvanEssen Are you implying Excel isn't a real programming language? It's turing complete \$\endgroup\$ – user Sep 29 '20 at 14:15
4
\$\begingroup\$

Jelly, 4 bytes

+ƝẠƇ

Try it online!

Takes a list of pairs, where 0 represents a path and 1 represents a wall. Returns a falsy value if the maze is solvable and a truthy value if not.

Jelly, 6 bytes

ḋ×ṛɗ/Ẹ

Try it online!

Takes a list of pairs, where 0 represents a wall and 1 represents a path. Returns 1 if the maze is solvable and 0 if not.

\$\endgroup\$
4
+50
\$\begingroup\$

Regex (.NET), 35 31 27 bytes

^(.)* ?#.*
(?>(?<-1>.)*) ?#

This had to be done. Checks if the string contains one of the following (uses #s and spaces) :

 #
# 
# 
# 
# 
 #

Matches impassible grids, doesn't match passible ones.

See Martin Ender's excellent capture group documentation.

Try it online!

Thanks to Deadcode for -9 bytes.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Hm, now I decide if you're a reputatable source :) \$\endgroup\$ – Wezl Apr 7 at 12:41
  • 1
    \$\begingroup\$ Cool to see someone new giving regex answers! So, note that since both rows will always have the same number of characters in them, (?<-1>.)* will always initially match will all copies of \1 popped from the balanced group stack. It can only do so less than the maximum number of times if the regex engine backtracks into it when it tries to make the following # match. So you can save 4 bytes by wrapping it in an atomic group and getting rid of the conditional. \$\endgroup\$ – Deadcode Apr 7 at 17:37
  • \$\begingroup\$ @Deadcode Thanks! I just had a look at the link above and tried to figure it out. I'm not very good at this. \$\endgroup\$ – emanresu A Apr 7 at 20:04
  • \$\begingroup\$ Hint: The (?<-1>.)* is the thing you don't want to be backtracked once it's finished. So wrap it in an atomic group (?>...). And then the (?(1)...|...) conditional is no longer needed; you can remove the conditional, which would now always evaluate its condition as "false" since \1 will now be guaranteed to no longer have any contents by that point, so you can keep its former "false" case and discard its "true" case. \$\endgroup\$ – Deadcode Apr 7 at 20:13
  • \$\begingroup\$ @Deadcode Ok, thanks! \$\endgroup\$ – emanresu A Apr 8 at 4:22
3
\$\begingroup\$

Perl 5 -p0, 67 bytes

$x=$_;$_=!grep{$b=$_-1;$x=~/^.{$b,$_}x.*?\n.{$b,$_}x/gm}1...5*y///c

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 26 23 bytes

⭆⪫E²S¶⎇⁼ι.ψι←¤-J⁰¦⁰T¹¦¹

Try it online! Link is to verbose version of code. Takes two strings of .s and xs as input (actually any character other than space or . would work) and outputs - if the maze can be solved or a blank space if it cannot. Edit: Saved 3 bytes because I had misread the question. Explanation:

⭆⪫E²S¶⎇⁼ι.ψι

Print the input, but change all the .s to null bytes, since Charcoal knows how to fill those.

Move to the end position.

¤-

Flood fill the null bytes with -s (chosen because this is Charcoal's default output character for a Boolean true value, but any character other than space would work).

J⁰¦⁰

Jump back to the start position.

T¹¦¹

Delete everything other than the start position, which is now - if the maze could be solved, or blank if it could not be solved.

\$\endgroup\$
2
  • \$\begingroup\$ what do you mean by "it's not clear which the start and end positions are"? \$\endgroup\$ – qwr Jul 11 '20 at 0:33
  • \$\begingroup\$ @qwr I must have been too tired... I see it now. \$\endgroup\$ – Neil Jul 11 '20 at 7:17
2
\$\begingroup\$

Io, 90 bytes

method(x,y,x map(i,v,v>0and(list(i-1,i,i+1)map(c,y at(c abs))detect(>0)))reduce(or)!=true)

Try it online!

Io, 98 bytes

Port of Bubbler's APL solution.

method(x,(o :=x map(o,o slice(0,-1)map(i,v,v+o at(i+1))))at(0)map(i,v,v*o at(1)at(i))push(0)sum<1)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E (legacy), 7 bytes

Port of @Bubbler's answer.

€ü~øP_P

Try it online!

Explanation

€       Map:
 ü          Apply to pairs:
  ~             OR
   ø    Transpose
    P   Product
     _  NOT
      P Product
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Max@MorphologicalComponents[#,CornerNeighbors->1<0]<2&

Try it online!

Credit for this idea goes to this answer by alephalpha from a couple years ago, where it used in a different context.

The core insight here is that -- if the maze can be solved -- then the "spaces" form a single contiguous morphological chunk. And Wolfram has a built-in for detecting that.

\$\endgroup\$
2
\$\begingroup\$

Javascript, 64 bytes

(a,b)=>!a.map((e,i)=>e&&(b[i-1]+b[i]+b[i+1])).reduce((x,y)=>x+y)

Input: two lists.

Example:

console.log(f([0,0,0,1,0,0,1,0],[1,1,0,0,0,0,0,0]))

Outputs true.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ This has 3 false positives in the test cases: Try it online! \$\endgroup\$ – Deadcode May 4 at 2:12
2
\$\begingroup\$

Haskell, 53 51 bytes

or.map(or.foldr1(zipWith(&&))).mapM(\x->[x,tail x])

Try it online!

The anonymous function takes a list of two lists where True is a wall and False is empty. Returns False if the maze is solvable.

\$\endgroup\$
1
  • \$\begingroup\$ is the function c or (#)? \$\endgroup\$ – Wezl Apr 7 at 20:10
1
\$\begingroup\$

Prolog, 99 bytes

f([[1,_],[_,1]|_]):- !,0=1.
f([[_,1],[1,_]|_]):- !,0=1.
f([[1,1]|_]):- !,0=1.
f([_|T]):-T==[];f(T).

Try it in SWISH

xnor's comment that the problem statement was equivalent to checking if no 2 x's touched vertically or diagonally helped me a lot here.


Imperfect version (never terminates if false), 66 bytes

f([X|T],C):-nth0(C,X,0),(T==[];f(T,C);D is mod(C+1,2),f([X|T],D)).

Try it in SWISH

Requires the first input to be a list of length N containing lists of length 2. Empty tiles are denoted by 0, and walls are denoted by anything else (I could also have used characters, I suppose, but this seemed easier). The second input (C) is 0 if we're currently at the tile on top, and 1 if we're at the tile on the bottom.

An example query would be:

?- f([[0,1],[0,1],[0,0],[1,0],[1,0],[0,0],[0,0],[0,1],[0,1],[0,0],[1,0]],0).
true.

However, if the maze is unsolvable, there wouldn't be any output, it'd just keep running.

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

JavaScript, 63 bytes

n=>k=>!n.filter((e,i)=>e>0&[k[i-1],k[i],k[i+1]].includes(1))[0]

Takes input in currying format, each argument being an array of 1s and 0s. Outputs true if the maze is solvable and false if unsolvable.

\$\endgroup\$
1

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.