Lo contrataron como asistente de investigación y le pidieron que creara un pequeño programa que construirá laberintos de ratas. La caja de la rata siempre es 62x22 y tiene una entrada (a) y una salida (A) para la rata, como esta (entrada 1):
#######a######################################################
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
#################################################A############
Su programa debe llenar el cuadro con bloques (#) dejando una ruta para la rata, así (salida 1):
#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
#################################################A############
¡Esto es fácil, piensas! Empiezas a escribir un pequeño programa, lleno de confianza. Sin embargo, el Principio Científico ha tenido una nueva idea: quiere que dos ratas naveguen por el laberinto al mismo tiempo. El Dr. Rattanshnorter explica que tienen diferentes puertas y diferentes salidas (entrada 2):
#b#####a######################################################
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# B
# #
#################################################A############
Las ratas han sido entrenadas para moverse en línea recta a través de las intersecciones cruzadas, pero las intersecciones en T las dejan confusamente irremediables e invalidarán el experimento. Comienzas en tu nueva tarea más compleja cuando el buen Doctor explica un requisito final: las ratas son salvajes entre sí, por lo que si se ven en algún momento, estallará una pelea de ratas y ambos estarán ante el tablero de ética. Ahora se da cuenta de que su programa debería generar un laberinto similar a este (salida 2):
#b#####a######################################################
# ##### ######################################################
# ##### ######################################################
# ##### ####################################### ####
# ##### ####################################### ######### ####
# ##### ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# # ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### B
################################################# ############
#################################################A############
Cuando la rata B llegue a la intersección, la rata A viajará por el corredor para salir de A y se evitará la pelea de ratas.
Reglas:
Su programa debe leer (STDIN o archivo) una entrada como las anteriores y generar (STDOUT o archivo) los mismos datos, excepto que ahora muchos espacios serán hash (#). Puede sustituir cualquier carácter individual (como
;
) en lugar de\n
en la cadena de entrada, pero la cadena de salida aún requiere\n
caracteres. ACTUALIZADOUna ruta de rata debe tener un ancho de un carácter de ancho, a excepción de las intersecciones cruzadas (cada espacio debe tener cero o dos adyacentes ortogonalmente
#
caracteres ). Cada rata debe tener una ruta única clara, excepto las intersecciones cruzadas. No se permiten intersecciones en T.Las ratas se liberan simultáneamente y se mueven a una velocidad constante. En ningún momento deben verse dos o más ratas (estar en la misma columna o fila sin una o más
#
caracteres intermedios).Si no hay solución posible (como puntos de entrada adyacentes), imprima
Impossible\n
y salga.Las entradas y salidas pueden estar en cualquier lado, sin embargo, nunca estarán en las esquinas.
Si una entrada y una salida coincidentes son adyacentes (por ejemplo:)
##aA##
, la rata no puede ir directamente dea
aA
. Debe haber una pequeña sección de corredor de 2 espacios dentro del área del laberinto.En el turno donde una rata alcanza su punto de salida (o en cualquier momento después de eso), ya no es visible para otras ratas.
Su programa puede estar diseñado para calcular laberintos para 1, 2, hasta 26 ratas.
Las lagunas estándar no están permitidas.
Puntuación:
Con su solución, nomine cuántas ratas por laberinto (N) puede resolver su programa. Su puntaje es la longitud de su código en bytes dividido por este número N.
Incluya una salida de muestra en su respuesta para que podamos ver qué produce su programa.
Respuestas:
Haskell, 26 ratas ?, ~ 5000 bytes
Teóricamente, este código debería funcionar para cualquier cantidad de ratas, pero no ofrezco ninguna garantía de que terminará antes de la muerte por calor del universo. Se basa en un algoritmo de retroceso que intenta ir primero por la ruta recta y luego cambiar de ruta si la ruta no funciona. El número de alternativas es exponencial con respecto a la longitud del camino y el número de ratas.
Todavía no me he molestado en jugar golf, ya que es muy grande y porque primero quiero hacerlo más rápido.
Salida de muestra, 6 ratas:
fuente
b
llega a la intersección dee
yb
, no es visto por éle
?b
parece llegar a esot = 11
, lo que pondríae
todavía en ese corredor. ¿Me estoy perdiendo de algo?Haskell, 1 rata, 681 personajes
El problema se puede resolver trivialmente para todos los laberintos con una sola rata. Este código también "funciona" para cualquier número de ratas, pero no sigue ninguna de las restricciones en las interacciones entre múltiples ratas y caminos.
Salida de muestra:
Estoy planeando admitir muchas ratas, así que escribí un código genérico, pero aún no he encontrado un buen algoritmo para eso.
parse
extrae una lista de todas las entradas y salidas, con sus coordenadasrats
toma esa lista y la convierte en pares de coordenadas para cada rata.bnds
toma una coordenada en un borde y la mueve a la coordenada más cercana dentro del laberinto.naive
toma una posición inicial y final y devuelve un camino simple entre ellas.main
luego reemplaza todo el espacio en blanco que no está en una ruta con '#'fuente