Solve a 2xN Maze

Question

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

Answer 1

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

Answer 2

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.

Answer 3

Ruby, ²⁹ 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!

Answer 4

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.

Answer 5

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).

Answer 6

J, ¹⁹ 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.

Answer 7

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

Answer 8

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).

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

Perl 5 -p0, 67 bytes

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

Try it online!

Answer 13

Charcoal, 26 23 bytes

⭆⪫Ｅ²Ｓ¶⎇⁼ι.ψι←¤-Ｊ⁰¦⁰Ｔ¹¦¹

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:

⭆⪫Ｅ²Ｓ¶⎇⁼ι.ψι

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).

Ｊ⁰¦⁰

Jump back to the start position.

Ｔ¹¦¹

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

Answer 14

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.

Answer 15

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!

Answer 16

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

Answer 17

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.

Answer 18

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.

Answer 19

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.