Es hora de otro desafío de laberinto, pero no como lo sabes.
Las reglas para este desafío son un poco diferentes a la mayoría de los desafíos de laberintos. Los tipos de mosaico se definen de la siguiente manera:
S: La ubicación en el laberinto donde comienzasE: La ubicación a la que intenta llegar0: Muro que no puedes cruzar+: Piso que puedes cruzar
Puede viajar en una de las seis direcciones: arriba a la izquierda, arriba a la derecha, izquierda, derecha, abajo a la izquierda o abajo a la derecha.
\ /
-S-
/ \
El laberinto no se envuelve. El objetivo es encontrar la cadena de ruta más corta para llegar Sa E.
Entrada:
La entrada es líneas separadas por espacios como los laberintos mostrados. Ningún espacio final seguirá una línea.
Salida:
Una cadena de R, Ly Fdonde
Rte gira a la derecha (en sentido horario) 60 gradosLgira a la izquierda (en sentido antihorario) 60 gradosFte mueve un espacio en la dirección que estás apuntando
Empiezas a señalar left-up
La ruta más corta se cuenta por la longitud de la cadena producida, no por el número de posiciones visitadas. Su programa debe imprimir la ruta más corta como la solución.
Si el laberinto no se puede resolver, debe salir Invalid maze!.
( >>>es la salida)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Tenga en cuenta que algunos de los laberintos tienen otras soluciones que tienen la misma longitud pero que no se enumeran aquí)
fuente
Respuestas:
Python 2, 291 bytes
Una función,
ftomar el laberinto como una lista de filas y devolver una solución, si existe.Explicación
Realiza una búsqueda de amplitud en el gráfico de pares de posición / dirección para encontrar la ruta más corta de
SaE.Lo interesante es encontrar una forma compacta de representar posiciones y direcciones en una cuadrícula hexagonal, que admita un simple "paso" (es decir, moverse en una determinada dirección) y rotación. Es tentador usar números complejos aquí, para representar coordenadas en una cuadrícula hexagonal "real", pero esta no es una muy buena idea por varias razones, la más grave de las cuales es el hecho de que necesitamos enchufar un √3 en algún lugar para que funcione (sen 60 ° = √3 / 2), que, cuando se usan números de punto flotante, no se recomienda si necesitamos precisión absoluta (por ejemplo, para hacer un seguimiento de los estados que ya hemos visitado;) puedes intentar encender tu consola JavaScript y escribir
Math.sqrt(3)*Math.sqrt(3) == 3y ver por ti mismo.¡Pero podemos usar un pequeño truco! En lugar de usar números complejos, definamos números hexagonales en una veta similar, como un par de números reales a + bh , donde h juega un papel similar al imaginario i cuando se trata de números complejos. Al igual que con los números complejos, podemos asociar el par ( a , b ) con un punto en el plano, donde el eje real apunta hacia la derecha, el eje imaginario apunta 60 ° hacia arriba, y ambos cruzan el hexágono regular de la unidad cuando el real y las partes imaginarias son iguales a 1, respectivamente. Mapear este sistema de coordenadas a las celdas del laberinto es trivial.
A diferencia de i , la constante h está definida por la relación h 2 = h - 1 (resolver para h podría revelar algunas ideas). ¡Y eso es todo! Los números hexagonales se pueden sumar y multiplicar, usando la relación anterior, al igual que los números complejos: ( a + bh ) + ( c + dh ) = ( a + c ) + ( b + d ) h ,
y ( a + bh ) · ( c + dh ) = ( ac - bd) + ( ad + bc + bd ) h . Estas operaciones tienen la misma interpretación geométrica que sus contrapartes complejas: la suma es la suma de vectores, y la multiplicación es escalado y rotación. En particular, para rotar un número hexagonal 60 ° en sentido antihorario, lo multiplicamos por h :
( a + bh ) · h = - b + ( a + b ) h , y para rotar el mismo número 60 ° en sentido horario, dividimos por h :
( a + bh ) / h = ( a +bh ) · (1 - h ) = (a + b) - ah . Por ejemplo, podemos tomar la unidad del número hexagonal apuntando a la derecha, 1 = (1, 0), un círculo completo, en sentido antihorario, multiplicándolo por h seis veces:
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
El programa utiliza números hexagonales de esta manera para representar la posición actual en el laberinto y la dirección actual, avanzar en la dirección especificada y rotar la dirección hacia la izquierda y hacia la derecha.
fuente
Hexagonía , 2437 bytes.
El programa tan esperado está aquí:
Pruébalo en línea!
Versión "legible":
Probado en IDE esotérico: TIO podría agotar el tiempo en algunos de los casos de prueba más grandes, pero todos verificados. Muchas gracias a Timwi, esto no hubiera sido posible sin el IDE.
Hay un poco de espacio vacío, por lo que podría haber sido capaz de ajustar esto en un hexágono de longitud lateral 28 (en lugar de la longitud lateral 29), pero esa será una tarea enorme, por lo que probablemente no voy a intentarlo.
Explicación Básica
Haga clic en las imágenes para obtener una versión más grande y más detallada.
Las funciones
Nota: Las divisiones son generalmente correctas, pero en ocasiones pueden ser una suposición aproximada.
Este código es bastante "funcional", tanto como lo permite Hexagony. Hay ocho funciones principales en este código etiquetadas en el diagrama anterior, nombradas por los números con los que se llaman (por lo que sus números de puntero de instrucción son ese número mod 6). En orden (aproximado) de llamada, son (los nombres entre comillas son ubicaciones en la memoria que se explicarán más adelante):
F,RyLlistos para su procesamiento principal. El puntero de instrucción 0 se mueve a la función 0 mientras que la ejecución se mueve a la función 1.+dentro de los 2 movimientos desde que se alcanza por primera vez. Vuelve a la función 1.F. Vuelve a la función 1.F,RoLanexa. Vuelve a la función 1.FFLF), luego termina el programa.Invalid maze!y termina.Memoria
Nota: Gracias al IDE Esotérico nuevamente por el diagrama.
La memoria consta de tres partes principales:
0o un lugar válido al que se accedió hace más movimientos de los que se necesitarían para salir del lugar en cualquier dirección.+que aún no se ha alcanzado.-1s con un solo-2a la izquierda, permite que el puntero de memoria regrese rápidamente al área de procesamiento central.F,R,Lcomo1,2,3respectivamente-1s hacia la derecha y luego los valores hacia arriba (aunque y = 0 se procesa como 1 de todos modos con el fin de separar el riel de los datos de referencia)Otras ubicaciones importantes de memoria:
Ese almacena aquí.fuente
Python 3, 466 bytes
Probablemente habría terminado más pequeño si usara la búsqueda de profundidad primero o algo así. Esta monstruosidad usa Dijkstra y es bastante rápida, pero muy larga.
El código define una función
Sque toma una cadena multilínea con el laberinto y devuelve el resultado.Aquí hay una prueba del código.
Sin golf
fuente
L,,R.Groovy, 624 bytes. ¡Delantero!
Time time hace que la pelota ruede con una grande. Toma una cadena de varias líneas como arg para
QVersión sin golf:
fuente
C #,
600574 bytesPrograma completo, acepta entrada de STDIN, salida a STDOUT.
Editar: hubo un error en el manejo de la envoltura (no se rompió en ninguno de los casos de prueba dados) que habría agregado 1 byte, por lo que hice un poco más de golf para compensar.
Comienza leyendo en el mapa, agregando
(a cada línea para que sepa dónde termina, y puede retroceder y agregar una carga de espacios para hacer que el mapa sea rectangular y con una fila de espacios a lo largo del lado derecho (esto ahorra haciendo cheques de envoltura como se explicará a continuación) Calcula el ancho del rectángulo en algún punto de esto y determina la longitud total del Mapa.A continuación, inicializa todo para una búsqueda de Breadth-First. Se crean dos matrices grandes, una para almacenar todos los estados que necesitamos explorar en nuestra búsqueda, la otra para registrar la ruta que tomamos para llegar a cada estado. El estado inicial se agrega a la matriz debida, con los punteros de cabeza y cola preestablecidos en algún punto anterior. Todo está indexado en 1.
Luego iteramos hasta que la cola se estrella contra la cabeza, o al menos parece haberse estrellado contra la cabeza. Para cada estado que hemos visitado, intentamos agregar un nuevo estado en la misma posición en la que giramos hacia la izquierda o la derecha, y luego uno en el que hemos avanzado. Las direcciones están indexadas, con la dirección inicial (predeterminada
0) correspondiente a "arriba a la izquierda".Cuando tratamos de poner en cola un estado, se verifica el límite, pero no se verifica el ajuste, debido a las columnas de espacios en el lado derecho, que se recoge con el "¿se nos permite estar aquí?" marca (no puedes estar en espacios). Si el estado está en cola, verificamos si está en la
Ecelda, y si lo está, configuramos el encabezado de la cola para que sea menos, lo que hace que salga el bucle principal y le dice a la última línea del programa que se imprima fuera de la ruta correspondiente, en lugar del mensaje de falla (que muestra si nos quedamos sin estados para expandirnos (la cola se estrella en la cabeza)).Como la mayoría de mis búsquedas de gráficos en este sitio, estoy haciendo un buen uso de las estructuras de C #, que por defecto se comparan por valor literal.
fuente
Python 2, 703 bytes
No es tan bueno como las otras dos versiones, pero al menos funciona jaja. Establecer
Men el laberinto.Como no tengo experiencia en la resolución de laberintos, solo se aplica un enfoque de fuerza bruta, donde encontrará todas las soluciones que no implique cruzar de nuevo sobre sí mismo. Calcula los giros a partir de los más cortos y luego elige el resultado más corto.
Versión desordenada y sin golf:
fuente
if heading != required_heading: while heading != required_heading:con solowhile heading != required_heading: