El escape del laberinto de flechas

14

Pregunta

Tienes una matriz de 50 por 50 caracteres. Cada celda tiene una flecha que apunta en cualquiera de las cuatro direcciones. Ninguna celda está vacía. Al ingresar a una celda, debe salir en la dirección especificada por la flecha. La flecha también puede apuntar en la misma dirección de donde vino, lo que resulta en un callejón sin salida.

Puede comenzar desde cualquier celda en el borde más externo del laberinto y encontrar un camino que lo lleve al laberinto y le haga salir en otra celda. La entrada se dará como una matriz que contiene <,>, ^ y v. La salida será un solo dígito (booleano, entero o carácter, cualquier cosa servirá) como 0 (lo que indica que la tarea es imposible) o 1 (lo que indica que tiene logrado la tarea).

Ejemplo (la matriz real será más grande que esto)

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

La salida será

1
como puede ingresar desde <a la derecha, lo que hará que salga de la parte inferior v por la ruta "<v v"

La tarea es escribir el código más corto posible que recibirá el laberinto como entrada, y determinar dónde existe una ruta en él como se especifica en las reglas y generar un solo dígito 0 o 1

También se permite generar VERDADERO y FALSO en lugar de dígitos reales.

fantasmas_en_el_código
fuente
66
Sería bueno tener algunos casos de prueba reales con los que trabajar
Liam el
¿La entrada es una matriz unidimensional o bidimensional? ¿Y solo puede ingresar a la derecha con un <o también puede ingresar con un ^?
bobbel
@bobbel Input se puede proporcionar como una matriz de 1 o 2 dimensiones, lo que sea necesario para un código más corto. Incluso las flechas se pueden ingresar como 1 2 3 4 en lugar de <> ^ v si eso puede acortar el código. Y sí, puedes ingresar a través de ^ también.
ghosts_in_the_code
1
La probabilidad de que una matriz aleatoria, de 50 por 50, no tenga una solución es de aproximadamente 0. Sería mejor si necesitara que la solución tenga al menos un cierto número de pasos o que el usuario especifique la ruta de la solución.
DavidC
1
Esto debería haber sido llamado "Un escape de flecha" ... Todavía reflexionando sobre una solución.
vaso de precipitados el

Respuestas:

6

CJam, 89 81 bytes

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

Pruébelo en línea en el intérprete de CJam .

Cómo 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
fuente