Code Golf Asked on October 27, 2021

Given a $2times 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.

A $2times 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.

Truthy or Falsey value indicating if the maze is solvable.

In these test cases, `x`

represents wall and `.`

represents empty tile.

```
.
.
```

```
..
x.
```

```
.x
..
```

```
...
...
```

```
..x
x..
```

```
....
..x.
```

```
.x...x...
...x...x.
```

```
...xx.....x
xx.....xx..
```

```
.x
x.
```

```
.x.
.x.
```

```
.xx
xx.
```

```
.xxx.
..x..
```

```
..x.
xxx.
```

```
.xx.x..
..xx...
```

```
.....x.x.
xxx.x....
```

```
....xx.xxx
.....xxx..
```

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

Answered by user100690 on October 27, 2021

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

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.

Answered by Donat on October 27, 2021

```
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.```
^((''
|^)(('.
)*|(.'
)*))*$
```

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.

```
^((''
|^)(.?'.?
)?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.

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

```
^(.(?=.*
(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.

Answered by Deadcode on October 27, 2021

```
+ƝẠƇ
```

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.

```
ḋ×ṛɗ/Ẹ
```

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.

Answered by xigoi on October 27, 2021

Based on @xnor's observation, this checks if there are `x`

s 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!

```
xudyx
```

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`

).

Answered by Dom Hastings on October 27, 2021

```
^(.)* ?#.*
(?>(?<-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.

Thanks to Deadcode for -9 bytes.

Answered by emanresu A on October 27, 2021

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

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.

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

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.

Answered by user on October 27, 2021

```
=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

Answered by Chronocidal on October 27, 2021

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

Answered by SomoKRoceS on October 27, 2021

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

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.

Answered by Jonah on October 27, 2021

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

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

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.

Answered by Jonah on October 27, 2021

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

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:

- remove first item from bottom row of maze + add
`1`

at the end - bottom row of maze
- 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

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

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

Answered by Dominic van Essen on October 27, 2021

Port of @Bubbler's answer.

```
€ü~øP_P
```

```
€ Map:
ü Apply to pairs:
~ OR
ø Transpose
P Product
_ NOT
P Product
```

Answered by user92069 on October 27, 2021

```
∧/⍲⌿2∨/⎕
```

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

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

Answered by Bubbler on October 27, 2021

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

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

Answered by user92069 on October 27, 2021

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

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.

Answered by xnor on October 27, 2021

`-p0`

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

Answered by Xcali on October 27, 2021

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

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.

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

Answered by Luis Mendo on October 27, 2021

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

Try it online! Link is to verbose version of code. Takes two strings of `.`

s and `x`

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

Answered by Neil on October 27, 2021

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

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!

Answered by Dingus on October 27, 2021

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP