Eres un raton Todos tus amigos del ratón han sido capturados, y están inconscientes y atrapados en un laberinto que solo tiene una entrada / salida. Tienes un mapa perfecto del laberinto, por lo que puedes trazar una solución para apresurarte y llevarlos a todos a un lugar seguro. Sin embargo, el laberinto está protegido con un sistema de seguridad que activará una alerta si 1000
se alcanza un umbral de , lo que hace que seas capturado y falles en tu misión de rescate.
De sus investigaciones anteriores sobre el laberinto, cada cuadrado que pisa (es decir, cada movimiento horizontal o vertical, los ratones no pueden moverse en diagonal ) se suma 1
al contador del sistema de seguridad. Sin embargo, si lleva un peso (ya sea un bloque de dinamita o un ratón amigo inconsciente), en su lugar se agrega, 2
ya que detecta la presión adicional. La plaza de entrada / salida no tiene este sistema de seguridad, por lo que no se agrega al mostrador.
Tienes un suministro ilimitado de dinamita que has traído a la entrada, por lo que puedes volar todos los muros para liberar a tus amigos. Pero debe tener cuidado al hacerlo, ya que cada explosión se suma 50
al contador por la presión de conmoción. Además, solo puede llevar una cosa a la vez, ya sea un mouse o un bloque de dinamita. Dado que cada bloque de dinamita solo puede detonar un espacio de pared, esto significa que si hay varias paredes en una fila, debe hacer un viaje con las manos vacías de regreso a la entrada para agarrar más.
Ejemplo resuelto
Supongamos que nuestro laberinto se ve así:
######
#M# E#
######
Lo usaré c
para el mostrador. Empezamos por el E
ntrance, movemos quede un solo cuadrado en el ejercicio de la dinamita, c=2
. Nos detonar la dinamita para explotar la pared, c=52
. Nos movemos dos casillas a la izquierda, con las manos vacías, para llegar c=54
, y ahora estamos parados en la casilla del ratón. E
Recogemos a nuestro amigo y volvemos 3 casillas al xit, pero la última casilla no cuenta, ya que no tiene sensores, por lo que solo hay 2 casillas con algo en la espalda. Eso significa que cuando llegamos a la salida con el mouse final c=58
, que es menor que 1000
, y por lo tanto, la misión tiene éxito.
Reto
Dado un laberinto de entrada, salida si usted, el héroe del ratón, puede rescatar con éxito a todos los ratones atrapados dentro de las limitaciones descritas anteriormente, o si la misión es un fracaso.
Entrada
- Un laberinto 2D en cualquier formato aceptable (cadena multilínea, matriz de cadenas, etc.).
- Para este desafío, lo usaré
#
tanto para las paredes interiores como para las exteriores,M
para los amigos del ratón yE
para la entrada. - La entrada nunca estará inmediatamente adyacente a una pared interior (siempre habrá al menos un espacio para moverse libremente).
- Puede sustituir cualquier carácter ASCII imprimible que desee siempre que sea coherente. Esto le permite usar dos símbolos diferentes para las paredes interiores frente a las paredes exteriores, siempre y cuando mantenga la consistencia (por ejemplo, si elige usar
@
para las paredes interiores en su lugar y se va#
hacia el exterior, cada pared interior debe ser@
y cada pared exterior#
) - El laberinto siempre estará completamente delimitado por paredes, pero no es necesariamente rectangular. Si lo desea, puede suponer que el laberinto se rellena con espacios para hacer una entrada rectangular (opcional).
- El laberinto puede tener secciones inalcanzables sin dinamita.
- No puedes dinamitar las paredes exteriores del laberinto.
Salida
Un valor verdadero / falso . Verdad para "Sí, el mouse puede rescatar a cualquier otro mouse" o Falsey para "No, el sistema de alarma se disparará".
Las normas
- Un programa completo o una función son aceptables.
- Las lagunas estándar están prohibidas.
- Este es el código de golf, por lo que se aplican todas las reglas habituales de golf, y gana el código más corto (en bytes).
Ejemplos
Ejemplos verdaderos, separados por líneas en blanco.
#####
#M E#
#####
######
#M# E#
######
########
#E # M#
# # #
# # #
# #
########
#############################
# ## # # #
# M ## M # # #
# ## # M # E #
#M ## # # #
#############################
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############
Ejemplos de Falsey, separados por líneas en blanco
#############################
#M ## ## ## #
# M ## M ## ## #
# ## ## M ## E #
#M ## ## ## #
#############################
#############################
########
########
# # #
# M # M#
########
#####
# M #
#####
#####
#####
#####
###################
# # # ## ## # # #
#M#M#M## E ##M#M#M#
# # # ## ## # # #
###################
#######
######
#####
####
# M#
####
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############
fuente
Respuestas:
Perl,
216215 bytesIncluye +2 para
-0p
Dar entrada en STDIN. Úselo
%
para paredes externas,#
para paredes internas,0
para espacios vacíos,8
para ratones yr
para la posición inicial. Todos los tableros deben estar acolchados para que formen un rectángulo. Puede transformar y ejecutar los ejemplos como:dynamite.pl
:Reemplace los
\xhh
escapes por el puntaje reclamado.El programa no puede manejar de manera realista casos complejos. En particular, no puede manejar ninguno de los casos de falla. Esto se debe a que hay demasiadas formas diferentes de volar las paredes internas o levantar ratones, por lo que la búsqueda se vuelve demasiado amplia y usa demasiada memoria, aunque es al menos lo suficientemente inteligente como para nunca procesar el mismo estado varias veces. El límite de presión debe reducirse a
100
unos tiempos de ejecución y uso de memoria algo soportables.Explicación
Utilizo el patrón de bits de un personaje para representar el estado de un campo:
Por ejemplo, el héroe (
01000000
) que lleva dinamita (00000001
) debe estar en un lugar donde pueda caminar (00010000
) y queremos que todos los valores sean ASCII (00100000
) imprimibles . Tomar el bit a bitor
de todas estas máscaras de bits da01110001
cuál es el código ASCII paraq
. En total esto se convierte en ::El programa solo considerará al héroe moviéndose hacia la derecha (la rotación explicada más adelante se encargará de las otras direcciones). Las máscaras de bits se eligieron cuidadosamente de modo que el héroe siempre esté representado por una letra y un lugar al que pueda moverse por un dígito (excepto el héroe en casa que lleva una víctima, pero nuevamente esto es intencional para que el único movimiento del héroe sea soltar la víctima). Entonces, un héroe que puede avanzar es igualado
/\pL\d/
. La subcadena coincidente debe modificarse para que el héroe y lo que lleva se eliminen del primer personaje y se agreguen al segundo, lo que se puede hacer de manera bitxor
a bit con el mismo valor para ambos personajes. El valor xor consiste en el bit de héroe (01000000
), el bit de dinamita (00000001
) y el bit de mouse de acarreo (00000100
). Juntos ellosor
para01000101
que es ASCIIE
. Entonces, mover al héroe se convierte en:El héroe puede volar una pared si está parado justo frente a ella y lleva dinamita (
q
,s
oy
). El héroe perderá su dinamita (xor
con00000001
) y el muro#
cambiará a un pasaje0
(xor con00010011
), así quePara manejar las otras direcciones, se gira todo el tablero (el tablero girado termina en
$o
):Además de moverse, el héroe también tiene otras elecciones que puede hacer:
Esto se hace por
El tablero está terminado si el héroe está en casa sin llevar nada (
x
) y no hay más víctimas para rescatar (no2
). Esto se puede probar convenientemente usandoUna vez que se resuelve el tablero quiero recordar este estado y al final imprimirlo. Para eso llevo la bandera "está resuelto"
$\
e imprimo eso al final del programa sin imprimir$_
, así queLos estados a procesar a presión 0 se mantienen
@0
, a presión 1,@1
etc. La presión actual se mantiene$%
. Utilizando$n
o algo así sería más corto, pero el código no funciona si la variable no se inicializa a algo, porque de lo contrario será autovivification cambiar$n
a un reference.Looping ARRAY lo largo de los estados a una cierta presión se realiza mediante unafor
y no unamap
causa con unfor
puede extender la matriz mientras aún se está repitiendo y recogerá los nuevos elementos. Esto es necesario porque las rotaciones y las elecciones de campo único del héroe suceden en tiempo 0 y terminan en la misma matriz de presión. Entonces el ciclo para una presión dada es hecho porEsto se repite hasta que la presión alcanza 1000 o se encuentra una solución:
Todo lo que queda es agregar estados recién descubiertos a sus respectivas matrices de presión. Eso se hará por subrutina
f
. Solo queremos agregar un estado si aún no se ha visto. Los estados que se han visto antes se mantienen%a
así:$n
representa la nueva presión para un estado. Lo deduciré del estado que las variables regex todavía tienen como resultado de la acción del héroe que condujo a esta llamada:Esto lleva a la siguiente fórmula para
$n
:Todas las sustituciones obtienen un
r
modificador, por lo que devuelven el estado modificado y dejan solo el estado actual$_
.f
luego se llama en este estado modificado, por lo que obtiene un código comoDebido a que el cálculo de
$n
necesita las variables de expresión regular, deben deshabilitarse por defecto en caso de que las sustituciones no cambien nada (porque no se cumple la condición para activarlas). Tampoco debo recoger ninguna variable regex de un bucle anterior. Por lo tanto, las sustituciones se envuelven en{}
bloques para guardar y restaurar el estado regex. Así es como obtienes declaraciones comoEn particular, la rotación está tan ajustada que llama
f
sin variables regex y obtiene una contribución de presión de 0.Lo único que queda por hacer es cebar
@0
con el estado inicial al inicioEsto está en el bucle principal, por lo que también intenta agregarse
$_
a matrices de presión posteriores, pero dado que el estado inicial ya%a
no estará en nada sucederá.Juntos, todo esto básicamente encuentra la solución más corta usando el algoritmo de Dijkstra . Sin embargo, hay un problema potencial. El código actual no agregará un estado si se redescubre con una presión menor que el primer descubrimiento. No he podido construir un tablero que desencadene esto, pero tampoco he podido demostrar que es imposible.
fuente
JavaScript,
863834785781 bytesGuardado 29 bytes gracias a ETHproductions
Guardado 53 bytes gracias a Jordania
Toma la entrada como una cadena multilínea.
Esto define una función anónima que utiliza una función recursiva
f
para determinar si activa la alarma antes de recuperar todos los ratones.f
regresa1000
si la presión es superior a 1000 (para evitar una recursión sin fin), regresa la presión si no hay más ratones para rescatar y el mouse en la salida, y devuelve la presión mínima de todos los movimientos posibles desde el estado actual de lo contrario. Utiliza una matrizL
para realizar un seguimiento de las posiciones ya visitadas dondeL[pos]==0
se visita, y no está definida si no lo es. Esto puede no ser necesario, pero evita que el mouse haga movimientos inútiles y arroje errores de recursión como mínimo. (Esto significa que debe redefinirL
si está probando esto varias veces)Esto usa el formato en la pregunta además de que requiere que uses un carácter diferente para las paredes externas. (Cualquier otra cosa que no sea
# MEmecd
)Versión más legible:
fuente
s in L|p > 999
.eval
y reemplazándolo@
con$1
(no estoy seguro de si esto funcionará, pero escribe$1
mucho)f
unaf=(...)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...
$1
18 veces, y.replace("@","$1")
es de 18 bytes. No veo una manera de lograrlo.