Sie sind Ruby, ein Eisenbahningenieur. Deine Aufgabe ist es, in einem beliebigen Tal eine Spur zu finden, die jede Station besucht ( M
). Die verlegte Gleismenge ist nicht wichtig, muss jedoch auf einem durchgehenden Pfad verlegt werden, der am Talein- / ausgangspunkt ( >
) beginnt und endet und sich an keinem Punkt kreuzt. Es gibt noch ein paar andere Einschränkungen: Berge ( ^
) sind unpassierbar, sodass Sie sie umgehen müssen, Flüsse ( ~
) müssen mit einer Brücke ( X
) überquert werden und der Rand des Tals ( #
) ist ebenfalls unpassierbar.
Die Regeln der Strecke
Wenn das Gleis nicht richtig verlegt ist, kommt es zu Entgleisungen, und das will niemand. Hier sind die Regeln für die Gleisplatzierung.
Es gibt vier Arten von Spur: -
|
/
\
.
So kann jeder mit dem anderen kombiniert werden:
Zulässige Kombinationen von -
(in der Mitte jedes Beispiels):
##### ##### ##### ##### ##### ##### #####
# # # # #\ # # # # /# #\ /# # #
#---# # --# # --# #-- # #-- # # - # # - #
# # #/ # # # # \# # # # # #/ \#
##### ##### ##### ##### ##### ##### #####
-
darf niemals kombiniert werden mit |
. Dies ist eine zu scharfe Kurve, als dass die Züge sicher fahren könnten.
Zulässige Kombinationen von /
(in der Mitte jedes Beispiels):
##### ##### ##### ##### ##### ##### #####
# /# # -# # |# # /# # /# # -# # |#
# / # # / # # / # # / # # / # # / # # / #
#/ # #/ # #/ # #| # #- # #| # #- #
##### ##### ##### ##### ##### ##### #####
\
darf niemals kombiniert werden mit /
. Dies ist eine zu scharfe Kurve, als dass die Züge sicher fahren könnten.
Zulässige Kombinationen von \
(in der Mitte jedes Beispiels):
##### ##### ##### ##### ##### ##### #####
#\ # #- # #| # #\ # #\ # #- # #| #
# \ # # \ # # \ # # \ # # \ # # \ # # \ #
# \# # \# # \# # |# # -# # |# # -#
##### ##### ##### ##### ##### ##### #####
Zulässige Kombinationen von |
(in der Mitte jedes Beispiels):
##### ##### ##### ##### ##### ##### #####
# | # #\ # # /# # | # # | # # /# #\ #
# | # # | # # | # # | # # | # # | # # | #
# | # # | # # | # #/ # # \# # \# #/ #
##### ##### ##### ##### ##### ##### #####
Tracks können auf folgende Weise mit den Stationen, Brücken und Taleingängen / -ausgängen kombiniert werden:
##### ##### #####
#\|/# #\|/# #/ #
#-M-# #-X-# >- #
#/|\# #/|\# #\ #
##### ##### #####
Bahnhöfe haben Drehtische, daher ist es zulässig, einen Bahnhof in einem spitzen Winkel zu verlassen (allerdings nicht in der Richtung, in der Sie gekommen sind - Sie möchten nicht in den nächsten planmäßigen Zug stürzen, der in die andere Richtung fährt!).
Brücken sind zum Überqueren von Flüssen gedacht. Sie müssen also die Brücke auf der gegenüberliegenden Seite des Flusses verlassen, auf den Sie sie betreten haben.
Eingang
Die Eingabe erfolgt über STDIN für Programme oder über ein Funktionsargument für Funktionen. Wenn Ihre Funktion einen Namen benötigt, damit ich ihn für meine Eingabe ausführen kann, sollte diese Namensdeklaration in die Byteanzahl einbezogen werden.
Die Eingabe ist eine einzelne Zeichenfolge mit Zeilenumbrüchen. Jede Zeile in Ihrer Eingabe hat immer die gleiche Länge wie die anderen, sodass Sie eine rechteckige Eingabe erhalten. Die Kante der Eingabe ist #
bis auf den Eintrittspunkt immer durchgehend und unpassierbar ( ). Jede Eingabe hat mindestens eine gültige Antwort.
Ausgabe
Ihre Ausgabe sollte als einzelne Zeichenfolge mit Zeilenumbrüchen von einer Funktion zurückgegeben oder für vollständige Programme ausgedruckt / auf dem Bildschirm angezeigt werden.
Die Ausgabe sollte mit der Eingabe identisch sein, jedoch mit den hinzugefügten Spurzeichen.
Wertung
Gewinner ist der kürzeste Code in Bytes.
Testfälle
###########
# M #
# ^ #
> ^^ M #
# ^ #
#~~~~~~~~~#
# M #
# ^^ #
# M#
###########
#################
# #
# M M #
# ^ #
# ^ M #
#~~~~~~~^ #
# #
# ^ #
# M^ #
# ^ #
> ^^^ M#
# #
# M #
#################
###############
# M ~ #
# ~ #
> ~ M #
# ~ #
# ~ #
# ~ #
###############
Mögliche Lösungen für Testfälle
###########
# ---M #
#/ ^ \ #
> ^^ M #
#\ ^ | #
#~X~~~~X~~#
# M \ #
# \ ^^ |#
# -----M#
###########
#################
# #
# M---------M #
# | ^ / #
# / ^ M- #
#~X~~~~~^ | #
# | \ #
# \^ \ #
# --M^ \ #
#/ ^ |#
> ^^^ M#
#\ / #
# -------M---- #
#################
###############
# M ~ #
#/ \ ~ #
> --X----M #
#\ ~ | #
# \ ~ / #
# ---X--- #
###############
Antworten:
Python 2 ,
3990343044124313 BytesDies ist im Grunde ein A * mit einer hässlichen Heuristik und einer hässlichen
getChildren
Methode. Um die 3 Testfälle nacheinander ausführen6.5s
zu können, muss ich auf meinem Computer arbeiten. Die Funktionf
ist hier die Lösung. Es nimmt die Map als String und gibt die gelöste Map als String zurück.Probieren Sie es online!
Testfälle
Test 1
Test 2
Test 3
Quellcode
A * State + A * Solver-Klasse
Diese habe ich tatsächlich aus meiner Lösung heraus golfen. Aber sie existieren in meiner "lesbaren" Version. Die State-Klasse ist generisch und soll implementiert werden. Die Solver-Klasse nimmt einen Startzustand an und folgt dann dieser Zustandsheuristik
getDist
.State Class
Dies ist die Implementierung der A * -Zustandsklasse. Die wichtigste Methode hierbei ist
getDist
die Heuristik zur Bestimmung, wie nahself
das Ziel ist. Grundsätzlich ist dies die Mindestentfernung, um alle verbleibenden Ziele zu besuchen und zum Start zurückzukehren.Kartenklasse
Diese Klasse speichert und verarbeitet die Karte. Die
isConnected
Methode ist wahrscheinlich das wichtigste Stück. Es wird geprüft, ob 2 Gleisstücke verbunden sind.Aktualisierung
;
squelle
elif e!=""and e in"MX>"
könnten zu einer einzigen Zeile mit einem Ternär zusammengefasst werdenif else
. Auchdef
könnten einige Ihrer slambda
s sein. Wie es seindef A(s):return str(s)
kannA=lambda s:str(s)
, oder wenn Sie von__str__
zu wechseln__repr__
, können Sie verwendenA=lambda s:`s`
, an welchem Punkt es nicht einmal wert ist,A
als eigene Funktion zu haben, da es Klammern erfordert, um aufzurufen. Verwenden Sie stattdessen Backticks.