Interactive Maze Solver

13

Bob foi sequestrado e está preso em um labirinto. Seu trabalho é ajudá-lo a encontrar uma saída. Mas como é um labirinto muito escuro e assustador, ele não consegue ver nada. Ele só pode sentir paredes quando corre para dentro dela, e sabe quando encontrou a saída, mas não sabe mais nada sobre isso.

Como ele precisa executar o programa pela memória, ele deve ser o mais curto possível.

Nota: Eu peguei esse problema em http://acmgnyr.org/year2016/problems.shtml , mas o adaptei um pouco e escrevi pessoalmente o programa / teste dos juízes.

Especificação

  • Este é um problema interativo, portanto, o programa produzirá movimentos para o stdout e obterá respostas do stdin.
  • Seu programa pode um dos movimentos de saída right, left, down, up.
  • Ele obterá como entrada um dos seguintes:
    • wall- isso significa que Bob bateu em uma parede. Bob ficará no mesmo lugar.
    • solved- Bob encontrou a saída! Seu programa agora também deve sair sem imprimir mais nada.
    • ok - Bob foi capaz de se mover na direção dada.
  • Se o labirinto não tiver saída, seu programa deverá ser exibido no exitpara que Bob saiba que ele deve desistir. Seu programa deve sair sem imprimir mais nada.
  • Como Bob está com pressa de sair, seu programa não deve fazer movimentos estranhos. Em outras palavras, seu programa não tem permissão para se mover na mesma direção do mesmo quadrado duas vezes .
  • Isso é , e o programa mais curto vence!

Exemplos

Nos exemplos a seguir, Sé o quadrado inicial, Xé a saída, #é uma parede e os espaços são quadrados válidos. Como não há uma resposta correta, essas são apenas exemplos de execuções de uma solução. Observe também que os desenhos do labirinto estão lá para você ver, e seu programa não os receberá 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 Checker

  • Eu escrevi um verificador de solução em Python. Você pode encontrá-lo em https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19 .
  • Execute como python mazechecker.py ./mazesolver.
  • Ele testará seu programa em todos os labirintos em uma pasta chamada mazes.
  • Os labirintos estão em arquivos separados no mesmo formato acima.
  • Ele verifica todas as condições listadas acima e notifica se sua solução viola alguma.
  • Você pode imprimir informações adicionais de diagnóstico com python mazechecker.py -d ./mazesolver.
  • Você pode encontrar uma mazespasta compactada aqui . Você também pode adicionar seus próprios, se quiser.
Maltysen
fonte
1
Provavelmente vale a pena declarar explicitamente que o problema foi lançado sob uma licença CC-BY-NA-SA e, portanto, seu remix está necessariamente sob a mesma licença.
24619 Nick Kennedy
3
solvedRecebemos um quando a saída no exit? Nesse caso, indique-o nas regras, não apenas nos casos de teste!
Wastl
1
" seu programa não pode se mover na mesma direção a partir do mesmo quadrado duas vezes. " Duas perguntas sobre isso: 1. Digamos que eu esteja na posição x,ye vá up, com resposta wall, depois rightcom resposta novamente wall, posso tentar upnovamente, ou estão disponíveis lefte downainda estão disponíveis desde que ainda não me mudei desta praça?
Kevin Cruijssen 26/04/19
1
2. Digamos que eu tenho esse labirinto . Com esse fluxo: certo (ok); certo, ok); direita (parede); para cima (ok) ; para cima (ok); para cima (parede); esquerda (parede); para baixo (ok); para baixo (ok); para baixo (ok); para baixo (ok); para baixo (parede); direita (parede); para cima (ok); para cima (ok); Agora estou autorizado a subir novamente, embora já tivesse feito esse quadrado específico antes (no negrito)?
Kevin Cruijssen 26/04/19
1
@KevinCruijssen Não acompanho explicitamente de onde vim na minha resposta. Em vez disso, mantenho o controle de todas as direções que foram processadas em cada quadrado e tento quadrados não visitados primeiro. Quando todas as praças não visitadas foram tentadas, a única ação legal restante é de onde eu vim (já visitei, mas não nessa direção).
Arnauld

Respostas:

7

JavaScript (ES6),  180  174 bytes

Usa prompt()para emitir a direção e recuperar o 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])

Experimente online! (com E / S automatizada)

Snippet interativo

AVISO : esse código exibirá uma caixa de diálogo prompt () até que 'resolvido' seja inserido ou a função conclua que não há saída.

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