23
\$\begingroup\$

Your job is to write a program that takes a number N as input and outputs all 2-by-N mazes that are solvable.

Output format can be in the form of any two distinct values representing wall and empty - I use x and . here but you can use anything. You can have a matrix, array, string, ascii art, whatever is convenient, and it can be horizontal, as shown in my examples, or vertical.

A maze is solvable if it has a path of empty cells (represented here as .) from the left end to the right end. For example,

xxxx.....
.....x..x

is solvable, because you can trace a path (marked with O):

xxxxOOOOO
OOOOOx..x

But this is not.

xxx.x..
..xxx..

You cannot pass through diagonal gaps, so this is also not:

xxx...
...xxx

Testcases

1:

.
. 
 
.
x

x
.

2: 

..
..

..
.x

.x
..

..
x.

..
xx

x.
..

xx
..
\$\endgroup\$
7
  • \$\begingroup\$ Sandboxed \$\endgroup\$ – A username Apr 30 at 10:05
  • \$\begingroup\$ Can you use two different characters for walls? \$\endgroup\$ – Axuary Apr 30 at 14:04
  • \$\begingroup\$ Related (determining if the maze is solvable) \$\endgroup\$ – xigoi Apr 30 at 14:45
  • 1
    \$\begingroup\$ @pxeger No explicit separation needed. I'll add that. \$\endgroup\$ – A username Apr 30 at 21:47
  • 1
    \$\begingroup\$ So it seems from your test-cases, you can't move at a diagonal? That's different from some rogue-like dungeon games where you could move through a diagonal gap in walls. You might want to change your "but this is not" example to be only blocked by a diagonal, to make sure that's clear. \$\endgroup\$ – Peter Cordes May 1 at 2:37

16 Answers 16

11
\$\begingroup\$

Excel, 163 143 bytes

=LET(a,BASE(SEQUENCE(3^A1)-1,3,A1),b,FILTER(a,ISERROR(FIND(12,a))*ISERROR(FIND(21,a))),SUBSTITUTE(b,2,0)&"
"&SUBSTITUTE(SUBSTITUTE(b,1,0),2,1))

Use 1 for walls and 0 for empty cells.

Original

=LET(a,BASE(SEQUENCE(3^A1)-1,3,A1),b,FILTER(a,ISERROR(FIND(12,a))*ISERROR(FIND(21,a))),SUBSTITUTE(SUBSTITUTE(b,1,"X"),2,0)&"
"&SUBSTITUTE(SUBSTITUTE(b,2,"X"),1,0))

Uses 0 for empty cells and X for walls.

Link to Spreadsheet

\$\endgroup\$
8
\$\begingroup\$

C (gcc), 192 190 188 bytes

  • Saved two bytes thanks to ceilingcat using ++u<=\$\iff\$u++< and puts("")'s return value of 1 (i.e. the number of printed bytes).
  • Saved two bytes thanks to ceilingcat; transforming (a=L>>_+o&1)|(b=L>>o++&1)||(l=v=0),l|=a,v|=b; into v=(a=L>>_+o&1)|(b=L>>o++&1)?l|=a,v|b:(l=0); which when naming the major equivalent segment @ becomes @||(l=v=0),l|=a,v|=b; and v=@?l|=a,v|b:(l=0);.
s,o,l,v,a,b,L;e(_){for(L=0;L++<1<<2*_;s||puts("")){for(l=v=o=s=0;o<_;s|=l&v)v=(a=L>>_+o&1)|(b=L>>o++&1)?l|=a,v|b:(l=0);for(l=0;l/2<!s;l+=puts(""))for(o=0;o<_;)putchar(46+(L>>l*_+o++)%2);}}

Try it online!


Uses . as a path character and / as a wall character. Requires n < 16 assuming an int is 32 bits wide and can thus hold 2*n +1 bits. Due to this problem's combinatorial nature, this restriction should be of little hindrance. Else one may need to consider 128 bit systems.

If one was to allow barely printable characters like tab (ASCII 9) and newline (ASCII 10 = 9+1), one could save a byte by substituting s!46+!9+!. Even more extremely, outputting literal zeroes and ones, s!46+!! would save three bytes.

\$\endgroup\$
5
  • \$\begingroup\$ assuming an int is 64 bits wide - the vast majority of modern C implementations, including GCC for x86-64 on TIO, have 32-bit int. So your actual limit is n < 16, for 1<<2*_ to shift by less than the type-width (which is probably still fine). Only a very few C implementations on 64-bit machines used wide int, possibly Cray IIRC. Is there a currently used system with a C++ compiler where int is over 32 bits wide? (probably no) \$\endgroup\$ – Peter Cordes May 1 at 2:28
  • 1
    \$\begingroup\$ @PeterCordes You are correct. I revised my statement. \$\endgroup\$ – Jonathan Frech May 1 at 15:39
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech May 1 at 15:39
  • \$\begingroup\$ I'd expect a 128-bit system to still use 32-bit int, for many of the same reason compilers/ABIs didn't grow int past 32-bit on 64-bit machines (unix.org/version2/whatsnew/lp64_wp.html). A possible choice would be 32-bit int, 64-bit long, 128-bit long long, as a way to expose the useful type sizes. (And of course 281-bit pointers.) Although some systems always have long being at least pointer width, e.g. common for Linux. Anyway, I might say "else one may need an exotic C implementation, or 64-bit long instead of implicit-int." If the mere hint of code quality isn't taboo here :P \$\endgroup\$ – Peter Cordes May 1 at 15:49
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech May 18 at 18:03
5
\$\begingroup\$

05AB1E, 12 11 bytes

Returns a list of mazes where each maze is a list of 2×1 slices. 0's are walls.

T2ãIãʒ∊ü&PĀ

Try it online! Footer prints mazes horizontally.

Same idea as my APL answer, for each 2×2 submaze check if it is solvable (contains 11 in the top or bottom row).

Commented:

T            # push integer / string 10
 2ã          # all pairs of 1/0
   Iã        # all n-tuples of pairs of 1/0
             # each n-tuple represents a 2×n maze
     ʒ       # filter the mazes on:
      ∊      #   extend the maze by mirroring (for n=1)
       ü&    #   bitwise and of adjacent maze slices 
         PĀ  #   is the product not equal to 0?
\$\endgroup\$
4
\$\begingroup\$

Python 3, 91 83 bytes

Returns a list of lists of strings with characters . and x.

f=lambda n,*d:[[]][n:]or[w+[x]for x in{'.x','x.'}^{*d,'..'}for w in f(n-1,x[::-1])]

Try it online! The output is vertical.

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

JavaScript (Node.js), 78 bytes

f=n=>n?f(n-1).flatMap(a=>(g=eval(a+=`
`))%22?[a+22,a+g]:[a+12,a+21,a+22]):['']

Try it online!

2 as path, 1 as wall

JavaScript (Node.js), 88 bytes

f=n=>n?f(n-1).flatMap(a=>(g=a.slice(0,2),g%11?[11,g]:['01',10,11]).map(_=>_+`
`+a)):['']

Try it online!

1 as path, 0 as wall

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

Haskell, 66 bytes

(d%)
r%0=[[]]
r%n=[h:t|h<-max[d,"x.",".x"][r,d],t<-h%(n-1)]
d=".."

Try it online!

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

Charcoal, 39 bytes

NθEΦEX³θE◧⍘ι³θΣλ⬤ι⁻³∧μ⁺λ§ι⊖μE²⭆ι§.x⁼⊕λν

Try it online! Link is to verbose version of code. Explanation: Represents mazes internally as a list of digits, 0 = no walls, 1 = upper wall, 2 = lower wall. (3 would be an impossible maze, of course.)

Nθ                                      Input `N` as a number.
    EX³θ                                Map over potential mazes
        E◧⍘ι³θΣλ                         Split into lists of walls
   Φ                                     Filter over mazes where
                ⬤ι                      All columns satisfy
                  ⁻³∧μ⁺λ§ι⊖μ            Consecutive sums do not total 3
  E                                     Map over filtered mazes
                            E²          Map over each row
                              ⭆ι        Map over the maze and join
                                §.x⁼⊕λν Select wall or space
                                        Implicitly print
\$\endgroup\$
3
\$\begingroup\$

J, 43 bytes

[:(#~(0=&#.*&(2#.\0,]))/"2)-]\"#.2#:@i.@^+:

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ With base 3 to filter out # # for free and easily filter # ./. # with (3=+/): 38b \$\endgroup\$ – xash Apr 30 at 18:30
  • \$\begingroup\$ This looks great. I will update later after I have a chance to digest it. \$\endgroup\$ – Jonah Apr 30 at 19:24
3
\$\begingroup\$

Jelly, 11 bytes

4ṗ’Ḋ&ƝP$Ƈd2

A monadic Link accepting a positive integer that yields a list of lists of pairs where 0 represents a wall and 1 represents space.

Try it online!

How?

4ṗ’Ḋ&ƝP$Ƈd2 - Link: integer, n
4           - four
 ṗ          - ([1,2,3,4]) Cartesian power (n) -> all n-tuples made from alphabet [1,2,3,4]
  ’         - decrement -> all n-tuples made from alphabet [0,1,2,3] (first is all zeros)
   Ḋ        - dequeue (remove the first, to make the rest work when n=1)
        Ƈ   - filter keep those for which this is truthy (non zero):
       $    -   last two links as a monad - f(potential):
     Ɲ      -     for neighbours:
    &       -       bitwise AND
      P     -     product
         d2 - div-mod two (vectorises)
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 47 40 43 bytes

Assumes ⎕IO←0, 0's are walls.

-7 bytes inspired by this answer.
-4 bytes thanks to Razetime! (Commute to save on parenthesis, replicate first instead of replicate along the first axis /[0])

{(⌊/⌈/[1]2⌊/x,⌽x)⌿x←(2*2×⍵)2⍵⍴↑⍳2⍴⍨2×⍵}

Try it online!

⌊/⌈/[1]2⌊/x,⌽x is checking if a maze is solvable, everything else is just generating and filtering all mazes.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I suspect a translation of my J method would save you ~7 bytes or so, because usually equivalent APL is shorter than J. Which is not to say my J solution is optimal :) \$\endgroup\$ – Jonah Apr 30 at 16:26
  • 1
    \$\begingroup\$ @Jonah I don't know how your method works, but I got the size you suggested with a shorter way of generating all combinations of 1's and 0's. \$\endgroup\$ – ovs Apr 30 at 16:53
  • 1
    \$\begingroup\$ Simple -1 by commuting the first reshape from the right \$\endgroup\$ – Razetime May 1 at 16:05
  • 1
    \$\begingroup\$ 39 \$\endgroup\$ – Razetime May 3 at 4:09
3
+50
\$\begingroup\$

Vyxal, 109 84 bytes

\0⅛\1⅛\2⅛?(¾3n›e(¼_)ƛ0+⅛_nt0=[n›⅛n2+⅛|nt1=[n›⅛|n2+⅛]])ƛ\0`00
`øṙ\1`01
`øṙ\2`10
`øṙ;⁋

My first Vyxal answer, which is probably why it's so bad.

-25 bytes thanks to lyxal.

Try it Online!

\$\endgroup\$
3
  • \$\begingroup\$ 84 bytes \$\endgroup\$ – lyxal May 8 at 11:28
  • \$\begingroup\$ @lyxal See how bad I am? Also, can you post the backslash trick in the tips page? \$\endgroup\$ – A username May 8 at 11:29
  • \$\begingroup\$ 81 bytes \$\endgroup\$ – Aaron Miller May 10 at 17:20
2
\$\begingroup\$

Haskell, 80 bytes

f n=[m|m<-mapM(["..","x.",".x"]<$f)[1..n],all(<"xx").z(z max)m$tail m]
z=zipWith

Try it online!

Takes n as input, returns the list of all the \$2\times n\$ solvable mazes; each maze is represented as a list of list of characters, where . is an empty cell and x is a wall.

Haskell, 81 bytes

f 1=pure<$>g e
f n=[x:h:t|h:t<-f$n-1,x<-g h]
g".."=[e,"x.",".x"]
g s=[e,s]
e=".."

Try it online!

Recursive version.

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

JavaScript (V8), 101 bytes

Prints all solutions, with 0 = empty and 1 = wall.

n=>{for(i=q=1<<n;i--;)for(j=q;j--;)i&(j|j*2|j/2)||print((g=n=>n--?[i>>n&1]+[j>>n&1]+`
`+g(n):'')(n))}

Try it online!

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

Haskell, 75 bytes

A port of my Python answer.

(!"")
0!_=[[]]
n!d=[x:w|x<-"..":[w|w<-[".x","x."],w/=d],w<-(n-1)!reverse x]

Try it online!

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

Pip -P, 39 bytes

Y3**a[01t00]@^_MtNI_.RV_FI@>(_TB3)My+,y

Outputs each maze as a list of 2x1 slices, where 0 is a space and 1 is a wall. Try it online!

Here's a version with nicer output: Try it online!

Explanation

Observing that a slice with both walls (11) is no good, we try all combinations of slices 00, 01, and 10, with the further rule that 01 and 10 cannot be adjacent.

I tried using Cartesian product at first, but found that abusing base conversion was shorter.

Y3**a[01t00]@^_MtNI_.RV_FI@>(_TB3)My+,y
                                         a is command-line arg; t is 10 (implicit)
Y3**a                                    Yank 3 to the power of a into y variable
                                   y+,y  Range from y to 2*y
                                  M      For each number in that range:
                             _TB3         Convert to base 3
                          @>(    )        Remove the leading 1
                                         We now have a list of all strings of 0,1,2
                                         whose length equals the input number
                                         0 represents a slice with a wall in the
                                         lower half, 1 with a wall in the upper half,
                                         and 2 a slice with no walls.
                        FI               Filter that list on this function:
                t                         10
                 NI                       is not a substring of
                   _.RV_                  the string concatenated to its reverse
               M                         For each string in the remaining list:
             ^_                           Split it into digits
     [01t00]@                             and use each digit to index into the list
                                          [01;10;00]
\$\endgroup\$
0
\$\begingroup\$

Zsh -F, 57 bytes

eval for\ {1..$1}\ (01 10 00) 'grep -Ev "1 1|10 01"<<<$@'

Try it online!

Outputs as a space-separated list of pairs of characters, with 1 representing walls and 0 representing gaps.

  • for\ {1..$1}\ (01 10 00): construct the string for 1 (01 10 00) for 2 (01 10 00) for 3 (01 10 00) ... for n (01 10 00)
  • evaluate that string, which is n nested for-loops using the loop variables 1 to n, creating all the combinations of 01 10 00 (so all possible mazes)
  • <<<$@ - print all the variables numbered 1 to n separated by spaces
  • grep -Ev "1 1|10 01" - filter out combinations which match either 1 1 or 10 01 (i.e., diagonal walls)
\$\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.