Inspirado en Realizamos saltos de torre y relacionados con 2D Maze Minus 1D
Introducción
Su tarea es encontrar la ruta más corta para salir de un laberinto de matrices siguiendo las reglas especificadas.
Desafío
Una matriz 1D a con n elementos puede considerarse como un laberinto compuesto por n puntos, donde el punto con índice k está conectado a los puntos con k + a [ k ] y k - a [ k ] de una sola manera. En otras palabras, puede saltar hacia adelante o hacia atrás exactamente a [ k ] pasos desde el punto con el índice k . Los puntos con un índice fuera de los límites de la matriz se consideran fuera del laberinto.
Para ilustrar esto, considere la siguiente matriz,
[0,8,5,9,4,1,1,1,2,1,2]
Si estamos en el quinto elemento en este momento, dado que el elemento es 4, podemos saltar 4 pasos hacia adelante hasta el noveno elemento, o 4 pasos hacia atrás hasta el primer elemento. Si hacemos lo último, terminamos con el elemento 0, que indica que no son posibles más movimientos. Si hacemos lo primero, dado que el noveno elemento es 2, podemos elegir saltar al elemento 11, que nuevamente es un 2, y luego podemos saltar nuevamente al "elemento 13", que está fuera de los límites del matriz y consideró una salida al laberinto.
Entonces, si comenzamos desde el elemento en el medio, una forma de salir del laberinto es saltar 1 paso hacia atrás, 4 pasos hacia adelante, 2 pasos hacia adelante y nuevamente 2 pasos hacia adelante, que se pueden expresar como la matriz [-1,4,2,2]
. Alternativamente se puede expresar con la matriz [4,8,10,12]
que registra el índice basado en cero de todos los puntos intermedios y finales (1 basado en índices es también fino), o sólo los signos, [-1,1,1,1]
.
Escapar del laberinto desde el extremo de bajo índice también está bien.
Usar la primera notación y comenzar desde el mismo elemento [1,1,1,2,2]
también es una solución, pero no es óptima ya que hay 5 pasos en lugar de 4.
La tarea es encontrar la ruta más corta para salir del laberinto de la matriz y generar la ruta. Si hay más de una ruta óptima, puede generar una o todas ellas. Si no hay una solución, debe generar un valor falso elegido por usted que sea discernible a partir de una ruta válida (no generar ningún resultado también está bien).
Para simplificar, el número de elementos en la matriz siempre es un número impar y siempre comenzamos desde el elemento en el medio.
Casos de prueba
Los casos de prueba ilustran varias formas de salida, pero no está limitado a estas.
Input
Output
[0,8,5,9,4,1,1,1,2,1,2]
[-1,4,2,2]
[2,3,7,1,2,0,2,8,9]
[2,9] (or [2,-5] or [[2,9],[2,-5]])
[0,1,2,2,3,4,4,4,3,2,2,3,0]
[1,-1,1,1]
[0,1,2,2,4,4,6,6,6,6,6,4,2,1,2,2,0]
[]
Especificaciones
Puede escribir una función o un programa completo.
La matriz solo contiene enteros no negativos.
Puede tomar entrada y salida a través de cualquier formulario estándar , pero especifique en su respuesta qué formulario está utilizando.
Este es el código de golf , gana el menor número de bytes.
Como de costumbre, las lagunas predeterminadas se aplican aquí.
fuente
[0,8,5,9,4,1,1,1,2,1,2]
, para salida[[-1,4,2,2]]
)[1,1,1,-1]
lugar de[-1,1,1,1]
?Respuestas:
JavaScript (ES6), 117 bytes
Devuelve una matriz de puntos intermedios y finales indexados en 0, o una matriz vacía si no existe una solución.
Pruébalo en línea!
Comentado
fuente
Casco , 22 bytes
Devuelve una lista de signos o una lista vacía si no existe una solución. Pruébalo en línea!
Explicación
Esta es una solución de fuerza bruta que comprueba las listas
-1,0,1
de mayor longitud y devuelve la primera que resulta en un salto fuera de la matriz. Como tiene una longitud mínima, no contendrá 0s.fuente
Python 3 ,
195188179 bytesPruébalo en línea!
Editar:
all(..)and s => all(..)*s
,if u not in x => if{u}-x
El primero explota
boolean * list == int * list
, el último usa la diferencia de conjunto (el conjunto vacío también es falso).Formato de salida: conjunto anidado de todas las respuestas óptimas, dado como índices basados en cero de puntos intermedios y finales.
Por ejemplo
f([0,8,5,9,4,1,1,1,2,1,2]) == [[4, 8, 10, 12]]
.El algoritmo es simple BFS.
s
registra todas lasi
rutas de longitud posibles eni
la iteración, excluyendo los índices ya visitados. Tenga en cuenta que la notación en estrella extendida se usa (ab) porque el acceso repetido a la matriz es costoso. Descubrí que dicha notación también puede reducir algunos espacios en blanco si se usa correctamente.También hice una versión recursiva (pero más larga) de la solución anterior. Ambos
s and
yor s
son necesarios, de lo contrario no funciona.Python 3 , 210 bytes
Pruébalo en línea!
fuente
Haskell ,
207202 bytes5 bytes guardados gracias a BMO .
Pruébalo en línea!
Esta es una función que toma una lista
Int
como parámetro y devuelve una lista de rutas donde cada ruta es una lista de saltos relativos tomados para salir de la matriz.La versión sin golf:
fuente
C (gcc) , 269 bytes
Pruébalo en línea!
Inicialmente probé una búsqueda recursiva de retroceso, porque usar
main
para la recursividad siempre es divertido. Al final, sin embargo, se pudo hacer una búsqueda directa no recursiva de amplitud, que es lo que es esta versión. Este programa toma la matriz de entrada como argumentos de línea de comandos, sin llaves, por ejemplo,0 8 5 9 4 1 1 1 2 1 2
para el primer ejemplo proporcionado. El programa genera en stdout una lista de índices de matriz delimitados por comas indexados en 1 en orden inverso, comenzando desde el índice final, fuera de límites / 'escapado' y trabajando nuevamente a través de los índices intermedios alcanzados (no genera el centro, índice inicial). El programa no genera llaves alrededor de la matriz y deja una coma final porqueprintf
Las declaraciones toman muchos caracteres. La salida correspondiente al primer ejemplo de prueba anterior es13,11,9,5,
, por ejemplo.Si no hay una ruta de escape del laberinto de matrices, el programa no genera nada.
Degolfed y explicó que está debajo (fuertemente desgolfado con algunos cambios para facilitar la lectura):
Como es habitual para el código C golfizado, la salida de la compilación incluirá, por supuesto, un muro amistoso de advertencias y notas.
fuente
Perl 5 , -a: 73 bytes
(conteo de estilo antiguo: 75 bytes,
+1
paraa
y+1
para la sustitución de-//
por-/$/
y utilizar$`
para$'
)Dé la matriz de entrada como una línea en STDIN, por ejemplo
0 8 5 9 4 1 1 1 2 1 2
imprime las posiciones visitadas en orden inverso, incluido el punto de partida, luego se bloquea
No imprime nada si no hay solución
Pruébalo en línea!
fuente
Ruby , 102 bytes
Pruébalo en línea!
Toma el laberinto de entrada como una matriz, e imprime la ruta de escape en reversa, desde la salida hasta el punto de partida (inclusive). No imprime nada si no hay escapatoria.
Este enfoque hace un mal uso del método de mapa para iterar a través de una matriz temporal que almacena el historial de rutas, que se extiende constantemente sobre la marcha cada vez que hay otro posible paso a seguir.
En principio, podría guardar otro byte usando en
return x
lugar debreak p x
, pero eso significaría afirmar que mi valor falso es igual a toda la basura monstruosa almacenadab
. Probablemente, esto sería demasiado, incluso teniendo en cuenta la flexibilidad permitida de la salida ...Tutorial
fuente