Bob fue secuestrado y está atrapado en un laberinto. Tu trabajo es ayudarlo a encontrar una salida. Pero como es un laberinto muy oscuro y aterrador, no puede ver nada. Solo puede sentir las paredes cuando se topa con ella, y sabe cuándo ha encontrado la salida, pero no sabe nada más.

Como tiene que ejecutar su programa de memoria, debe ser lo más corto posible.

Nota: Tomé este problema de http://acmgnyr.org/year2016/problems.shtml , pero lo adapté un poco y escribí el programa del juez / casos de prueba yo mismo.

Especificación

• Este es un problema interactivo, por lo que su programa generará movimientos en stdout y aceptará respuestas de stdin.
• Su programa puede una salida de los movimientos right, left, down, up.
• Luego obtendrá como entrada uno de los siguientes:
  • wall- Esto significa que Bob ha golpeado una pared. Bob se quedará en el mismo lugar.
  • solved- Bob ha encontrado la salida! Su programa ahora también debería salir sin imprimir nada más.
  • ok - Bob pudo moverse en la dirección dada.
• Si el laberinto no tiene salida, su programa debería salir no exitpara que Bob sepa que debe darse por vencido. Su programa debería salir sin imprimir nada más.
• Como Bob tiene prisa por salir, su programa no debe hacer movimientos extraños. En otras palabras, su programa no puede moverse en la misma dirección desde la misma casilla dos veces .
• Este es el código de golf , por lo que gana el programa más corto

Ejemplos

En los siguientes ejemplos, Ses el cuadrado inicial, Xes la salida, #es un muro y los espacios son cuadrados válidos. Como no hay una respuesta correcta única, estos son solo ejemplos de ejecuciones de una solución. También tenga en cuenta que los dibujos del laberinto están ahí para que los vea, y su programa no los obtendrá como entrada.

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

Programa de corrector

• He escrito un corrector de soluciones en Python. Puede encontrarlo en https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
• Ejecútalo como python mazechecker.py ./mazesolver.
• Pondrá a prueba su programa en todos los laberintos en una carpeta llamada mazes.
• Los laberintos están en archivos separados en el mismo formato desde arriba.
• Comprueba todas las condiciones enumeradas anteriormente y le notifica si su solución viola alguna.
• Puede hacer que imprima información de diagnóstico adicional con python mazechecker.py -d ./mazesolver.
• Puede encontrar una mazescarpeta comprimida aquí . También puede agregar el suyo si lo desea.

JavaScript (ES6),  180  174 bytes

Utiliza prompt()para dar salida a la dirección y recuperar el resultado.

_=>(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])

Pruébalo en línea! (con E / S automatizadas)

Fragmento interactivo

ADVERTENCIA : este código mostrará un cuadro de diálogo prompt () hasta que se ingrese 'resuelto' o la función descubra que no hay salida en absoluto.

(
_=>(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])
)()

Comentado

_ => (                      // 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)