Bob a été kidnappé et est coincé dans un labyrinthe. Votre travail consiste à l'aider à trouver une issue. Mais comme c'est un labyrinthe très sombre et effrayant, il ne peut rien voir. Il ne peut sentir les murs que lorsqu'il s'y précipite et sait quand il a trouvé la sortie, mais il n'en sait rien de plus.

Puisqu'il doit exécuter votre programme par mémoire, il doit être aussi court que possible.

Remarque: J'ai pris ce problème à partir de http://acmgnyr.org/year2016/problems.shtml , mais je l'ai adapté légèrement et j'ai écrit moi-même le programme juge / les cas de test.

spécification

• Il s'agit d'un problème interactif, donc votre programme générera des mouvements vers stdout et recevra les réponses de stdin.
• Votre sortie peut l' un des programmes les mouvements right, left, down, up.
• Il obtiendra alors en entrée l'un des éléments suivants:
  • wall- cela signifie que Bob a heurté un mur. Bob restera au même endroit.
  • solved- Bob a trouvé la sortie! Votre programme devrait maintenant également quitter sans imprimer autre chose.
  • ok - Bob a pu se déplacer dans la direction donnée.
• Si le labyrinthe n'a pas de sortie, votre programme devrait sortir no exitpour faire savoir à Bob qu'il doit abandonner. Votre programme devrait alors quitter sans imprimer autre chose.
• Étant donné que Bob est pressé de sortir, votre programme ne devrait pas faire de mouvements étrangers. En d'autres termes, votre programme n'est pas autorisé à se déplacer dans la même direction à partir du même carré deux fois .
• C'est du golf de code , donc le programme le plus court gagne!

Exemples

Dans les exemples suivants, Sest le carré de départ, Xest la sortie, #est un mur et les espaces sont des carrés valides. Puisqu'il n'y a pas de réponse correcte unique, ce ne sont que des exemples d'exécutions d'une solution. Notez également que les dessins du labyrinthe sont juste là pour que vous puissiez les voir, et votre programme ne les recevra pas en entrée.

########
#S     #
###### #
     # #
     #X#

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              solved

#####
# S #
#####

right
              ok
right
              wall
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              wall
right
              ok
no exit
              solved

###############################
#S                            #
##############       ###      #
             #       #X#      #
             #                #
             ##################

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              wall
down
              ok
left
              wall
down
              ok
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              solved

Programme Checker

• J'ai écrit un vérificateur de solution en Python. Vous pouvez le trouver sur https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
• Exécutez-le comme python mazechecker.py ./mazesolver.
• Il testera votre programme sur tous les labyrinthes d'un dossier appelé mazes.
• Les labyrinthes sont dans des fichiers séparés dans le même format que ci-dessus.
• Il vérifie toutes les conditions énumérées ci-dessus et vous avertit si votre solution en viole une.
• Vous pouvez lui faire imprimer des informations de diagnostic supplémentaires avec python mazechecker.py -d ./mazesolver .
• Vous pouvez trouver un mazesdossier zippé ici . Vous pouvez également y ajouter le vôtre si vous le souhaitez.

JavaScript (ES6),  180  174 octets

Permet prompt()de sortir la direction et de récupérer le résultat.

_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])

Essayez-le en ligne! (avec E / S automatisées)

Extrait interactif

AVERTISSEMENT : ce code affichera une boîte de dialogue d'invite () jusqu'à ce que «résolu» soit entré ou que la fonction comprenne qu'il n'y a aucune sortie du tout.

(
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])
)()

Commenté

_ => (                      // anonymous function taking no argument
  g = p =>                  // g = recursive function taking the current position p = [x, y]
    [ ...'0123',            // i<4  : try to move on squares that haven't been visited yet
      ...'0123',            // 3<i<8: try to go back to where we initially came from
      ...'4'                // i=8  : if everything failed, there must be no exit
    ].some((d, i) =>        // for each direction d at index i:
      g[p] >> d & 1         //   if this direction was already tried at this position
      | i < 4 &             //   or i is less than 4 and
      g[P = [               //   the square at the new position P = [X, Y] with:
        p[0] + (d - 2) % 2, //     X = x + dx[d]
        p[1] + ~-d % 2      //     Y = y + dy[d]
      ]] > 0 ?              //   was already visited:
        0                   //     abort
      : (                   //   else:
        r = prompt(         //     output the direction:
          [ 'up',           //       0 = up
            'left',         //       1 = left
            'down',         //       2 = down
            'right',        //       3 = right
            'no exit'       //       4 = no exit
          ][                //
            g[p] |= 1 << d, //       mark this direction as used
            d               //       d = actual index of the string to output
          ]                 //     r = result of prompt()
        )                   //
      ) < 's' ?             //     if r = 'ok':
        g(P)                //       do a recursive call at the new position
      :                     //     else:
        r < 't'             //       yield true if r = 'solved' or false if r = 'wall'
    )                       // end of some()
)([0, 0])                   // initial call to g at (0, 0)