Vous êtes Ruby, un ingénieur ferroviaire. Votre tâche consiste à tracer la voie dans une vallée donnée de manière à ce qu'elle se rende dans toutes les stations ( M
). Le nombre de pistes posées n’est pas important, mais il doit être tracé dans un chemin continu qui commence et se termine au point d’entrée / sortie de la vallée ( >
) et ne se croise jamais. Il existe quelques autres contraintes: les montagnes ( ^
) sont impraticables, vous devez donc les contourner, les rivières ( ~
) doivent être traversées à l'aide d'un pont ( X
) et le bord de la vallée ( #
) est également impraticable.
Les règles de la piste
Si les rails ne sont pas bien posés, il y aura des déraillements et personne ne le souhaite. Voici donc les règles concernant le placement des rails.
Il existe quatre types de voies: -
|
/
\
.
Voici comment chacun peut être combiné avec les autres:
Combinaisons autorisées à partir de -
(au centre de chaque exemple):
##### ##### ##### ##### ##### ##### #####
# # # # #\ # # # # /# #\ /# # #
#---# # --# # --# #-- # #-- # # - # # - #
# # #/ # # # # \# # # # # #/ \#
##### ##### ##### ##### ##### ##### #####
-
ne peut jamais être combiné avec |
. C'est un virage trop serré pour que les trains puissent se déplacer en toute sécurité.
Combinaisons autorisées à partir de /
(au centre de chaque exemple):
##### ##### ##### ##### ##### ##### #####
# /# # -# # |# # /# # /# # -# # |#
# / # # / # # / # # / # # / # # / # # / #
#/ # #/ # #/ # #| # #- # #| # #- #
##### ##### ##### ##### ##### ##### #####
\
ne peut jamais être combiné avec /
. C'est un virage trop serré pour que les trains puissent se déplacer en toute sécurité.
Combinaisons autorisées à partir de \
(au centre de chaque exemple):
##### ##### ##### ##### ##### ##### #####
#\ # #- # #| # #\ # #\ # #- # #| #
# \ # # \ # # \ # # \ # # \ # # \ # # \ #
# \# # \# # \# # |# # -# # |# # -#
##### ##### ##### ##### ##### ##### #####
Combinaisons autorisées à partir de |
(au centre de chaque exemple):
##### ##### ##### ##### ##### ##### #####
# | # #\ # # /# # | # # | # # /# #\ #
# | # # | # # | # # | # # | # # | # # | #
# | # # | # # | # #/ # # \# # \# #/ #
##### ##### ##### ##### ##### ##### #####
Les voies peuvent se combiner avec les gares, les ponts et l’entrée / la sortie de la vallée des manières suivantes:
##### ##### #####
#\|/# #\|/# #/ #
#-M-# #-X-# >- #
#/|\# #/|\# #\ #
##### ##### #####
Les gares ont des tables tournantes, il est donc permis de laisser une gare à un angle aigu (mais pas dans le sens où vous êtes venu - vous ne voudriez pas vous écraser sur le prochain train programmé venant de l'autre côté!).
Les ponts servent à traverser les rivières, vous devez donc sortir du pont de l'autre côté de la rivière par laquelle vous êtes entré.
Contribution
La saisie se fera via STDIN pour les programmes ou un argument de fonction pour les fonctions. Si votre fonction a besoin d'un nom pour que je puisse l'exécuter sur mon entrée, cette déclaration de nom doit être incluse dans le nombre d'octets.
L'entrée sera une chaîne unique avec des sauts de ligne. Chaque ligne de votre entrée aura toujours la même longueur que les autres, vous donnant une entrée rectangulaire. Le bord de l’entrée sera toujours solide et infranchissable ( #
), sauf pour le point d’entrée. Toute entrée donnée aura au moins une réponse valide.
Sortie
Votre sortie doit être renvoyée sous la forme d'une chaîne unique avec des sauts de ligne d'une fonction ou imprimée / renvoyée à l'écran pour des programmes complets.
La sortie doit être identique à l'entrée mais avec les caractères de piste ajoutés.
Notation
Le gagnant sera le code le plus court en octets.
Cas de test
###########
# M #
# ^ #
> ^^ M #
# ^ #
#~~~~~~~~~#
# M #
# ^^ #
# M#
###########
#################
# #
# M M #
# ^ #
# ^ M #
#~~~~~~~^ #
# #
# ^ #
# M^ #
# ^ #
> ^^^ M#
# #
# M #
#################
###############
# M ~ #
# ~ #
> ~ M #
# ~ #
# ~ #
# ~ #
###############
Solutions possibles aux cas de test
###########
# ---M #
#/ ^ \ #
> ^^ M #
#\ ^ | #
#~X~~~~X~~#
# M \ #
# \ ^^ |#
# -----M#
###########
#################
# #
# M---------M #
# | ^ / #
# / ^ M- #
#~X~~~~~^ | #
# | \ #
# \^ \ #
# --M^ \ #
#/ ^ |#
> ^^^ M#
#\ / #
# -------M---- #
#################
###############
# M ~ #
#/ \ ~ #
> --X----M #
#\ ~ | #
# \ ~ / #
# ---X--- #
###############
Réponses:
Python 2 ,
3990343044124313 octetsCeci est fondamentalement un A * avec une heuristique laide et une
getChildren
méthode laide . Pour exécuter les 3 cas de test consécutivement prend6.5s
sur ma machine. La fonctionf
est la solution ici. Il prend la carte sous forme de chaîne et renvoie la carte résolue sous forme de chaîne.Essayez-le en ligne!
Cas de test
Test 1
Test 2
Test 3
Code source
Classe A * State + A * Solver
En fait, je les ai sortis de ma solution. Mais ils existent dans ma version "lisible" . La classe d'état est générique et destinée à être implémentée. La classe de solveur prend un état de départ et suit ensuite cette heuristique des états
getDist
.Classe d'état
C'est l'implémentation de la classe d'état A *. La méthode la plus importante ici est la méthode
getDist
heuristique permettant de déterminer la proximitéself
du but. C’est fondamentalement la distance minimale pour visiter toutes les destinations restantes et revenir au début.Classe de carte
Cette classe stocke et traite la carte. La
isConnected
méthode est probablement la pièce la plus importante. Il teste pour voir si 2 morceaux de piste sont connectés.Mises à jour
;
s utiliséla source
elif e!=""and e in"MX>"
pourraient être combinées en une seule ligne avec un ternaireif else
. En outre, certains de vosdef
s pourraient êtrelambda
s. Commedef A(s):return str(s)
peut l'êtreA=lambda s:str(s)
, ou si vous passez de__str__
à__repr__
, vous pouvez utiliserA=lambda s:`s`
, à ce moment-là, il ne vaut même pas la peine d'avoirA
sa propre fonction, car il faut des parenthèses pour appeler. Utilisez simplement des backticks à la place.