Twoim zadaniem jest odgrywanie ról obu postaci w tej scenie od początku. Cobb daje Ariadnie wyzwanie:

Masz dwie minuty na zaprojektowanie labiryntu, którego rozwiązanie zajmuje jedną minutę.

Niektóre wolności zostaną uwzględnione w tym opisie. Co najważniejsze, to wyzwanie nie jest oparte na czasie, a wyniki oparte są na skuteczności twoich labiryntów i rozwiązujących labirynt.

Przepraszam za wiele zmian tego wyzwania, gdy przechodzimy do łatwego i sprawiedliwego formatu.

Część I: Format labiryntu

Wszystkie labirynty są kwadratowe. Komórka w labiryncie jest reprezentowana jako krotka o zerowym indeksie row column.

Ściany są reprezentowane przez dwa ciągi binarne: jeden dla ścian poziomych (które blokują ruch między rzędami) i ścian pionowych (odwrotnie). W NxNlabiryncie są Nx(N-1)możliwe ściany każdego typu. Weźmy przykład 3x3, w którym komórki są oznaczone:

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

wszystkie możliwe pionowe ściany są: AB BC DE EF GH HI. Przełożone na sznurek ściany pokazane są 011001dla ścian pionowych i 010010dla ścian poziomych. Również przez „ciąg binarny” rozumiem „znaki” 0 i „1”.

Pełny format labiryntu to ciąg znaków, który zawiera w następującej kolejności:

• szerokość
• rozpocznij krotkę komórki
• krotka końcowa komórki
• poziome ściany
• pionowe ściany

Na przykład ten labirynt:

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

jest sformatowany do tego:

5
4 2
0 2
00001011101110001100
10100110000100010010

Część II: Architekt

Program Architekt tworzy labirynt. Musi grać zgodnie z zasadami i zapewniać prawidłowy labirynt (taki, w którym istnieje rozwiązanie, a końca nie ma na początku).

Dane wejściowe: dwie dodatnie liczby całkowite:

size [random seed]

Gdzie sizebędzie [15, 50]. Zachęcamy do skorzystania z losowego materiału siewnego, aby można było odtworzyć mecze, chociaż nie jest to wymagane.

Dane wyjściowe: Labirynt prawidłowy rozmiar x rozmiar (kwadrat) przy użyciu formatu opisanego w części I. „ważny” oznacza, że ​​istnieje rozwiązanie, a komórka początkowa nie jest równa komórce końcowej.

Ocena architekta w danym labiryncie wynosi

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

Architekci są więc nagradzani za skomplikowane labirynty, ale karani za każdą zbudowaną ścianę (jest to substytut ograniczenia czasowego Ariadny). Thedist() Funkcja ta zapewnia, że labirynt bez ścian nie dostaje nieskończoną wynik. Zewnętrzne granice labiryntu nie wpływają na liczbę ścian.

Część III: Solver

Solver próbuje rozwiązać labirynty generowane przez architektów innych osób. Jest coś w rodzaju mgły wojny: uwzględniane są tylko ściany przylegające do odwiedzanych komórek (wszystkie inne są zastępowane przez „?”)

wejście: ten sam format labiryntu, ale z „?” gdzie ściany są nieznane, dodatkowy wiersz dla bieżącej lokalizacji i oddzielona przecinkami lista prawidłowych wyborów z tej lokalizacji. (Jest to duża edycja, która ma na celu uproszczenie pisania funkcji parsowania labiryntu)

przykład (taki sam jak powyższy labirynt 5x5 po zrobieniu jednego kroku w lewo)

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

Co odpowiada coś takiego, gdzie ?jest mgła:

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

wyjście: jeden z krotek z listy prawidłowych wyborów

Wynik każdego Solvera jest odwrotnością wyniku architekta.

Część IV: Król wzgórza

Architekci i solwery otrzymują osobne wyniki, więc potencjalnie może być dwóch zwycięzców.

Każda para architektów i solverów będzie miała wiele szans na przechytrzenie się. Wyniki będą uśredniane dla wszystkich testów i przeciwników. Wbrew konwencjom golfa kod wygrywa najwyższy średni wynik!

Zamierzam, aby to trwało, ale nie mogę zagwarantować ciągłego testowania na zawsze! Powiedzmy na razie, że zwycięzca zostanie ogłoszony za tydzień.

Część V: Składanie

• Utrzymuję władzę weta wobec wszystkich zgłoszeń - spryt jest zachęcany, ale nie wtedy, gdy psuje konkurencję lub mój komputer! (Jeśli nie potrafię powiedzieć, co robi twój kod, prawdopodobnie go zawetuję)
• Wymyśl nazwę swojej pary Architekt / Solver. Opublikuj swój kod wraz z instrukcjami, jak go uruchomić.

Już wkrótce: zaktualizowany zestaw testowy Python dla nowego formatu. Nastąpiły duże zmiany, aby umożliwić przesłanie dowolnego języka.

BuildFun i SolveFun

Cóż, zajęło to sporo czasu i nie jestem do końca pewien, czy solver oszukuje, czy nie. Choć ma dostęp do całego labiryntu przez cały czas, patrzy tylko na komórkę, w której się znajduje, otaczające go ściany i, jeśli nie ma między nimi ściany, komórki przylegające do niej. Jeśli jest to niezgodne z zasadami, daj mi znać, a postaram się to zmienić.

W każdym razie oto kod:

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

Zdaję sobie sprawę, że jest to absurdalnie długi i nie jest szczególnie łatwy do odczytania, ale jestem leniwy, więc tak właśnie jest.

BuildFun

Architekt BuildFun jest dość prostym programem do generowania labiryntu, który zawsze tworzy „idealny” labirynt (jeden bez pętli i gdzie dwa punkty zawsze będą miały dokładnie jedną ścieżkę między nimi). Opiera swoją logikę na danych wejściowych nasion, co oznacza, że ​​generowane labirynty są pseudolosowe z czymś, co często wydaje się powtarzającymi się wzorami, a przy tym samym ziarnie i rozmiarze powstanie ten sam labirynt.

Po wygenerowaniu labiryntu program podejmie próbę maksymalizacji wyniku labiryntu, szukając punktu początkowego i końcowego, które prowadzą do najdłuższej ścieżki między nimi. Aby to zrobić, biegnie przez każdy punkt początkowy, rozkłada znaczniki, aby znaleźć punkt końcowy najdalej od niego, i wybiera kombinację z najdłuższą ścieżką.

Następnie rysuje labirynt, liczy ściany i wysyła informacje o labiryncie. Jest to punkt początkowy, punkt końcowy, odległość między nimi, liczba ścian i wynik. Formatuje również te informacje w stylu opisanym powyżej dla rozmiaru, początku i końca, ścian poziomych i ścian pionowych i zapisuje je w pliku tekstowym o nazwie Maze.txt do późniejszego wykorzystania.

SolveFun

Solver, SolveFun, używa pliku tekstowego Maze.txt jako danych wejściowych i działa w bardzo podobny sposób jak architekt. Przy każdym ruchu wybierze kierunek, w którym chce podążać, w oparciu o swoje względne położenie do końca, a następnie spojrzy na otaczające go ściany. Jeśli nie ma tam ściany, sprawdzi, czy znajdowała się w sąsiedniej komórce, a jeśli nie, zostanie dodana jako możliwa opcja. Następnie przesunie się w kierunku najbliższym preferowanemu, pod warunkiem że ma opcje. Jeśli nie ma opcji, będzie się cofać, dopóki nie będzie. Trwa to aż do końca.

Podczas ruchu rejestruje ścieżkę, którą obiera w ścieżce zmiennej, która jest używana na końcu do wyprowadzenia całkowitej liczby kroków. Rejestruje także liczbę powtórzeń wykorzystanych do obliczenia zmarnowanych kroków na końcu. Kiedy osiągnie koniec, wypuści labirynt z najkrótszą ścieżką od początku do końca oznaczoną *s.

Jak biegać

Ze względu na metodę wypisywania labiryntu (która obejmuje podkreślenie niektórych znaków), należy go uruchomić z wiersza poleceń w formie

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

i

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

gdzie Size jest liczbą całkowitą od 15 do 50 (włącznie), a Seed jest liczbą całkowitą od 4 do Size (włącznie).