Design and Solve a Maze [on hold while sandboxing]

Question

Your task is to play the roles of both characters in this scene from Inception. In it, Cobb gives Ariadne a challenge:

You have two minutes to design a maze that takes one minute to solve.

Some liberties will be taken on that description. Most importantly, this challenge is not time-based, rather scores are based on the effectiveness of your mazes and maze-solvers.

I apologize for the many edits to this challenge as we iterate towards an easy and fair format..

Part I: Maze format

All mazes are square. A cell in the maze is represented as a zero-indexed tuple row column.

Walls are represented by two binary strings: one for horizontal walls (which block movement between rows) and vertical walls (vice versa). On an NxN maze, there are Nx(N-1) possible walls of each type. Let's take a 3x3 example where the cells are labelled:

A   B | C
   ---
D | E   F
   ---
G   H | I

all possible vertical walls are: AB BC DE EF GH HI. Translated into a string, the walls shown are 011001 for vertical walls and 010010 for horizontal walls. Also, by "binary string" I mean "the characters '0' and '1'".

The full maze format is a string which contains, in this order:

• width
• start cell tuple
• end cell tuple
• horizontal walls
• vertical walls

For example, this maze:

   0 1 2 3 4
   _________
0 | |  E|  _|
1 |  _|_|_  |
2 |_ _ _  | |
3 |  _ _  | |
4 |____S|___|
start:(4,2)
end:(0,2)

is formatted to this:

5
4 2
0 2
00001011101110001100
10100110000100010010

Part II: The Architect

The Architect program creates the maze. It must play by the rules and provide a valid maze (one where a solution exists, and the end is not on top of the start).

Input: Two positive integers:

size [random seed]

Where size will be in [15, 50]. You are encouraged to make use of the random seed so that matches can be replayed, although it is not required.

Output: A valid size x size (square) maze using the format described in Part I. "valid" means that a solution exists, and the start cell is not equal to the end cell.

The score of an Architect on a given maze is

   # steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))

So architects are rewarded for complex mazes, but penalized for each wall built (this is a substitute for Ariadne's time restriction). The dist() function ensures that a maze with no walls does not get an infinite score. The outside borders of the maze do not contribute to the wall count.

Part III: The Solver

The Solver attempts to solve mazes generated by others' architects. There is a sort of fog-of-war: only walls adjacent to visited cells are included (all others are replaced with '?')

input: the same maze format, but with '?' where walls are unknown, an extra line for the current location, and a comma-separated list of valid choices from this location. (This is a big edit that is meant to make it simpler to write a maze-parsing function)

example (same as the above 5x5 maze after taking one step left)

5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2

Which corresponds something like this, where ? is fog:

   0 1 2 3 4
   _________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|

output: One of the tuples from the list of valid choices

Each Solver's score is the inverse of the Architect's score.

Part IV: King of the Hill

Architects and Solvers are given separate scores, so there could potentially be two winners.

Each pair of architects and solvers will have many chances to outwit each other. Scores will be averaged over all tests and opponents. Contrary to code golf conventions, highest average score wins!

I intend for this to be ongoing, but I can't guarantee continued testing forever! Let's say for now that a winner will be declared in one week.

Part V: Submitting

• I maintain veto power over all submissions - cleverness is encouraged, but not if it breaks the competition or my computer! (If I can't tell what your code does, I will probably veto it)
• Come up with a name for your Architect/Solver pair. Post your code along with instructions on how to run it.

Coming soon: an updated python test kit for the new format. Big changes happened to allow any language submissions.

Answer 1

BuildFun and SolveFun

Well, this took quite a while and I'm not entirely sure if the solver is cheating or not. While it has access to the entire maze all of the time, it only looks at the cell it's in, the walls surrounding it and, if there isn't a wall between them, the cells adjacent to it. If this is against the rules please let me know and I'll try to change it.

Anyway, here's the code:

#Architect function
def BuildFun(size,seed):
   #Initialise grid and ensure inputs are valid
   if size<15:size=15
   if size>50:size=50
   if seed<4:seed=4
   if seed>size:seed=size
   grid=[]
   for x in range(size):
      gridbuilder=[]
      for y in range(size):gridbuilder.append([0,1,1])
      grid.append(gridbuilder)
   coords=[0,0]
   grid[0][0][0]=1
   #Generate maze
   while 1:
      #Choose a preffered direction based on location in grid and seed
      pref=((((coords[0]+coords[1]+2)*int(size/2))%seed)+(seed%(abs(coords[0]-coords[1])+1)))%4
      #Find legal moves
      opt=[]
      if coords[0]>0:opt+=[0] if grid[coords[0]-1][coords[1]][0]==0 else []
      if coords[1]<size-1:opt+=[1] if grid[coords[0]][coords[1]+1][0]==0 else []
      if coords[0]<size-1:opt+=[2] if grid[coords[0]+1][coords[1]][0]==0 else []
      if coords[1]>0:opt+=[3] if grid[coords[0]][coords[1]-1][0]==0 else []
      #There are legal moves
      if len(opt)>0:
         moved=False
         while not moved:
            #Try to move in preffered direction
            if pref in opt:
               if pref==0:
                  coords[0]-=1
                  grid[coords[0]][coords[1]][0]=1
                  grid[coords[0]][coords[1]][2]=0
               elif pref==1:
                  grid[coords[0]][coords[1]][1]=0
                  coords[1]+=1
                  grid[coords[0]][coords[1]][0]=1
               elif pref==2:
                  grid[coords[0]][coords[1]][2]=0
                  coords[0]+=1
                  grid[coords[0]][coords[1]][0]=1
               else:
                  coords[1]-=1
                  grid[coords[0]][coords[1]][0]=1
                  grid[coords[0]][coords[1]][1]=0
               moved=True
            #Change preferred direction if unable to move
            else:
               pref+=1
               if pref==4:pref=0
      #There aren't legal moves
      else:
         moved=False
         #Return to a previously visited location
         if not moved:
            try:
               if grid[coords[0]-1][coords[1]][0]==1 and grid[coords[0]-1][coords[1]][2]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[0]-=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]][coords[1]+1][0]==1 and grid[coords[0]][coords[1]][1]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[1]+=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]+1][coords[1]][0]==1 and grid[coords[0]][coords[1]][2]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[0]+=1
                  moved=True
            except:pass
         if not moved:
            try:
               if grid[coords[0]][coords[1]-1][0]==1 and grid[coords[0]][coords[1]-1][1]==0:
                  grid[coords[0]][coords[1]][0]=2
                  coords[1]-=1
                  moved=True
            except:pass
      #Check if finished
      fin=True
      for x in grid:
         for y in x:
            if y[0]==0:
               fin=False
               break
         if not fin:break
      if fin:break
   for x in grid:
      for y in x:
         y[0]=0
   #Find positions for start and finish such that the route between them is as long as possible
   lsf=[[0,0],[0,0],0]
   for y in range(size):
      for x in range(size):
         #Check all start positions
         lengths=[]
         coords=[[y,x,4,0]]
         while len(coords)>0:
            #Spread tracers out from start to the rest of the maze
            for coord in coords:
               opt=[]
               if coord[0]>0:opt+=[0] if grid[coord[0]-1][coord[1]][2]==0 else []
               opt+=[1] if grid[coord[0]][coord[1]][1]==0 else []
               opt+=[2] if grid[coord[0]][coord[1]][2]==0 else []
               if coord[1]>0:opt+=[3] if grid[coord[0]][coord[1]-1][1]==0 else []
               try:opt.remove(coord[2])
               except:pass
               #Dead end, tracer dies and possible end point is recorded along with length
               if len(opt)==0:
                  lengths.append([coord[0],coord[1],coord[3]])
                  coords.remove(coord)
               else:
                  #Create more tracers at branch points
                  while len(opt)>1:
                     if opt[0]==0:coords.append([coord[0]-1,coord[1],2,coord[3]+1])
                     elif opt[0]==1:coords.append([coord[0],coord[1]+1,3,coord[3]+1])
                     elif opt[0]==2:coords.append([coord[0]+1,coord[1],0,coord[3]+1])
                     else:coords.append([coord[0],coord[1]-1,1,coord[3]+1])
                     del opt[0]
                  if opt[0]==0:
                     coord[0]-=1
                     coord[2]=2
                     coord[3]+=1
                  elif opt[0]==1:
                     coord[1]+=1
                     coord[2]=3
                     coord[3]+=1
                  elif opt[0]==2:
                     coord[0]+=1
                     coord[2]=0
                     coord[3]+=1
                  else:
                     coord[1]-=1
                     coord[2]=1
                     coord[3]+=1
         #Find furthest distance and, if it's longer than the previous one, the start/end positions get updated
         lengths=sorted(lengths,key=lambda x:x[2],reverse=True)
         if lengths[0][2]>lsf[2]:lsf=[[y,x],[lengths[0][0],lengths[0][1]],lengths[0][2]]
   #Find number of walls and output maze
   w=draw(grid,size,lsf[0],lsf[1])
   #Output maze information
   print('Start = '+str(lsf[0]))
   print('End = '+str(lsf[1]))
   print('Distance = '+str(lsf[2]))
   print('Walls = '+str(w))
   print('Score = '+str(float(lsf[2])/float(w))[:5])
   #Convert array grid to binary strings horizontal and vertical
   horizontal=vertical=''
   for y in range(size):
      for x in range(size-1):vertical+=str(grid[y][x][1])
   for y in range(size-1):
      for x in range(size):horizontal+=str(grid[y][x][2])
   #Save maze information to text file for use with SolveFun
   save=open('Maze.txt','w')
   save.write(str(size)+'\n'+str(lsf[0][0])+' '+str(lsf[0][1])+'\n'+str(lsf[1][0])+' '+str(lsf[1][1])+'\n'+horizontal+'\n'+vertical)
   save.close()
#Solver function
def SolveFun():
   try:
      #Get maze information from text file
      save=open('Maze.txt','r')
      data=save.readlines()
      save.close()
      size=int(data[0])
      s=data[1].rsplit(' ')
      start=[int(s[0]),int(s[1])]
      e=data[2].rsplit(' ')
      end=[int(e[0]),int(e[1])]
      horizontal=data[3].rstrip('\n')
      vertical=data[4]
      #Build maze from information
      grid=[]
      for y in range(size):
         grid.append([])
         for x in range(size):
            grid[y].append([0,1,1])
      for y in range(size):
         for x in range(size-1):
            grid[y][x][1]=int(vertical[y*(size-1)+x])
      for y in range(size-1):
          for x in range(size):
            grid[y][x][2]=int(horizontal[y*size+x])
      path=''
      cpath=''
      bs=0
      pos=start[:]
      grid[pos[0]][pos[1]][0]=1
      while pos!=end:
         #Want to move in direction of finish
         if end[0]<pos[0] and pos[0]-end[0]>=abs(pos[1]-end[1]):pref=0
         elif end[1]>pos[1] and end[1]-pos[1]>=abs(pos[0]-end[0]):pref=1
         elif end[0]>pos[0] and end[0]-pos[0]>=abs(pos[1]-end[1]):pref=2
         else:pref=3
         #Find legal moves
         opt=[]
         if pos[0]>0:
            if grid[pos[0]-1][pos[1]][2]==0:opt+=[0]if grid[pos[0]-1][pos[1]][0]==0 else[]
         if pos[1]>0:
            if grid[pos[0]][pos[1]-1][1]==0:opt+=[3]if grid[pos[0]][pos[1]-1][0]==0 else[]
         if grid[pos[0]][pos[1]][2]==0:opt+=[2]if grid[pos[0]+1][pos[1]][0]==0 else[]
         if grid[pos[0]][pos[1]][1]==0:opt+=[1]if grid[pos[0]][pos[1]+1][0]==0 else[]
         if len(opt)>0:
            moved=False
            while not moved:
               #Try to move in preferred direction
               if pref in opt:
                  if pref==0:
                     pos[0]-=1
                     path+='0'
                     cpath+='0'
                  elif pref==1:
                     pos[1]+=1
                     path+='1'
                     cpath+='1'
                  elif pref==2:
                     pos[0]+=1
                     path+='2'
                     cpath+='2'
                  else:
                     pos[1]-=1
                     path+='3'
                     cpath+='3'
                  grid[pos[0]][pos[1]][0]=1
                  moved=True
               #Change preferred direction by 1
               else:
                  pref=(pref+1)%4
         #No legal moves, backtrack
         else:
            bs+=1
            grid[pos[0]][pos[1]][0]=2
            if int(cpath[len(cpath)-1])==0:
               pos[0]+=1
               path+='2'
            elif int(cpath[len(cpath)-1])==1:
               pos[1]-=1
               path+='3'
            elif int(cpath[len(cpath)-1])==2:
               pos[0]-=1
               path+='0'
            else:
               pos[1]+=1
               path+='1'
            cpath=cpath[:len(cpath)-1]
      #Output maze with solution as well as total steps and wasted steps
      draw(grid,size,start,end)
      print('\nPath taken:')
      print(str(len(path))+' steps')
      print(str(bs)+' backsteps')
      print(str(bs*2)+' wasted steps')
   except:print('Could not find maze')
def draw(grid,size,start,end):
   #Build output in string d
   d='   '
   for x in range(size):d+=' '+str(x)[0]
   d+='\n   '
   for x in range(size):d+='  ' if len(str(x))==1 else ' '+str(x)[1]
   d+='\n    '+'_'*(size*2-1)
   w=0
   for y in range(size):
      d+='\n'+str(y)+'  |' if len(str(y))==1 else '\n'+str(y)+' |'
      for x in range(size):
         if grid[y][x][2]:
            if start==[y,x]:d+=UL.S+'S'+UL.E
            elif end==[y,x]:d+=UL.S+'F'+UL.E
            elif grid[y][x][0]==1:d+=UL.S+'*'+UL.E
            else:d+='_'
            w+=1
         else:
            if start==[y,x]:d+='S'
            elif end==[y,x]:d+='F'
            elif grid[y][x][0]==1:d+='*'
            else:d+=' '
         if grid[y][x][1]:
            d+='|'
            w+=1
         else:d+=' '
   #Output maze and return number of walls
   print(d)
   w-=size*2
   return w
#Underlines text
class UL:
   S = '\033[4m'
   E = '\033[0m'

I realise that this is ridiculously long and not particularly easy to read, but I'm lazy so this is how it's staying.

BuildFun

The architect, BuildFun, is a fairly simple maze generating program that will always create a 'perfect' maze (one with no loops and where any two points will always have exactly one path between them). It bases its logic off of the seed input meaning that the mazes generated are pseudo-random with what often appear to be repeating patterns and, with the same seed and size, the same maze will be created.

Once the maze is generated, the program will attempt to maximise the maze's score by searching for the start point and end point that result in the longest path between them. To do this, it runs through every start point, spreads out tracers to find the end point furthest from it, and picks the combination with the longest path.

After this, it draws the maze, counts the walls and outputs the maze's information. This is the start point, end point, distance between them, number of walls and score. It also formats this information into the style described above for size, start and end, horizontal walls and vertical walls and saves this into a text file called Maze.txt for use later.

SolveFun

The solver, SolveFun, uses the text file Maze.txt as the input and works in a very similar way to the architect. For every move, it will choose a direction that it wants to go based on its relative position to the end and then it will look at the walls surrounding it. If a wall is not there, it will check to see if it has been in the cell adjacent to it and, if not, it will be added as possible option. It will then move in the direction closest to its preferred direction provided it has options. If it doesn't have options, it will backtrack until it does. This continues until it reaches the end.

As it moves, it records the path it is taking in the variable path which is used at the end to output the total number of steps. It also records the amount of times it had to backtrack used to calculate wasted steps at the end. When it reaches the end, it will output the maze with the shortest path from start to end marked on with *s.

How to Run

Due to the method of outputting the maze (which includes underlining certain characters), this has to be run from a command line in the form

python -c 'import filename;filename.BuildFun(Size, Seed)'

and

python -c 'import filename;filename.SolveFun()'

where Size is an integer between 15 and 50 (inclusive) and Seed is an integer between 4 and Size (inclusive).