Die Herausforderung
Der kürzeste Code nach Zeichenanzahl, um Robot dabei zu helfen, das Kätzchen in möglichst wenigen Schritten zu finden.
Golfer, dies ist eine Zeit der Krise - Kätzchen wird vermisst und Robot muss es finden! Der Roboter muss Kitten auf dem kürzesten Weg erreichen. Es gibt jedoch viele Hindernisse, die Robot im Weg stehen, und Sie müssen eine Lösung für ihn programmieren.
Früher hatte Robot ein Programm, das es für ihn ausführte, aber dieses Programm ging verloren und Robot hat kein Backup :(.
Die Laufzeit von Robot ist nicht die beste und die wenigsten Zeichen, die Robot aus dem Quellcode lesen muss, die geringste Verarbeitungszeit, und das bedeutet, dass Kitten schneller gefunden wird!
Der Speicher des Roboters enthält eine Karte des Ortes, an dem er sich gerade befindet. Oben steht für Nord, unten für Süd, rechts für Ost und links für West. Der Roboter befindet sich immer in einem rechteckigen Raum unbekannter Größe, umgeben von Wänden, die #
in seiner Radarkarte dargestellt sind. Bereiche, in die der Roboter eintreten kann, werden durch ein Leerzeichen dargestellt .
Das Radar des Roboters sucht auch nach vielen Hindernissen im Raum und markiert sie mit verschiedenen ASCII-Buchstaben. Der Roboter kann diese Hindernisse nicht überwinden. Das Radar markiert Kätzchen als ASCII-Sonderzeichen K
, während der Standort des Roboters mit gekennzeichnet ist R
.
Das Navigationssystem des Roboters funktioniert folgendermaßen: Er kann ein Richtungsduo und die Anzahl der Bewegungseinheiten verstehen, zu denen er reisen soll, z. B. N 3
"3 Bewegungseinheiten nach Norden". Die Radarkarte des Roboters ist so aufgebaut, dass eine Bewegungseinheit aus einem ASCII-Zeichen besteht. Roboter können nur in 4 Richtungen fahren und nicht diagonal fahren.
Ihre Aufgabe, tapferer Kätzchen-Retter, ist es, die Radarkarte des Roboters einmal zu lesen und die geringste Anzahl von Richtungen mit der geringsten Bewegungsentfernung auszugeben. Robot hat garantiert mindestens einen Weg zu Kitten.
Um sicherzustellen, dass Robot keine Zeit damit verschwendet, ein fehlerhaftes Programm auszuführen, das Robot bei der Suche nach Kitten nicht hilft, ermutige ich Sie, tapferen Kitten-Retter, diese Ausgabe des früheren Programms von Robot zu verwenden, um sicherzustellen, dass keine Zeit für die Suche nach Kitten verschwendet wird!
Testfälle
Input:
######################
# d 3 Kj #
# #
# R #
# q #
######################
Output:
E 13
N 2
Input:
######################
# d r 3 Kj #
# p p #
# T X #
# q s t #
# #
# R o d W #
# #
# g t U #
# #
######################
Output:
N 1
E 10
N 4
E 2
Input:
######################
# spdfmsdlwe9mw WEK3#
# we hi #
# rdf fsszr#
# sdfg gjkti #
# fc d g i #
# dfg sdd #
# g zfg #
# df df #
# xcf R#
######################
Output:
N 1
W 9
N 5
E 4
N 1
E 4
N 1
Die Codezählung umfasst die Eingabe / Ausgabe (dh das vollständige Programm).
quelle
Antworten:
C ++
1002899799 ZeichenHinweis erfordert die Verwendung von C ++ 0x, um das Leerzeichen zwischen>> in Vorlagen zu entfernen.
Es findet die Route mit der minimalen Anzahl von Abbiegungen.
Es
Dijkstra's Algorithm
zur Lösung des Problems des kürzesten Pfades.Zur Unterscheidung mehrerer Routen gleicher Größe hat eine lange gerade Linie weniger Gewicht als mehrere kurze Linien (dies begünstigt Routen mit weniger Abbiegungen).
In besser lesbarer Form:
quelle
Scala 2.8 (451 Zeichen)
... aber es löst keine Bindungen zugunsten der geringsten Anzahl von Richtungen (obwohl es die geringste Anzahl von Schritten findet).
Scala 2.8, 642 Zeichen, löst Bindungen korrekt;
Es wurde ein kürzerer Pfad für das zweite Beispiel als der im Problem angegebene gefunden:
quelle
Python 2.6 (504 Zeichen)
quelle
Python 2.6 (535 Zeichen)
Entpackt auf eine stark misshandelte A * -Implementierung. Liest stdin. Sucht nach Lösungen mit minimaler Gesamtentfernung. Bricht Bindungen, indem es eine minimale Anzahl von Richtungen bevorzugt. Listen bewegt sich zu stdout. Findet Kätzchen.
Ausgepackt :
Die Quelle wurde an einigen Stellen manuell gegolft, um eine kleinere komprimierte Darstellung zu erhalten. Beispielsweise wurde eine for-Schleife über die Kompassrichtungen abgewickelt.
quelle
c ++ - 681 notwendige Zeichen
Es ersetzt zuerst alle Hindernisse auf der Karte durch in
#
s (und ändert die Werte vonK
undR
, um für sehr lange Pfade Headroom im Zeichenraum zu lassen. Dann kritzelt es auf der Karte. Ein iterativer Prozess markiert alle nacheinander zugänglichen Quadrate bis dahin ist in der Lage, das Kätzchen in einem Zug zu erreichen.Nachdem die gleiche Routine zur Überprüfung der Zugänglichkeit verwendet wird, um eine Reihe von Positionen zu finden, die in minimalen Anweisungen zum Start zurückführen.Diese Anweisungen werden durch vorhergehendes Laden in eine Zeichenfolge geladen, so dass sie in der richtigen Reihenfolge drucken.Ich habe nicht die Absicht, weiter Golf zu spielen, da dies die Bindungen nicht richtig löst und nicht einfach angepasst werden kann.
Es fällt weiter aus
produzieren
Mehr oder weniger lesbare Version:
quelle
Ruby - 539 Zeichen
Könnte eine Menge Verbesserung gebrauchen, aber es funktioniert für kürzeste Schritte sowie Richtungen.
quelle
Ruby - 648 Zeichen
Eine andere, die den Test mit der geringsten Anzahl von Richtungen nicht besteht, da mir keine einfache Möglichkeit zum Einbetten in A * einfällt.
quelle