11
\$\begingroup\$

You are an evil wizard, doing evil wizard business, when suddenly your crystal ball alerts you of a hero on their way to defeat you. To crush their hopes and dreams, you decide to trap the hero in a maze. You could just make a big maze but where would be the fun in that? Instead, you decide you want to make the maze as small as possible for a truly humiliating defeat. Thanks to your wizard skills, you know in advance how the hero will navigate the maze.

The hero's moves are represented by a list where each element can be one of "LR", "LS", "RL", "RS", "SL" or "SR". Inside the maze the hero moves forwards until they reach an intersection. Then the corresponding element in the list tells which direction the hero should continue. The hero first tries to move in the direction represented by the first letter, and next in the direction represented by the second letter. So for example, if the hero's moves are ["LS", "SR", "RS"], at the first intersection the hero will turn left. If that is not possible, they will go straight. Similarly in the second intersection, the hero will try to go straight, but if that's not possible, they will go right instead.

If the hero reaches a dead end or the beginning of the maze, they will just turn around. If there is a corner (the path just turns), then the hero will just follow the path. These interactions don't require any decisions, and therefore don't consume the decision list.

The hero gives up when they reach an intersection, but the decision list is consumed.

Rules

You are given the hero's move list as input and you have to output the maze as output. The maze begins at the upper left corner and ends at the lower right corner. The maze must be possible to traverse. You can use different values for "LR", etc, but please don't encode any extra information in the values, such as code. Output the maze as ascii art like this:

█ ████████
█    █   █
██ █ █ ███
██ ███   █
█      █ █
████████ █

You can also use different (distinct) characters for the wall and air. You can also return a two dimensional or flattened two dimensional list with two distinct values for wall and air (if you use a flattened list, please also return at least one of the dimensions to remove ambiguity). Since the outer border of a maze is always the same, you can return just the inner portion (also applies to ascii art output).

The maze cannot contain any areas accessible to the hero where the hallway is wider than one block. So for example:

Not Ok:

█ ███
█   █
█   █
███ █

Ok:

█ █
█ ████
█    █
████ █

The size of a maze is the area of it's rectangle bounding box. For example, the preceding maze has size 24.

You must output the smallest maze, where the hero gives up. In case of ties, any minimal solution is fine.

The input list has at least one element.

Test cases

["LR"]
-> 
█ ██
█  █
██ █
█  █
██ █
or
█ ██
█  █
█ ██
█  █
██ █
or
█ ███
█ █ █
█   █
███ █

["RL","RL","RS","LS","LR","RS","RS","SR","LR","RL"]
->
█ ███
█  ██
█ █ █
█   █
███ █

["LS", "LS", "LS", "LS", "LS", "LS", "LS", "LS", "LS", "LS", "LS", "LS"]
->
█ █████
█    ██
█ █ █ █
█  █  █
█ █ █ █
█     █
█████ █

["LR","RL","LS","LR","LS","LR","SR","SR","LR","SL","RL","SL","RS","RL","SR","LS","RS","SR","LS","SL","RS","SL","SR","SR","RS","RS","RS","RS","RL","LS","RS","RL","RL","SR","RL","RS","SL","RS","LS","RS","SR","SR","SR","RL","RL","SL","LR","LR","RS","RL","SR","SL","SR","RS","SR","RS","RS","RL","RL","RS"]
->
█ █████
█   █ █
█ █   █
█   █ █
█ ██  █
█████ █

["LR","RS","LR","RS","SR","RS","RS","LR","RS","SR","SR","SL","RS","LS","SR","SR","RL","RS","LS","LR","RS","RL","RL","RL","SL","SL","RL","RS","RS","RS","SL","SL","SR","RS","RS","LR","RS","RL","LR","RL","RS","SL","LR","RL","LR","SR","RS","LR","LR","RL","RS","SR","SR","LR","SR","SR","SL","RL","RS","LR","RS","RS","RS","LS","LS","RL","RL","SL","LS","LS","SL","RS","LS","RS","SL","LS","LS","RS","LS","LS","SL","SR","LS","RL","SL","LR","RS","RS","RS","RS","SL","LR","RL","RL","RS","SL","SR","RS","LR","RS","RS","LS","RS","LR","RS","SL","RS","LS","RS","SR","RL","RL","RL","LS","RS","RS","RS","LS","LS","SR"]
->
█ ████
█    █
█ █ ██
█    █
██ ███
█    █
██ █ █
████ █
\$\endgroup\$
12
  • 1
    \$\begingroup\$ EDIT: Nevermind, exit has to be lower right. Why is [1011, 1001, 1011] not a valid maze for ["LR"]? Hero will go left, hit dead end, turn around and face the intersection again \$\endgroup\$ Jan 25, 2022 at 21:56
  • 1
    \$\begingroup\$ For "LS"*n, is [1,0,1,1,1;1,0,0,0,1;1,0,1,0,1;1,0,0,0,1;1,1,1,0,1] valid? \$\endgroup\$
    – tsh
    Jan 26, 2022 at 2:25
  • 3
    \$\begingroup\$ @AnttiP I believe your second test example is incorrect, the hero escapes on the second 'RL' \$\endgroup\$
    – jezza_99
    Jan 26, 2022 at 21:21
  • 1
    \$\begingroup\$ Thank you @jezza_99, I've fixed it \$\endgroup\$
    – AnttiP
    Jan 27, 2022 at 14:39
  • 1
    \$\begingroup\$ I have really loved this challenge since I saw it in the sandbox. I'm saving this as a nomination for the best of 2022! \$\endgroup\$
    – ophact
    Jan 27, 2022 at 17:11

4 Answers 4

5
+50
\$\begingroup\$

Python 3.8 (pre-release), 1206 1095 1052 866 bytes

H=range
R=input().split()
s=0
while s:=s+1:
 B=[[*map(int,bin(2**s|k)[3:])]for k in H(2**s)]
 for a in H(2,s):
  for c in((b:=s//a)*a==s)*B:
   m=[[1,0,*[1]*a],*[[1,*c[a*n:a*-~n],1]for n in H(b)],[*[1]*a,0,1]];I=0;P=[0,1];D=[1,0]
   while[b,a]>=(P:=[P[0]+D[0],P[1]+D[1]])>[0for T in B if 1>T[-1]==T[0]and all(W or len([w for w in[i%a>a-2 or T[i+1],1>i%a or T[i-1],i+a>=len(T)or T[i+a],i<a or T[i-a]]if 1>w])==1+(len(T)-1>i>0)and 1>c[i]for i,W in enumerate(T))]>[1for c in H(a)for r in H(b)if 1>m[r+1][c+1]+m[r][c+1]+m[r][c]+m[r+1][c]]:
    A=[l for l in[[0,1],[1,0],[0,-1],[-1,0]]if 2+b>P[0]+l[0]>-1<P[1]+l[1]<a+2>1>m[P[0]+l[0]][P[1]+l[1]]!=[-l[0],-l[1]]!=D]
    if A[1:]:R[I:]or exit([print(*r,sep="")for r in m][0]);F,S=R[I];f=lambda Q:[D,[D[::-1],[-D[1],0]][D[1]],[[0,-D[0]],D[::-1]][D[1]]][ord(Q)%5%3];D=[f(S),Z:=f(F)][Z in A];I+=1
    else:D,*_=*A,[-D[0],-D[1]]

Try it online!

This version brute-forces every possible maze. The results don't match the test cases, but then again, the other answers don't match the test cases either.

Takes way too long to solve the third one, however.

More explanation

The code creates a variable called s which holds the size of the inner maze. At each iteration, we generate all binary strings of length s (where a 1 is wall and a 0 is air) using a trick to avoid having to use lengthy padding methods, and ensuring that it doesn't start with a 1 in order not to have to check for impossible entry into the maze.

We go through each width from 2 to s. If this width does not divide s, dismiss it. Otherwise, we generate the mazes with the wall/air determined by the binary string, and the width/height determined by this divisor. We dismiss the maze if it is not traversable (a maze is traversable if, out of the binary strings, you can find one in which the zeroes form a linear path from the beginning of the maze to the exit) or if there is a 2x2 block of zeroes within the maze (disallowed by the OP).

Then, we run a simulation of the maze. We initialize the directions, decision number, and position, and update the position accordingly at each iteration. If the exit is reached, we break out of the current loop and move on to the next binary string. Otherwise, we calculate the number of possible directions to go at an intersection (excluding the way we came, of course), and:

  • if there is no direction left (i.e. the hero hits a dead end), turn around, i.e. negate the direction;
  • if there is one direction left, simply go that way;
  • if there are two or more directions, we take the current decision. If there is no such decision, meaning we have consumed all decisions, that is victory and hence we break out of all loops. Otherwise, we try following the first choice of that decision, and if impossible, we follow the second choice (one or the other is guaranteed to work, as some simple mathematical reasoning will reveal). We then increment the decision number.

We increment the size of the maze once all factorizations and binary strings have been exhausted for that particular size.

Once we have found a good maze, we output it with a nice output format.

I insist on the nice input/output format.

Acknowledgements

Thanks to @AnttiP, the OP of this challenge, for golfing off an astonishing 186 bytes.

\$\endgroup\$
9
  • 2
    \$\begingroup\$ -111 bytes: Try it online \$\endgroup\$
    – AnttiP
    Jan 27, 2022 at 23:06
  • \$\begingroup\$ @AnttiP thanks, I will incorporate once I get access to a computer. Your comparisons are giving me a headache, though! :) \$\endgroup\$
    – ophact
    Jan 28, 2022 at 6:19
  • 2
    \$\begingroup\$ Further -75 bytes: Try it online. Biggest changes were turning B to a list of ints, and moving two if-conditionals to the while loops conditional. \$\endgroup\$
    – AnttiP
    Jan 28, 2022 at 14:42
  • \$\begingroup\$ Wow, you're good at this! \$\endgroup\$
    – ophact
    Jan 28, 2022 at 17:06
  • 1
    \$\begingroup\$ 797 bytes with f'{k:0{s}b}', 4-sum([...]) instead of len(w for w in[...]if 1>w) and splitting the pairs P, D and l into individual variables. \$\endgroup\$
    – ovs
    Jan 30, 2022 at 19:03
4
\$\begingroup\$

JavaScript (Node.js), 314 bytes

f=(x,n=8)=>(g=(s,i=n)=>s[n]?i>2?(h=x=>~n%i|M.some((_,b)=>(s[b+1]&s[b+i]&s[b-~i]|-~b%i<2|b<i^b>n-i^b==1^b==n-1)&s[b]|[...E.filter(j=>+s[j+P])[2]?x[R++]||[]:_].some(g=>+s[p=P+E[+g+W&3]]&&(P=p,W+=+g))&P>n-3,P=W=R=0,E=[1,i,-1,-i]))(M=[...(x+1).repeat(n)].fill('3012'))>h(x)?[s,i]:g(s,i-1):0:g(s+1)||g(s+0))``||f(x,n+1)

Try it online!

EDIT: Fixed a bug(not enough steps for LS RS RS ... RS LS LS), making it MORE slower

01000
01110
01010
01110
00010

Slow even for smallest input [], returning (same as 1st case)

0100
0110
0100
0110
0010

For the 2nd case f(['13','13','10','30','31','10','10','01','31','13']), output is

01000
01100
01010
01110
00010

not further tested

f=(x,n=8)=>(  // start from size=9, though startting from 10 also work
  g=(s,i=n)=> // recurse
    s[n]?     // otherwise g(s+1)||g(s+0)
      i>2?(   // width>=3
        h=(s,i,x)=>    // runable checker
          ~n%i|        // rectangle (n+1 is the size)
          [...s].some(
            (t,j)=>(   // no 2*2 road, border is correct. 1 if don't satisfy
              s[j+1]&s[j+i]&s[j-~i]|-~j%i<2|j<i^j>n-i^j==1^j==n-1
            )&t
          )||
          M.some(_=> // walk for enough time
              [...E.filter(j=>+s[j+P])[2]?x[R++]||[]:'0132'] // if branch then take instruction, otherwise try 3 forward then one back
              .some(g=>+s[p=P+E[+g+W&3]]&&(P=p,W+=+g))       // try walk
              &P>n-3,P=W=R=0,E=[1,i,-1,-i]                   // if at aim
          )          // it starts at (0,0) and go right, but can never go back to (0,0) since it's a wall
      )(s,i,M=[...s+s].fill('30')) // Using fact that '30'(LS)*inf always go for a possible maze to share code
      &&!h(s,i,x)?[s,i]:g(s,i-1)
  :0:g(s+1)||g(s+0))``||f(x,n+1)
\$\endgroup\$
1
  • \$\begingroup\$ @DialFrost I think this should be ~300 bytes for js/py but all submissions are >1k – l4m2 2 days ago \$\endgroup\$
    – l4m2
    Jan 30, 2022 at 2:57
3
\$\begingroup\$

Python3, 1651 bytes:

import copy,time
M=[(0,1),(0,-1),(1,0),(-1,0)]
R=range
E=enumerate
def v(m,n):
 for j,k in M:
  if(q:=n[0]+j)<0 or(w:=n[1]+k)<0:return 0
  try:
   m[q][w]
  except:return 0
 for q,l in E(m):
  for w,s in E(l):
   if not s:
    try:
     if not any([s,m[q][w+1],m[q+1][w],m[q+1][w+1]]):return 0
    except:1
 return 1
class H:
 def __init__(self):self.s={}
 def g(self,m,e,s):
  if e in s:
   yield(m,s);return
  for x,y in s:
   for j,k in M:
    if 0<(q:=x+j)<len(m)and 0<(w:=y+k)<len(m[0])and m[q][w]:
     B=copy.deepcopy(m)
     B[q][w]=0
     if (q,w)==e or v(B,(q,w)):
      if (q,w)not in self.s.get(tuple(sorted(s)),[]):
       self.s[tuple(sorted(s))]=self.s.get(tuple(sorted(s)),[])+[(q,w)]
       yield from self.g(B,e,s+[(q,w)])
T={0:{'L':((0,1),1),'R':((0,-1),2),'S':((1,0),0)},1:{'L':((-1,0),3),'R':((1,0),0),'S':((0,1),1)},2:{'L':((1,0),0),'R':((-1,0),3),'S':((0,-1),2)},3:{'L':((0,-1),2),'R':((0,1),1),'S':((-1,0),3)}}
U={0:3,3:0,1:2,2:1}
def r(d,c,w,e,s):
 if c==(0,1):d=0
 if c==e:return 0
 if not(m:=[(a,(x,y),D)for a,(q,D)in T[d].items()if(x:=q[0]+c[0],y:=q[1]+c[1])in w]):return r(U[d],c,w,e,s)
 if len(m)==1:return r(m[0][-1],m[0][1],w,e,s)
 if not s:return 1
 W={a:(c,b)for a,b,c in m}
 return r(*W.get(s[0][0],W.get(s[0][1])),w,e,s[1:])
def S(s):
 L=set()
 P=max(4,len(set(s)))
 k=P+1
 while k:
  for i in R(P,k):
   for j in R(P,k):
    if (i,j)not in L:
      L.add((i,j))   
      b=[[1 for _ in R(j)]for _ in R(i)]
      b[0][1]=0
      t=time.time()
      for G,W in H().g(b,(i-1,j-2),[(0,1)]):
       if time.time()-t>5:break
       yield(G,W,(i-1,j-2))
  k+=1
def f(s):
 for G,W,e in S(s):
  if r(0,(0,1),W,e,s):return G

Try it online!

Produces the correct mazes for all the test cases in under 60 seconds.

\$\endgroup\$
2
  • \$\begingroup\$ this is the most optimized one by far so you easily can get the bounty ajax! (hopefully this can be golfed further) \$\endgroup\$
    – DialFrost
    Jan 28, 2022 at 14:07
  • \$\begingroup\$ @DialFrost Thank you, I would appreciate any golfing suggestions. \$\endgroup\$
    – Ajax1234
    Jan 28, 2022 at 14:29
3
\$\begingroup\$

Python 3, 2̶9̶3̶1̶ 1765 bytes

It's long, it's ugly, but it works (and for an infinite maze size). Brute force method, and it takes quite a while to run all test cases (took me ~15 minutes). Big thanks to @ThisFieldIsRequired and @12944qwerty for helping me shave it down.

def f(a):
    from pathfinding.core.grid import Grid
    from pathfinding.finder.a_star import AStarFinder as A
    c=[]
    r=None
    x,y=4,4
    while 1:
        z=x-2
        v=y-2
        e=(x-2)*(y-2)
        if c and x*y>=r:pass
        else:
            for i in range(2**e, int(''.join([t for u in [['1']+['0']*(v-1) for t in range(z)] for t in u]),2),-1):
                o=list(a)
                p=list(map(int, format(i,'b').rjust(e,'0')))
                b=[p[(i*z-z):i*z] for i in range(1,v+1)]
                if 0 in [b[0][0],b[-1][-1]]:continue
                g=Grid(matrix=b)
                s=g.node(0,0)
                d=g.node(z-1,v-1)
                h=A(diagonal_movement=2)
                P,R=h.find_path(s,d,g)
                if len(P)==0:continue
                B=0
                for k in range(v-1):
                    for l in range(z-1):
                        q = [b[k][l],b[k+1][l],b[k][l+1],b[k+1][l+1]]
                        if 0 not in q:B=1;break
                    if B:break
                if B:continue
                b=[[0]+l+[0] for l in b]
                b.insert(0, [0 for f in range(x)])
                b.append([0 for f in range(x)])
                b[0][1],b[-1][-2]=1,1
                L=[[1,1],[0,1]]
                d=[y-1,z]
                o.reverse()
                while 1:
                    if [L[0][0], L[0][1]]==d:break
                    U=[L[0][0]-1,L[0][1]]
                    U.append(b[U[0]][U[1]])
                    D=[L[0][0]+1,L[0][1]]
                    D.append(b[D[0]][D[1]])
                    S=[L[0][0],L[0][1]-1]
                    S.append(b[S[0]][S[1]])
                    R=[L[0][0],L[0][1]+1]
                    R.append(b[R[0]][R[1]])
                    Q=[U, D, S, R]
                    O=sum([U[2],D[2],S[2],R[2]])
                    if O==1:L[0],L[1]=L[1],L[0];continue
                    elif O==2:
                        for C in Q:
                            if [C[0],C[1]] == L[1]:continue
                            elif C[2] == 1:L=[[C[0],C[1]],L[0]];break
                        continue
                    else:
                        try:
                            I=o.pop()
                        except IndexError:
                            c=b
                            r=x*y
                            B=1
                            break
                        Y=[q-w for q,w in zip(L[0],L[1])]
                        for m in I:
                            if m=="L":T=[-Y[1],Y[0]]
                            elif m=="R":T=[Y[1],-Y[0]]
                            else:T=Y
                            N=[[q+w for q,w in zip(L[0],T)],L[0]]
                            if b[N[0][0]][N[0][1]]:L=N;break
                if B:break
        if x!=y and x<y:x,y=y,x
        elif x!=y and x>y:x,y=y,x;continue
        if x==y:x+=1;y=4
        else:y+=1
        if c and r<=x*4:break
    return c

Try it online!

Outputs:

['LR'] 
->
█ ███
█ █ █
█   █
███ █
Score is: 20

['LR', 'RS', 'SR', 'LS', 'RL', 'SL', 'SL', 'RL', 'RL', 'LR', 'RL', 'RL', 'LS'] 
->
█ ██
█  █
█ ██
█  █
█ ██
█  █
██ █
Score is: 28

['LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS', 'LS'] 
->
█ █████
█    ██
█ █ █ █
█  █  █
█ █ █ █
█     █
█████ █
Score is: 49

['LR', 'RL', 'LS', 'LR', 'LS', 'LR', 'SR', 'SR', 'LR', 'SL', 'RL', 'SL', 'RS', 'RL', 'SR', 'LS', 'RS', 'SR', 'LS', 'SL', 'RS', 'SL', 'SR', 'SR', 'RS', 'RS', 'RS', 'RS', 'RL', 'LS', 'RS', 'RL', 'RL', 'SR', 'RL', 'RS', 'SL', 'RS', 'LS', 'RS', 'SR', 'SR', 'SR', 'RL', 'RL', 'SL', 'LR', 'LR', 'RS', 'RL', 'SR', 'SL', 'SR', 'RS', 'SR', 'RS', 'RS', 'RL', 'RL', 'RS'] 
->
█ █████
█   █ █
█ █   █
█   █ █
█ ██  █
█████ █
Score is: 42

['LR', 'RS', 'LR', 'RS', 'SR', 'RS', 'RS', 'LR', 'RS', 'SR', 'SR', 'SL', 'RS', 'LS', 'SR', 'SR', 'RL', 'RS', 'LS', 'LR', 'RS', 'RL', 'RL', 'RL', 'SL', 'SL', 'RL', 'RS', 'RS', 'RS', 'SL', 'SL', 'SR', 'RS', 'RS', 'LR', 'RS', 'RL', 'LR', 'RL', 'RS', 'SL', 'LR', 'RL', 'LR', 'SR', 'RS', 'LR', 'LR', 'RL', 'RS', 'SR', 'SR', 'LR', 'SR', 'SR', 'SL', 'RL', 'RS', 'LR', 'RS', 'RS', 'RS', 'LS', 'LS', 'RL', 'RL', 'SL', 'LS', 'LS', 'SL', 'RS', 'LS', 'RS', 'SL', 'LS', 'LS', 'RS', 'LS', 'LS', 'SL', 'SR', 'LS', 'RL', 'SL', 'LR', 'RS', 'RS', 'RS', 'RS', 'SL', 'LR', 'RL', 'RL', 'RS', 'SL', 'SR', 'RS', 'LR', 'RS', 'RS', 'LS', 'RS', 'LR', 'RS', 'SL', 'RS', 'LS', 'RS', 'SR', 'RL', 'RL', 'RL', 'LS', 'RS', 'RS', 'RS', 'LS', 'LS', 'SR'] 
->
█ ████
█    █
█ █ ██
█    █
██ ███
█    █
██ █ █
████ █
Score is: 48
\$\endgroup\$
4
  • \$\begingroup\$ You can save many bytes by converting those 4-space indents to 1-space indents or tabs. o.reverse() can be o=o[::-1]. You can separate some statements by semicolons rather than newlines which saves some bytes in the deeper parts of the code. You can also remove spaces in statements (such as in x = 1), and remove spaces between numbers and keywords. \$\endgroup\$
    – ophact
    Jan 27, 2022 at 12:43
  • \$\begingroup\$ @ThisFieldIsRequired cheers for the tips, will see how low I can get it \$\endgroup\$
    – jezza_99
    Jan 27, 2022 at 18:31
  • 1
    \$\begingroup\$ No problem. Having tried golfing it myself, the tips above can save at least 1000 bytes. \$\endgroup\$
    – ophact
    Jan 27, 2022 at 19:05
  • 1
    \$\begingroup\$ Reducing whitespace and used ;, switching reverse, replaced append with +=, Replaced IndexError with Exception (-1 byte), using function assignment, etc. For some reason -~x made it impossibly slow. Got it down to 1765 bytes Take a look if you want. (it is a bit slower because python) \$\endgroup\$ Jan 28, 2022 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.