Su tarea es interpretar los roles de ambos personajes en esta escena desde el inicio. En él, Cobb le da a Ariadne un desafío:
Tienes dos minutos para diseñar un laberinto que lleva un minuto resolver.
Se tomarán algunas libertades con esa descripción. Lo más importante, este desafío no se basa en el tiempo, sino que los puntajes se basan en la efectividad de sus laberintos y solucionadores de laberintos.
Pido disculpas por las muchas ediciones a este desafío mientras iteramos hacia un formato fácil y justo.
Parte I: formato de laberinto
Todos los laberintos son cuadrados. Una celda en el laberinto se representa como una tupla indexada a cero row column
.
Las paredes están representadas por dos cadenas binarias: una para paredes horizontales (que bloquean el movimiento entre filas) y paredes verticales (viceversa). En un NxN
laberinto, hay Nx(N-1)
posibles paredes de cada tipo. Tomemos un ejemplo de 3x3 donde las celdas están etiquetadas:
A B | C
---
D | E F
---
G H | I
todas las posibles paredes verticales son: AB BC DE EF GH HI
. Traducido a una cadena, las paredes que se muestran son 011001
para paredes verticales y 010010
para paredes horizontales. Además, por "cadena binaria" me refiero a "los caracteres '0' y '1'".
El formato de laberinto completo es una cadena que contiene, en este orden:
- anchura
- iniciar la tupla celular
- tupla celular final
- paredes horizontales
- paredes verticales
Por ejemplo, este laberinto:
0 1 2 3 4
_________
0 | | E| _|
1 | _|_|_ |
2 |_ _ _ | |
3 | _ _ | |
4 |____S|___|
start:(4,2)
end:(0,2)
está formateado para esto:
5
4 2
0 2
00001011101110001100
10100110000100010010
Parte II: El Arquitecto
El programa Arquitecto crea el laberinto. Debe cumplir con las reglas y proporcionar un laberinto válido (uno donde exista una solución y el final no esté encima del inicio).
Entrada: dos enteros positivos:
size [random seed]
¿Dónde size
estará [15, 50]
? Se le recomienda que utilice la semilla aleatoria para poder reproducir las coincidencias, aunque no es obligatorio.
Salida: Un laberinto válido de tamaño x tamaño (cuadrado) usando el formato descrito en la Parte I. "válido" significa que existe una solución, y la celda inicial no es igual a la celda final.
La puntuación de un arquitecto en un laberinto dado es
# steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))
Por lo tanto, los arquitectos son recompensados por laberintos complejos, pero penalizados por cada muro construido (esto es un sustituto de la restricción de tiempo de Ariadne). La dist()
función garantiza que un laberinto sin paredes no obtenga una puntuación infinita. Los bordes exteriores del laberinto no contribuyen al conteo de paredes.
Parte III: El Solucionador
El Solver intenta resolver laberintos generados por los arquitectos de otros. Hay una especie de niebla de guerra: solo se incluyen las paredes adyacentes a las celdas visitadas (todas las demás se reemplazan con '?')
entrada: el mismo formato de laberinto, pero con '?' donde los muros son desconocidos, una línea adicional para la ubicación actual y una lista separada por comas de opciones válidas de esta ubicación. (Esta es una gran edición que pretende simplificar la escritura de una función de análisis de laberintos)
ejemplo (igual que el laberinto 5x5 anterior después de dar un paso a la izquierda)
5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2
Lo que corresponde a algo como esto, donde ?
está la niebla:
0 1 2 3 4
_________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|
salida: una de las tuplas de la lista de opciones válidas
El puntaje de cada Solucionador es el inverso del puntaje del Arquitecto.
Parte IV: Rey de la colina
Los arquitectos y los solucionadores reciben puntuaciones separadas, por lo que podría haber dos ganadores.
Cada par de arquitectos y solucionadores tendrán muchas oportunidades de burlarse mutuamente. Los puntajes se promediarán en todas las pruebas y oponentes. Al contrario de las convenciones de golf codificadas, ¡el puntaje promedio más alto gana!
¡Tengo la intención de que esto continúe, pero no puedo garantizar que continúen las pruebas para siempre! Digamos por ahora que se declarará un ganador en una semana.
Parte V: Presentación
- Mantengo el poder de veto sobre todas las presentaciones: se recomienda la inteligencia, ¡pero no si se rompe la competencia o mi computadora! (Si no puedo decir qué hace su código, probablemente lo vetaré)
- Proponga un nombre para su par Arquitecto / Solucionador. Publique su código junto con instrucciones sobre cómo ejecutarlo.
Próximamente: un kit de prueba de Python actualizado para el nuevo formato. Se produjeron grandes cambios para permitir el envío de cualquier idioma.
fuente
Respuestas:
BuildFun y SolveFun
Bueno, esto tomó bastante tiempo y no estoy completamente seguro de si el solucionador está haciendo trampa o no. Si bien tiene acceso a todo el laberinto todo el tiempo, solo mira la celda en la que se encuentra, las paredes que lo rodean y, si no hay una pared entre ellas, las celdas adyacentes. Si esto va en contra de las reglas, avíseme e intentaré cambiarlo.
De todos modos, aquí está el código:
Me doy cuenta de que esto es ridículamente largo y no es particularmente fácil de leer, pero soy vago, así es como se mantiene.
BuildFun
El arquitecto, BuildFun, es un programa generador de laberintos bastante simple que siempre creará un laberinto 'perfecto' (uno sin bucles y donde dos puntos siempre tendrán exactamente un camino entre ellos). Basa su lógica en la entrada de semilla, lo que significa que los laberintos generados son seudoaleatorios con lo que a menudo parecen ser patrones repetitivos y, con la misma semilla y tamaño, se creará el mismo laberinto.
Una vez que se genera el laberinto, el programa intentará maximizar la puntuación del laberinto buscando el punto de inicio y el punto final que resulten en el camino más largo entre ellos. Para hacer esto, recorre cada punto de inicio, extiende los trazadores para encontrar el punto final más alejado de él y selecciona la combinación con el camino más largo.
Después de esto, dibuja el laberinto, cuenta las paredes y genera la información del laberinto. Este es el punto de inicio, el punto final, la distancia entre ellos, el número de paredes y la puntuación. También formatea esta información en el estilo descrito anteriormente para tamaño, inicio y final, paredes horizontales y paredes verticales, y la guarda en un archivo de texto llamado Maze.txt para su uso posterior.
SolveFun
El solucionador, SolveFun, utiliza el archivo de texto Maze.txt como entrada y funciona de manera muy similar al arquitecto. Para cada movimiento, elegirá una dirección en la que quiere ir en función de su posición relativa hasta el final y luego mirará las paredes que lo rodean. Si no hay un muro allí, verificará si ha estado en la celda adyacente y, de lo contrario, se agregará como posible opción. Luego se moverá en la dirección más cercana a su dirección preferida, siempre que tenga opciones. Si no tiene opciones, retrocederá hasta que lo tenga. Esto continúa hasta que llega al final.
A medida que se mueve, registra la ruta que está tomando en la ruta variable que se utiliza al final para generar el número total de pasos. También registra la cantidad de veces que tuvo que retroceder para calcular los pasos desperdiciados al final. Cuando llegue al final, dará salida al laberinto con el camino más corto de principio a fin marcado con
*
s.Como correr
Debido al método de salida del laberinto (que incluye subrayar ciertos caracteres), esto debe ejecutarse desde una línea de comando en el formulario
python -c 'import filename;filename.BuildFun(Size, Seed)'
y
python -c 'import filename;filename.SolveFun()'
donde Size es un número entero entre 15 y 50 (inclusive) y Seed es un número entero entre 4 y Size (inclusive).
fuente