A fuga do labirinto de flechas

14

Questão

Você tem uma matriz de 50 por 50 caracteres. Cada célula tem uma seta apontando em qualquer uma das quatro direções. Nenhuma célula está vazia. Ao inserir uma célula, você deve sair dela na direção especificada pela seta. A seta também pode apontar na mesma direção de onde você veio, resultando em um beco sem saída.

Você pode começar de qualquer célula na borda mais externa do labirinto e encontrar um caminho que o leve ao labirinto e faça com que você saia em outra célula. A entrada será fornecida como uma matriz contendo <,>, ^ e v. A saída será um dígito (booleano, número inteiro ou caractere, qualquer coisa serve) como 0 (indicando que a tarefa é impossível) ou 1 (indicando que você possui alcançou a tarefa).

Exemplo (a matriz real será maior que isso)

^ v < >
> < v <
v > v ^

A saída será 

1
como você pode digitar a partir do <à direita, o que fará com que você saia da parte inferior v pelo caminho "<v v"

A tarefa é escrever o código mais curto possível que receberá o labirinto como entrada e determinar onde existe um caminho, conforme especificado nas regras, e emitir um único dígito 0 ou 1

Saída TRUE e FALSE em vez de dígitos reais também é permitida.

code-golf maze ghosts_in_the_code
fonte
6
Seria bom ter alguns casos de teste reais para trabalhar com
Liam
A entrada é uma matriz unidimensional ou bidimensional? E você pode digitar apenas à direita por um <ou você também pode digitar por um ^?
bobbel
A entrada @bobbel pode ser fornecida como uma matriz de 1 ou 2 dimensões, o que for necessário para um código mais curto. As setas pares podem ser inseridas como 1 2 3 4 em vez de <> ^ v, se isso puder diminuir o código. E sim, você pode entrar via ^ também.
ghosts_in_the_code
1
A probabilidade de uma matriz aleatória, de 50 por 50, não ter uma solução é de aproximadamente 0. Seria melhor se você exigisse que a solução tivesse pelo menos um certo número de etapas ou que o usuário especificasse o caminho da solução.
31415
1
Isso deveria ter sido chamado de "Uma fuga de flecha" ... Ainda pensando em uma solução.
Novinho

Respostas:

6

CJam, 89 81 bytes

q~"><v^":A2/{f{\*}z}/sA[1W52-52]er:T,,{[52md]51f%0e=1=},:E{[2704{__T=+}*]\-E&},,g

Experimente on-line no intérprete CJam .

Como funciona

q~        e# Read and evaluate all input. This pushes an array of strings.
"><v^":A  e# Push that string and save it in A.
2/        e# Split it into ["><" "v^"].
{         e# For each chunk:
  f{      e#   For each input string, push the string and the chunk; then:
    \*    e#     Join the chunk, using the string as separator.
  }       e#
  z       e#   Transpose rows and columns.
}/        e#
s         e# Flatten the resulting array of strings.
A         e# Push "><v^".
[1W52-52] e# Push [1 -1 52 -52].
er        e# Perform transliteration.
:T        e# Save the result in T.
,,        e# Push [0 ... 2703].
{         e# Filter; for each integer I in [0 ... 2703]:
  [52md]  e#   Push [I/52 I%52].
  51f%    e#   Take both integers modulo 51 to map 51 to 0.
  0e=     e#   Count the number of resulting zeroes.
  1=      e#   Check if the count is 1.
},        e# If it is, keep I.
:E        e# Save the filtered array in E.
{         e# For each integer I in E:
  [2704{  e#   Do 2704 times:
    __    e#     Push two copies of the integer on the stack.
    T=    e#     Select the corresponding element from T.
    +     e#     Add it to the first copy.
  }*]     e#   Collect all results in an array.
  \-      e#   Remove I from that array.
  E&      e#   Intersect with E.
},        e# If the intersection is non-empty, keep the integer.
,g        e# Push the sign of the length of the filtered array.
Dennis
fonte