Votre tâche consiste à jouer les rôles des deux personnages dans cette scène de Inception. Dans ce document, Cobb lance un défi à Ariane:

Vous avez deux minutes pour concevoir un labyrinthe qui prend une minute à résoudre.

Certaines libertés seront prises sur cette description. Plus important encore, ce défi n'est pas basé sur le temps, les scores sont plutôt basés sur l'efficacité de vos labyrinthes et de vos labyrinthes.

Je m'excuse pour les nombreuses modifications apportées à ce défi alors que nous itérons vers un format simple et équitable ..

Partie I: Format du labyrinthe

Tous les labyrinthes sont carrés. Une cellule du labyrinthe est représentée comme un tuple indexé zéro row column.

Les murs sont représentés par deux chaînes binaires: une pour les murs horizontaux (qui bloquent le mouvement entre les rangées) et les murs verticaux (vice versa). Sur un NxNlabyrinthe, il existe Nx(N-1)des murs possibles de chaque type. Prenons un exemple 3x3 où les cellules sont étiquetées:

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

toutes les parois verticales possibles sont les suivantes : AB BC DE EF GH HI. Traduits en chaîne, les murs indiqués sont 011001des murs verticaux et 010010des murs horizontaux. En outre, par "chaîne binaire", je veux dire "les caractères" 0 "et" 1 "".

Le format du labyrinthe complet est une chaîne qui contient, dans cet ordre:

• largeur
• démarrer le tuple de cellule
• tuple de cellule d'extrémité
• murs horizontaux
• murs verticaux

Par exemple, ce labyrinthe:

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

est formaté comme suit:

5
4 2
0 2
00001011101110001100
10100110000100010010

Partie II: L'architecte

Le programme Architect crée le labyrinthe. Il doit respecter les règles et fournir un labyrinthe valide (celui où une solution existe et où la fin n'est pas au-dessus du début).

Entrée: deux entiers positifs:

size [random seed]

Où sizesera [15, 50]. Nous vous encourageons à utiliser la graine aléatoire afin que les matchs puissent être rejoués, bien que cela ne soit pas obligatoire.

Sortie: un labyrinthe de taille x taille (carré) valide utilisant le format décrit dans la partie I. «valide» signifie qu'une solution existe et que la cellule de début n'est pas égale à la cellule de fin.

Le score d'un architecte sur un labyrinthe donné est

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

Les architectes sont donc récompensés pour des labyrinthes complexes, mais pénalisés pour chaque mur construit (ceci remplace la restriction de temps d'Ariane). La dist()fonction garantit qu'un labyrinthe sans murs n'obtient pas un score infini. Les bordures extérieures du labyrinthe ne contribuent pas au dénombrement des murs.

Partie III: Le solveur

Le Solveur tente de résoudre des labyrinthes générés par les architectes des autres. Il y a une sorte de brouillard de guerre: seuls les murs adjacents aux cellules visitées sont inclus (tous les autres sont remplacés par «?»)

entrée: le même format de labyrinthe, mais avec '?' où les murs sont inconnus, une ligne supplémentaire pour l'emplacement actuel et une liste de choix valides séparés par des virgules à partir de cet emplacement. (Il s'agit d'un gros montage qui vise à simplifier l'écriture d'une fonction d'analyse de labyrinthe)

exemple (identique au labyrinthe 5x5 ci-dessus après avoir fait un pas à gauche)

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

Ce qui correspond à quelque chose comme ça, où ?est le brouillard:

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

sortie: l' un des tuples de la liste des choix valides

Le score de chaque solveur est l'inverse du score de l'architecte.

Partie IV: Roi de la colline

Les architectes et les solveurs reçoivent des scores séparés, il pourrait donc y avoir potentiellement deux gagnants.

Chaque paire d'architectes et de solveurs aura de nombreuses chances de se surpasser. Les scores seront calculés en moyenne sur tous les tests et adversaires. Contrairement aux conventions de golf de code, le score moyen le plus élevé gagne!

J'ai l'intention que cela se poursuive, mais je ne peux pas garantir la poursuite des tests pour toujours! Disons pour l'instant qu'un gagnant sera déclaré dans une semaine.

Partie V: Soumission

• Je conserve un droit de veto sur toutes les soumissions - l'intelligence est encouragée, mais pas si cela brise la concurrence ou mon ordinateur! (Si je ne peux pas dire ce que fait votre code, je vais probablement y opposer mon veto)
• Trouvez un nom pour votre paire Architecte / Solveur. Publiez votre code avec des instructions sur la façon de l'exécuter.

Prochainement: un kit de test python mis à jour pour le nouveau format. De grands changements se sont produits pour permettre toutes les soumissions linguistiques.

BuildFun et SolveFun

Eh bien, cela a pris un certain temps et je ne suis pas tout à fait sûr de savoir si le solveur triche ou non. Bien qu'il ait accès à tout le labyrinthe tout le temps, il ne regarde que la cellule dans laquelle il se trouve, les murs qui l'entourent et, s'il n'y a pas de mur entre eux, les cellules adjacentes. Si cela est contraire aux règles, veuillez me le faire savoir et j'essaierai de le changer.

Quoi qu'il en soit, voici le 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'

Je me rends compte que c'est ridiculement long et pas particulièrement facile à lire, mais je suis paresseux alors c'est comme ça que ça reste.

BuildFun

L'architecte, BuildFun, est un programme de génération de labyrinthe assez simple qui créera toujours un labyrinthe «parfait» (un sans boucles et où deux points auront toujours exactement un chemin entre eux). Il fonde sa logique sur l'entrée de graine, ce qui signifie que les labyrinthes générés sont pseudo-aléatoires avec ce qui semble souvent être des motifs répétitifs et, avec la même graine et la même taille, le même labyrinthe sera créé.

Une fois le labyrinthe généré, le programme tentera de maximiser le score du labyrinthe en recherchant le point de départ et le point final qui se traduisent par le chemin le plus long entre eux. Pour ce faire, il parcourt chaque point de départ, répartit les traceurs pour trouver le point final le plus éloigné et sélectionne la combinaison avec le chemin le plus long.

Après cela, il dessine le labyrinthe, compte les murs et sort les informations du labyrinthe. Il s'agit du point de départ, du point d'arrivée, de la distance entre eux, du nombre de murs et du score. Il formate également ces informations dans le style décrit ci-dessus pour la taille, le début et la fin, les murs horizontaux et les murs verticaux et les enregistre dans un fichier texte appelé Maze.txt pour une utilisation ultérieure.

SolveFun

Le solveur, SolveFun, utilise le fichier texte Maze.txt comme entrée et fonctionne de manière très similaire à l'architecte. Pour chaque mouvement, il choisira une direction qu'il veut suivre en fonction de sa position relative jusqu'à la fin, puis il regardera les murs qui l'entourent. Si un mur n'est pas là, il vérifiera s'il a été dans la cellule adjacente et, sinon, il sera ajouté comme option possible. Il se déplacera ensuite dans la direction la plus proche de sa direction préférée à condition qu'il ait des options. S'il n'a pas d'options, il reviendra en arrière jusqu'à ce qu'il le fasse. Cela continue jusqu'à la fin.

En se déplaçant, il enregistre le chemin qu'il prend dans le chemin variable qui est utilisé à la fin pour afficher le nombre total d'étapes. Il enregistre également le nombre de fois qu'il a dû revenir en arrière pour calculer les étapes perdues à la fin. Quand il atteint la fin, il sortira le labyrinthe avec le chemin le plus court du début à la fin marqué avec* s.

Comment courir

En raison de la méthode de sortie du labyrinthe (qui comprend le soulignement de certains caractères), cela doit être exécuté à partir d'une ligne de commande sous la forme

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

et

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

où Size est un entier compris entre 15 et 50 (inclus) et Seed est un entier compris entre 4 et Size (inclus).