Eres Ruby, un ingeniero ferroviario. Su tarea es establecer un camino en cualquier valle dado de modo que visite cada estación ( M
). La cantidad de pista establecida no es importante, pero debe colocarse en un camino continuo que comienza y termina en el punto de entrada / salida del valle ( >
) y no se cruza en ningún punto. Hay algunas otras limitaciones: las montañas ( ^
) son intransitables, por lo que debe rodearlas, los ríos ( ~
) deben cruzarse con un puente ( X
) y el borde del valle ( #
) también es intransitable.
Las reglas de la pista
Si la pista no se coloca correctamente, habrá descarrilamientos y nadie quiere eso, así que aquí están las reglas sobre la colocación de la pista.
Hay cuatro tipos de vías: -
|
/
\
.
Así es como cada uno se puede combinar con los demás:
Combinaciones permitidas de -
(en el centro de cada ejemplo):
##### ##### ##### ##### ##### ##### #####
# # # # #\ # # # # /# #\ /# # #
#---# # --# # --# #-- # #-- # # - # # - #
# # #/ # # # # \# # # # # #/ \#
##### ##### ##### ##### ##### ##### #####
-
nunca se puede combinar con |
. Este es un giro demasiado brusco para que los trenes lo hagan con seguridad.
Combinaciones permitidas de /
(en el centro de cada ejemplo):
##### ##### ##### ##### ##### ##### #####
# /# # -# # |# # /# # /# # -# # |#
# / # # / # # / # # / # # / # # / # # / #
#/ # #/ # #/ # #| # #- # #| # #- #
##### ##### ##### ##### ##### ##### #####
\
nunca se puede combinar con /
. Este es un giro demasiado brusco para que los trenes lo hagan con seguridad.
Combinaciones permitidas de \
(en el centro de cada ejemplo):
##### ##### ##### ##### ##### ##### #####
#\ # #- # #| # #\ # #\ # #- # #| #
# \ # # \ # # \ # # \ # # \ # # \ # # \ #
# \# # \# # \# # |# # -# # |# # -#
##### ##### ##### ##### ##### ##### #####
Combinaciones permitidas de |
(en el centro de cada ejemplo):
##### ##### ##### ##### ##### ##### #####
# | # #\ # # /# # | # # | # # /# #\ #
# | # # | # # | # # | # # | # # | # # | #
# | # # | # # | # #/ # # \# # \# #/ #
##### ##### ##### ##### ##### ##### #####
Las pistas pueden combinarse con las estaciones, puentes y entrada / salida del valle de las siguientes maneras:
##### ##### #####
#\|/# #\|/# #/ #
#-M-# #-X-# >- #
#/|\# #/|\# #\ #
##### ##### #####
Las estaciones tienen mesas giratorias, por lo que es permisible dejar una estación en un ángulo agudo (aunque no en la dirección en la que viniste, ¡no querrás chocar contra el próximo tren programado que viene en la otra dirección!).
Los puentes son para cruzar ríos, por lo que debe salir del puente en el lado opuesto del río en el que ingresó.
Entrada
La entrada será a través de STDIN para programas o un argumento de función para funciones. Si su función necesita un nombre para poder ejecutarlo en mi entrada, entonces esa declaración de nombre debe incluirse en el recuento de bytes.
La entrada será una sola cadena con saltos de línea. Cada línea dentro de su entrada siempre tendrá la misma longitud que las demás, lo que le dará una entrada rectangular. El borde de la entrada siempre será sólido e intransitable ( #
) excepto el punto de entrada. Cualquier entrada dada tendrá al menos una respuesta válida.
Salida
Su salida debe devolverse como una sola cadena con saltos de línea desde una función, o imprimirse / repetirse en la pantalla para programas completos.
La salida debe ser la misma que la entrada pero con los caracteres de pista agregados.
Puntuación
El ganador será el código más corto en bytes.
Casos de prueba
###########
# M #
# ^ #
> ^^ M #
# ^ #
#~~~~~~~~~#
# M #
# ^^ #
# M#
###########
#################
# #
# M M #
# ^ #
# ^ M #
#~~~~~~~^ #
# #
# ^ #
# M^ #
# ^ #
> ^^^ M#
# #
# M #
#################
###############
# M ~ #
# ~ #
> ~ M #
# ~ #
# ~ #
# ~ #
###############
Posibles soluciones para probar casos
###########
# ---M #
#/ ^ \ #
> ^^ M #
#\ ^ | #
#~X~~~~X~~#
# M \ #
# \ ^^ |#
# -----M#
###########
#################
# #
# M---------M #
# | ^ / #
# / ^ M- #
#~X~~~~~^ | #
# | \ #
# \^ \ #
# --M^ \ #
#/ ^ |#
> ^^^ M#
#\ / #
# -------M---- #
#################
###############
# M ~ #
#/ \ ~ #
> --X----M #
#\ ~ | #
# \ ~ / #
# ---X--- #
###############
Respuestas:
Python 2 ,
3990343044124313 bytesEsto es básicamente un A * con un
getChildren
método feo y heurístico feo . Para ejecutar los 3 casos de prueba de forma consecutiva toma6.5s
mi máquina. La funciónf
es la solución aquí. Toma el mapa como una cadena y devuelve el mapa resuelto como una cadena.Pruébalo en línea!
Casos de prueba
Prueba 1
Prueba 2
Prueba 3
Código fuente
A * Estado + A * Clase de solucionador
De hecho, los saqué de mi solución. Pero existen en mi versión 'legible' . La clase de estado es genérica y está destinada a implementarse. La clase Solver toma un estado inicial y luego sigue los estados heurísticos
getDist
.Clase de estado
Esta es la implementación de la clase de estado A *. El método más importante aquí es
getDist
la heurística para determinar qué tan cercaself
está de la meta. Básicamente es la distancia mínima para visitar todos los destinos restantes y volver a comenzar.Clase de mapa
Esta clase almacena y procesa el mapa. El
isConnected
método es probablemente la pieza más importante. Prueba para ver si hay 2 piezas de pista conectadas.Actualizaciones
;
sfuente
elif e!=""and e in"MX>"
podrían combinarse en una sola línea con un ternarioif else
. Además, algunos de susdef
s podrían serlambda
s. Me gustadef A(s):return str(s)
puede serA=lambda s:str(s)
, o si cambia de__str__
a__repr__
, puede usarA=lambda s:`s`
, en ese punto, ni siquiera vale la pena tenerloA
como su propia función, ya que requiere paréntesis para llamar. Solo usa backticks en su lugar.