Trap the hero in a maze

Question

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"]
->
█ ████
█    █
█ █ ██
█    █
██ ███
█    █
██ █ █
████ █

Answer 1

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.

Answer 2

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)

Answer 3

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.

Answer 4

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