16
\$\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\$
  • 11
    \$\begingroup\$ I think this is equivalent to "check that no two x's touch diagonally or vertically". \$\endgroup\$ – xnor Jul 10 at 23:36
  • 1
    \$\begingroup\$ @xnor are you sure? \$\endgroup\$ – qwr Jul 10 at 23:38
  • 1
    \$\begingroup\$ Can we input a binary matrix? \$\endgroup\$ – Luis Mendo Jul 10 at 23:40
  • \$\begingroup\$ @LuisMendo Ok i'll relax input rules a little. \$\endgroup\$ – qwr Jul 10 at 23:41
  • 1
    \$\begingroup\$ is input always "horizontal" like in examples? can I make them vertical instead? \$\endgroup\$ – Noone AtAll Jul 12 at 20:02

14 Answers 14

12
\$\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
| improve this answer | |
\$\endgroup\$
  • 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 at 6:55
11
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ nice solution. I guess you could do the same in C with a 128 bit integer type. \$\endgroup\$ – qwr Jul 11 at 0:32
9
\$\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!

| improve this answer | |
\$\endgroup\$
  • \$\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 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 at 1:05
  • \$\begingroup\$ I love this approach. Well done. \$\endgroup\$ – Jonah Jul 11 at 23:10
  • \$\begingroup\$ @Dingus - right - yes - sorry, I missed that bit \$\endgroup\$ – Digital Trauma Jul 12 at 1:07
4
\$\begingroup\$

J, 19 bytes

0=1#.2 2*/@:#.;._3]

Try it online!

A port of Bubbler's APL solution saves 3 bytes:

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

but it seemed a shame not use J "Subarrays" adverb 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

2 2 v;._3 will apply the verb v to every 2x2 block. Eg, 2 2 <;._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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -p0, 67 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\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
| improve this answer | |
\$\endgroup\$
2
\$\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).

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I love it when Excel is able to compete competitively against 'real' programming languages! Well done. \$\endgroup\$ – Dominic van Essen Jul 14 at 9:33
1
\$\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!

| improve this answer | |
\$\endgroup\$
1
\$\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
| improve this answer | |
\$\endgroup\$
1
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ what do you mean by "it's not clear which the start and end positions are"? \$\endgroup\$ – qwr Jul 11 at 0:33
  • \$\begingroup\$ @qwr I must have been too tired... I see it now. \$\endgroup\$ – Neil Jul 11 at 7:17
0
\$\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.

| improve this answer | |
\$\endgroup\$
0
\$\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.

| improve this answer | |
\$\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.