Un laberinto en una cuadrícula de celdas cuadradas N por N se define al especificar si cada borde es un muro o no un muro. Todos los bordes exteriores son paredes. Una celda se define como el inicio , y una celda se define como la salida , y la salida es accesible desde el inicio. El inicio y la salida nunca son la misma celda.
Tenga en cuenta que ni el inicio ni la salida deben estar en el borde exterior del laberinto, por lo que este es un laberinto válido:
Una cadena de 'N', 'E', 'S' y 'W' indica que intenta moverse hacia el norte, este, sur y oeste, respectivamente. Un movimiento que está bloqueado por un muro se omite sin movimiento. Una cadena sale de un laberinto si la aplicación de esa cadena desde el inicio da como resultado que se alcance la salida (independientemente de si la cadena continúa después de llegar a la salida).
Inspirado por esta pregunta enigmática. SE para la cual xnor proporcionó un método comprobable de resolución con una cadena muy larga, escriba código que pueda encontrar una sola cadena que salga de un laberinto de 3 por 3.
Excluyendo laberintos inválidos (inicio y salida en la misma celda, o salida no accesible desde el inicio) hay 138,172 laberintos válidos y la cadena debe salir de cada uno de ellos.
Validez
La cadena debe cumplir lo siguiente:
- Está compuesto solo por los caracteres 'N', 'E', 'S' y 'W'.
- Sale de cualquier laberinto al que se aplica, si se inicia desde el principio.
Dado que el conjunto de todos los laberintos posibles incluye cada laberinto posible con cada punto de inicio válido posible, esto significa automáticamente que la cadena saldrá de cualquier laberinto desde cualquier punto de inicio válido. Es decir, desde cualquier punto de partida desde el que se pueda alcanzar la salida.
Victorioso
El ganador es la respuesta que proporciona la cadena válida más corta e incluye el código utilizado para producirla. Si más de una de las respuestas proporciona una cadena de esta longitud más corta, gana el primero en publicar esa longitud de cadena.
Ejemplo
Aquí hay una cadena de ejemplo de 500 caracteres de longitud, para darle algo que vencer:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Gracias a orlp por donar esto.
Tabla de clasificación
Los puntajes iguales se enumeran en orden de publicación de ese puntaje. Este no es necesariamente el orden en que se publicaron las respuestas, ya que la puntuación de una respuesta determinada puede actualizarse con el tiempo.
Juez
Aquí hay un validador de Python 3 que toma una cadena de NESW como argumento de línea de comando o mediante STDIN.
Para una cadena no válida, esto le dará un ejemplo visual de un laberinto en el que falla.
fuente
Respuestas:
C ++,
979593918683828179 caracteresMi estrategia es bastante simple: un algoritmo de evolución que puede crecer, reducir, intercambiar elementos y mutar secuencias válidas. Mi lógica de evolución ahora es casi la misma que la de @ Sp3000, ya que la suya fue una mejora sobre la mía.
Sin embargo, mi implementación de la lógica del laberinto es bastante ingeniosa. Esto me permite verificar si las cadenas son válidas a una velocidad vertiginosa. Intenta resolverlo mirando el comentario
do_move
y elMaze
constructor.fuente
do_move
ahora es increíblemente rápido.Python 3 + PyPy,
8280 caracteresDudé en publicar esta respuesta porque básicamente tomé el enfoque de orlp y le di mi propio giro. Esta cadena se encontró comenzando con una solución pseudoaleatoria de longitud 500: se probaron bastantes semillas antes de que pudiera romper el récord actual.
La única nueva optimización importante es que solo miro un tercio de los laberintos. Se excluyen dos categorías de laberintos de la búsqueda:
<= 7
cuadrados son accesiblesLa idea es que cualquier cadena que resuelva el resto de los laberintos también debe resolver lo anterior automáticamente. Estoy convencido de que esto es cierto para el segundo tipo, pero definitivamente no lo es para el primero, por lo que la salida contendrá algunos falsos positivos que deben verificarse por separado. Sin embargo, estos falsos positivos generalmente solo pierden unos 20 laberintos, así que pensé que sería una buena compensación entre velocidad y precisión, y también les daría a las cuerdas un poco más de espacio para respirar para mutar.
Inicialmente, revisé una larga lista de heurísticas de búsqueda, pero horriblemente ninguno de ellos obtuvo nada mejor que 140.
fuente
0
a lon
largo del camino y suponga que esa cadena loS
lleva de0
an
. LuegoS
también te lleva de cualquier celda intermediac
an
. Supongamos lo contrario. Dejea(i)
ser la posición después de losi
pasos que comienzan0
yb(i)
comienzan enc
. Luegoa(0) = 0 < b(0)
, cada paso cambiaa
yb
como máximo 1, ya(|S|) = n > b(|S|)
. Toma la más pequeña det
esa maneraa(t) >= b(t)
. Claramentea(t) != b(t)
o estarían sincronizados, por lo que deben intercambiar lugares paso a pasot
moviéndose en la misma dirección.C ++ y la biblioteca de lingeling
Utilizando un enfoque basado en SAT , pude resolver completamente el problema similar para laberintos 4x4 con celdas bloqueadas en lugar de paredes delgadas y posiciones fijas de inicio y salida en esquinas opuestas. Así que esperaba poder usar las mismas ideas para este problema. Sin embargo, aunque para el otro problema solo usé 2423 laberintos (mientras tanto se ha observado que 2083 son suficientes) y tiene una solución de longitud 29, la codificación SAT usó millones de variables y su resolución tomó días.
Así que decidí cambiar el enfoque de dos maneras importantes:
También hice algunas optimizaciones para usar menos variables y cláusulas unitarias.
El programa se basa en @ orlp's. Un cambio importante fue la selección de laberintos:
is_solution
verifica si se alcanzan todas las posiciones alcanzables.De esta manera, obtengo un total de 10772 laberintos con posiciones de inicio.
Aquí está el programa:
Primero
configure.sh
ymake
ellingeling
solucionador, luego compila el programa con algo comog++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
, dónde...
está el camino dondelglib.h
resp.liblgl.a
son, por lo que ambos podrían ser, por ejemplo../lingeling-<version>
. O simplemente colóquelos en el mismo directorio y no use las opciones-I
y-L
.El programa toma un argumento de línea de comandos obligatoria, una cadena que consiste en
N
,E
,S
,W
(para direcciones fijas) o*
. Por lo tanto, puede buscar una solución general de tamaño 78 dando una cadena de 78*
s (entre comillas), o buscar una solución comenzando con elNEWS
usoNEWS
seguido de tantos*
s como desee para pasos adicionales. Como primera prueba, tome su solución favorita y reemplace algunas de las letras*
. Esto encuentra una solución rápida para un valor sorprendentemente alto de "algunos".El programa le dirá qué laberinto agrega, descrito por la estructura de la pared y la posición de inicio, y también le dará la cantidad de posiciones y paredes alcanzables. Los laberintos se ordenan según estos criterios, y se agrega el primero sin resolver. Por lo tanto, la mayoría de los laberintos añadidos tienen
(9/4)
, pero a veces otros también aparecen.Tomé la solución conocida de longitud 79, y para cada grupo de 26 letras adyacentes, traté de reemplazarlas con 25 letras. También intenté eliminar 13 letras del principio y del final, y reemplazarlas por 13 al principio y 12 al final, y viceversa. Desafortunadamente, todo salió insatisfactorio. Entonces, ¿podemos tomar esto como un indicador de que la longitud 79 es óptima? No, igualmente intenté mejorar la solución de longitud 80 a longitud 79, y eso tampoco fue exitoso.
Finalmente, intenté combinar el comienzo de una solución con el final de la otra, y también con una solución transformada por una de las simetrías. Ahora me estoy quedando sin ideas interesantes, así que decidí mostrarte lo que tengo, a pesar de que no condujo a nuevas soluciones.
fuente