Ваша задача - сыграть роли обоих персонажей в этой сцене с самого начала. В этом Кобб бросает вызов Ариадне:

У вас есть две минуты, чтобы создать лабиринт, который занимает одну минуту, чтобы решить.

Некоторые свободы будут приняты в этом описании. Самое главное, что эта задача не основана на времени, скорее оценки основаны на эффективности ваших лабиринтов и решателей лабиринтов.

Я прошу прощения за многочисленные правки этой проблемы, поскольку мы переходим к простому и честному формату.

Часть I: формат лабиринта

Все лабиринты квадратные. Ячейка в лабиринте представлена ​​в виде кортежа с нулевым индексом row column.

Стены представлены двумя бинарными строками: одна для горизонтальных стен (которые блокируют движение между рядами) и вертикальные стены (наоборот). На NxNлабиринте есть Nx(N-1)возможные стены каждого типа. Давайте возьмем пример 3x3, где ячейки помечены:

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

все возможные вертикальные стенки являются: AB BC DE EF GH HI. В переводе на строку, стены указаны 011001для вертикальных стен и 010010для горизонтальных стенок. Также под «двоичной строкой» я подразумеваю «символы« 0 »и« 1 »».

Полный формат лабиринта представляет собой строку, которая содержит в следующем порядке:

• ширина
• начать кортеж клетки
• кортеж конечных клеток
• горизонтальные стены
• вертикальные стены

Например, этот лабиринт:

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

отформатирован к этому:

5
4 2
0 2
00001011101110001100
10100110000100010010

Часть II: Архитектор

Программа Architect создает лабиринт. Он должен играть по правилам и предоставлять действительный лабиринт (тот, где решение существует, и конец не находится сверху начала).

Входные данные: два натуральных числа:

size [random seed]

Где sizeбудет [15, 50]. Рекомендуется использовать случайное начальное число, чтобы совпадения можно было воспроизвести, хотя это и не требуется.

Вывод: действительный лабиринт размера x (квадратный), использующий формат, описанный в части I. «Действительный» означает, что решение существует, и начальная ячейка не равна конечной ячейке.

Оценка Архитектора в данном лабиринте

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

Таким образом, архитекторы получают вознаграждение за сложные лабиринты, но наказываются за каждую построенную стену (это заменяет ограничение времени Ариадны). В dist()функции гарантирует , что лабиринт без стен не получить бесконечный счет. Внешние границы лабиринта не влияют на количество стен.

Часть III: Решатель

Решатель пытается решить лабиринты, созданные другими архитекторами. Существует своего рода туман войны: включены только стены, прилегающие к посещенным клеткам (все остальные заменены на «?»)

вход: тот же формат лабиринта, но с '?' где стены неизвестны, дополнительная строка для текущего местоположения и разделенный запятыми список допустимых вариантов из этого местоположения. (Это большое редактирование, предназначенное для упрощения написания функции разбора лабиринта)

пример (такой же, как и в предыдущем лабиринте 5х5 после выполнения шага влево)

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

Что соответствует примерно так, где ?туман

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

вывод: один из кортежей из списка допустимых вариантов

Оценка каждого Солвера является обратной к оценке Архитектора.

Часть IV: Король горы

Архитекторы и Солверы получают отдельные оценки, поэтому потенциально может быть два победителя.

У каждой пары архитекторов и решателей будет много шансов перехитрить друг друга. Результаты будут усреднены по всем тестам и оппонентам. Вопреки правилам игры в гольф, выигрывает самый высокий средний балл!

Я намерен, чтобы это продолжалось, но я не могу гарантировать, что тестирование будет продолжаться вечно! Скажем пока, что победитель будет объявлен через неделю.

Часть V: Отправка

• Я сохраняю право вето на все представленные материалы - это поощряет ум, но не в том случае, если это нарушает конкуренцию или мой компьютер! (Если я не могу сказать, что делает ваш код, я, вероятно, наложу вето на него)
• Придумайте имя для вашей пары Архитектор / Солвер. Разместите свой код вместе с инструкциями по его запуску.

Скоро: обновленный набор тестов Python для нового формата. Большие изменения произошли, чтобы позволить любые языковые представления.

BuildFun и SolveFun

Ну, это заняло довольно много времени, и я не совсем уверен, обманщик решает или нет. Хотя у него есть доступ ко всему лабиринту все время, он только смотрит на ячейку, в которой он находится, на стены, окружающие его, и, если между ними нет стены, на соседние с ней клетки. Если это противоречит правилам, пожалуйста, дайте мне знать, и я постараюсь изменить это.

Во всяком случае, вот код:

#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'

Я понимаю, что это смехотворно долго и не особенно легко для чтения, но я ленив, так что это так.

BuildFun

Архитектор BuildFun - это довольно простая программа, генерирующая лабиринт, которая всегда будет создавать «идеальный» лабиринт (один без петель, где любые две точки всегда будут иметь ровно один путь между ними). Он основывает свою логику на исходном входе, что означает, что сгенерированные лабиринты являются псевдослучайными с часто повторяющимися образцами, и при одинаковом начальном значении и размере будет создан тот же лабиринт.

После того, как лабиринт создан, программа попытается максимизировать оценку лабиринта путем поиска начальной и конечной точек, которые приводят к самому длинному пути между ними. Для этого он проходит через каждую начальную точку, распределяет трассеры, чтобы найти конечную точку, наиболее удаленную от нее, и выбирает комбинацию с самым длинным путем.

После этого он рисует лабиринт, считает стены и выводит информацию лабиринта. Это начальная точка, конечная точка, расстояние между ними, количество стен и оценка. Он также форматирует эту информацию в описанном выше стиле для размера, начала и конца, горизонтальных и вертикальных стен и сохраняет ее в текстовом файле с именем Maze.txt для последующего использования.

SolveFun

Решатель SolveFun использует текстовый файл Maze.txt в качестве входных данных и работает очень похоже на архитектуру. Для каждого движения он будет выбирать направление, в котором он хочет идти, основываясь на его относительном положении до конца, а затем он будет смотреть на окружающие его стены. Если стены там нет, она проверит, находилась ли она в соседней с ней ячейке, и если нет, то будет добавлена ​​в качестве возможного варианта. Затем он будет двигаться в направлении, наиболее близком к предпочтительному, при условии, что у него есть опции. Если у него нет опций, он будет возвращаться, пока не получит. Это продолжается, пока не достигнет конца.

По мере движения он записывает путь, по которому он идет, в переменном пути, который используется в конце для вывода общего количества шагов. Он также записывает, сколько раз ему пришлось возвращаться назад, чтобы вычислить потерянные шаги в конце. Когда он достигнет конца, он выведет лабиринт с кратчайшим путем от начала до конца, отмеченным символом *s.

Как запустить

Из-за метода вывода лабиринта (который включает в себя подчеркивание определенных символов), это должно быть запущено из командной строки в форме

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

и

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

где Size - целое число от 15 до 50 (включительно), а Seed - целое число от 4 до размера (включительно).