User CarpetPython hat eine neue Version dieses Problems veröffentlicht, bei der heuristische Lösungen aufgrund des größeren Suchraums einen viel größeren Stellenwert haben . Ich persönlich denke, dass diese Herausforderung viel schöner ist als meine. Versuchen Sie es also einmal!
Vektorrennen ist ein süchtig machendes Spiel, das mit einem Stift und einem Blatt Papier mit quadratischen Linien gespielt werden kann. Sie zeichnen eine beliebige Rennstrecke auf das Papier, definieren Start und Ende und lenken dann Ihr punktgroßes Auto rundenbasiert. Gehen Sie so schnell wie möglich ans Ende, aber achten Sie darauf, dass Sie nicht in eine Wand geraten!
Die Strecke
- Die Karte ist ein zweidimensionales Gitter, in dem jede Zelle ganzzahlige Koordinaten hat.
- Sie bewegen sich auf den Gitterzellen.
- Jede Gitterzelle ist entweder Teil der Spur oder eine Wand.
- Genau eine Spurzelle ist die Startkoordinate.
- Mindestens eine Streckenzelle wird als Ziel festgelegt. Die Landung auf einem dieser Felder beendet das Rennen. Mehrere Zielzellen sind nicht unbedingt verbunden.
Das Auto lenken
Ihr Auto startet an einer bestimmten Koordinate und mit einem Geschwindigkeitsvektor (0, 0)
. In jeder Runde können Sie jede Komponente der Geschwindigkeit anpassen ±1
oder so lassen, wie sie ist. Anschließend wird der resultierende Geschwindigkeitsvektor zur Position Ihres Fahrzeugs hinzugefügt.
Ein Bild kann helfen! Der rote Kreis war Ihre Position in der letzten Runde. Der blaue Kreis ist Ihre aktuelle Position. Ihre Geschwindigkeit ist der Vektor vom roten zum blauen Kreis. Abhängig davon, wie Sie Ihre Geschwindigkeit einstellen, können Sie sich in diesem Zug zu einem der grünen Kreise bewegen.
Wenn Sie in einer Mauer landen , verlieren Sie sofort.
Deine Aufgabe
Sie haben es erraten: Schreiben Sie ein Programm, das mit einer Rennstrecke als Eingabe das Auto in möglichst wenigen Runden zu einer der Zielzellen steuert. Ihre Lösung sollte in der Lage sein, mit beliebigen Spuren einigermaßen gut umzugehen, und nicht speziell für die bereitgestellten Testfälle optimiert sein.
Eingang
Wenn Ihr Programm aufgerufen wird, lesen Sie von stdin :
target
n m
[ASCII representation of an n x m racetrack]
time
target
Dies ist die maximale Anzahl von Umdrehungen, die Sie zur Fertigstellung des Tracks ausführen dürfen, und time
das Gesamtzeitbudget für den Track in Sekunden (nicht unbedingt eine Ganzzahl). Einzelheiten zum Timing finden Sie weiter unten.
Für die durch Zeilenumbrüche getrennte Spur werden die folgenden Zeichen verwendet:
#
- WandS
- der Anfang*
- ein Ziel.
- alle anderen Gleisfelder (zB Straße)
Alle Zellen außerhalb des n x m
bereitgestellten Rasters sind implizit Wände.
Der Koordinatenursprung befindet sich in der oberen linken Ecke.
Hier ist ein einfaches Beispiel:
8
4.0
9 6
###...***
###...***
###...***
......###
S.....###
......###
Bei Verwendung der 0-basierten Indexierung wäre die Startkoordinate (0,4)
.
Nach jedem Zug erhalten Sie weitere Eingaben:
x y
u v
time
Wo x
, y
, u
, v
sind alle 0-basierten Zahlen. (x,y)
ist Ihre aktuelle Position und (u,v)
ist Ihre aktuelle Geschwindigkeit. Beachten Sie, dass x+u
und / oder y+v
außerhalb der Grenzen liegen könnte.
time
ist, was von Ihrem Zeitbudget übrig ist, in Sekunden. Fühlen Sie sich frei, dies zu ignorieren. Dies gilt nur für Teilnehmer, die ihre Implementierung wirklich auf das Zeitlimit beschränken möchten.
Wenn das Spiel vorbei ist (weil du in einer Mauer gelandet bist, außerhalb der Grenzen gelandet bist, target
Kurven überschritten hast, die Zeit abgelaufen ist oder das Ziel erreicht hast), erhältst du eine leere Linie.
Ausgabe
Schreibe für jede Runde an stdout :
Δu Δv
wobei Δu
und Δv
jeweils ein von -1
, 0
, 1
. Dies wird hinzugefügt (u,v)
, um Ihre neue Position zu bestimmen. Zur Verdeutlichung lauten die Anweisungen wie folgt
(-1,-1) ( 0,-1) ( 1,-1)
(-1, 0) ( 0, 0) ( 1, 0)
(-1, 1) ( 0, 1) ( 1, 1)
Eine optimale Lösung für das obige Beispiel wäre
1 0
1 -1
1 0
Beachten Sie, dass sich der Controller nicht an stderr anschließt , sodass Sie ihn für jede Art von Debug-Ausgabe verwenden können, die Sie möglicherweise während der Entwicklung Ihres Bots benötigen. Bitte entfernen / kommentieren Sie solche Ausgaben in Ihrem eingereichten Code.
Es kann eine halbe Sekunde dauern, bis Ihr Bot in jeder einzelnen Runde reagiert. Für Runden, die länger dauern, haben Sie ein Zeitbudget (pro Spur) von target/2
Sekunden. Jedes Mal, wenn eine Runde länger als eine halbe Sekunde dauert, wird die zusätzliche Zeit von Ihrem Zeitbudget abgezogen. Wenn Ihr Zeitbudget Null erreicht, wird das aktuelle Rennen abgebrochen.
Neu: Aus praktischen Gründen muss ich ein Speicherlimit festlegen (da der Speicher für vernünftige Spurgrößen begrenzter zu sein scheint als die Zeit). Daher muss ich jeden Testlauf abbrechen, bei dem der Rennfahrer mehr als 1 GB Arbeitsspeicher verwendet, gemessen mit Process Explorer als Private Bytes .
Wertung
Es gibt einen Benchmark von 20 Tracks. Für jeden Track:
- Wenn Sie den Track abgeschlossen haben, entspricht Ihre Punktzahl der Anzahl der Züge, die Sie benötigen, um eine Zielzelle geteilt durch
target
zu erreichen . - Wenn Ihnen die Zeit / das Gedächtnis ausgeht oder Sie das Ziel nicht erreichen, bevor
target
die Runden abgelaufen sind, oder Sie zu einem beliebigen Zeitpunkt in einer Mauer / außerhalb der Grenzen landen, lautet Ihre Punktzahl2
. - Wenn Ihr Programm nicht deterministisch ist, ist Ihre Punktzahl der Durchschnitt über 10 Läufe auf dieser Strecke (bitte geben Sie dies in Ihrer Antwort an).
Ihre Gesamtpunktzahl ist die Summe der Einzelpunktzahlen. Die niedrigste Punktzahl gewinnt!
Darüber hinaus kann (und wird nachdrücklich empfohlen) jeder Teilnehmer einen zusätzlichen Benchmark-Track bereitstellen , der in die offizielle Liste aufgenommen wird. Frühere Antworten werden einschließlich dieses neuen Titels neu bewertet. Dies dient dazu, sicherzustellen, dass keine Lösung zu genau auf die vorhandenen Testfälle zugeschnitten ist, und um interessante Randfälle zu berücksichtigen, die ich möglicherweise übersehen habe (die Sie jedoch möglicherweise bemerken).
Binden brechen
Da es bereits eine optimale Lösung gibt, wird dies wahrscheinlich der Hauptfaktor für die Punktzahl der Teilnehmer sein.
Wenn es ein Unentschieden gibt (aufgrund mehrerer Antworten, die alle Spuren optimal oder auf andere Weise lösen), werde ich zusätzliche (größere) Testfälle hinzufügen, um das Unentschieden zu lösen. Diese werden auf eine feste Art und Weise generiert, um menschliche Vorurteile bei der Erstellung dieser Binder zu vermeiden :
- Ich werde die Seitenlänge
n
im10
Vergleich zum zuletzt auf diese Weise erzeugten Track erhöhen . (Ich kann Größen überspringen, wenn sie die Krawatte nicht brechen.) - Grundlage ist diese Vektorgrafik
- Dies wird mit diesem Mathematica-Snippet in der gewünschten Auflösung gerastert .
- Der Start ist in der oberen linken Ecke. Insbesondere ist dies die Zelle ganz links in der obersten Zeile dieses Spurendes.
- Das Ziel ist in der unteren rechten Ecke. Insbesondere ist dies die Zelle ganz rechts in der untersten Zeile dieses Spurendes.
- Der
target
Wille4*n
.
Der letzte Track des ersten Benchmarks wurde bereits so generiert, mit n = 50
.
Der Controller
Das Programm, mit dem die Einsendungen getestet werden, ist in Ruby geschrieben und befindet sich zusammen mit der von mir verwendeten Benchmark-Datei auf GitHub . Es gibt dort auch einen Beispiel-Bot randomracer.rb
, der einfach zufällige Züge auswählt. Sie können die Grundstruktur als Ausgangspunkt für Ihren Bot verwenden, um zu sehen, wie die Kommunikation funktioniert.
Sie können Ihren eigenen Bot gegen eine Trackdatei Ihrer Wahl wie folgt ausführen:
ruby controller.rb track_file_name command to run your racer
z.B
ruby controller.rb benchmark.txt ruby randomracer.rb
Das Repository enthält außerdem zwei Klassen Point2D
und Track
. Wenn Ihr Beitrag in Ruby verfasst ist, können Sie ihn jederzeit wiederverwenden.
Befehlszeilenoptionen
Sie können Befehlszeilenoptionen hinzufügen -v
, -s
, -t
bevor der Benchmark des Dateinamens. Wenn Sie mehrere Switches verwenden möchten, können Sie dies beispielsweise auch tun -vs
. Das machen sie:
-v
(ausführlich): Verwenden Sie diese Option, um die Debug-Ausgabe des Controllers zu erhöhen.
-s
(lautlos): Wenn Sie Ihre Position und Geschwindigkeit lieber selbst verfolgen möchten und sich nicht um das Zeitbudget kümmern, können Sie diese drei Ausgabezeilen in jeder Runde (an Ihre Übermittlung gesendet) mit dieser Flagge ausschalten.
-t
(Tracks): Ermöglicht die Auswahl einzelner zu testender Tracks. Beispielsweise -t "1,2,5..8,15"
würden nur die Spuren 1, 2, 5, 6, 7, 8 und 15 getestet. Vielen Dank an Ventero für diese Funktion und den Optionsparser.
Ihre Einreichung
Bitte geben Sie in Ihrer Antwort zusammenfassend Folgendes an:
- Ihr Ergebnis.
- Wenn Sie Zufälligkeit verwenden, geben Sie dies bitte an, damit ich Ihre Punktzahl über mehrere Läufe mitteln kann.
- Der Code für Ihre Einreichung.
- Der Speicherort eines kostenlosen Compilers oder Interpreters für die Sprache Ihrer Wahl, der auf einem Windows 8-Computer ausgeführt wird.
- Kompilierungsanweisungen, falls erforderlich.
- Eine Windows-Befehlszeilenzeichenfolge zum Ausführen Ihrer Übermittlung.
- Ob für Ihre Einreichung die
-s
Flagge erforderlich ist oder nicht. - (optional) Ein neuer, lösbarer Track, der dem Benchmark hinzugefügt wird. Ich werde einen vernünftigen
target
für deine Strecke manuell ermitteln. Wenn der Track zum Benchmark hinzugefügt wird, bearbeite ich ihn aus Ihrer Antwort heraus. Ich behalte mir das Recht vor, Sie nach einem anderen Titel zu fragen (nur für den Fall, dass Sie einen unverhältnismäßig großen Titel hinzufügen, obszöne ASCII-Grafiken in den Titel einfügen usw.). Wenn ich den Testfall zum Benchmark-Set hinzufüge, ersetze ich den Track in Ihrer Antwort durch einen Link zum Track in der Benchmark-Datei, um die Unordnung in diesem Beitrag zu verringern.
Wie Sie sehen, werde ich alle Einsendungen auf einem Windows 8-Computer testen. Wenn es absolut keine Möglichkeit gibt, Ihren Beitrag unter Windows zum Laufen zu bringen, kann ich auch eine Ubuntu-VM ausprobieren. Dies ist jedoch erheblich langsamer. Wenn Sie also das Zeitlimit maximieren möchten, stellen Sie sicher, dass Ihr Programm unter Windows ausgeführt wird.
Möge der beste Fahrer vektoriell hervorgehen!
Aber ich will spielen!
Wenn Sie das Spiel selbst ausprobieren möchten, um ein besseres Gefühl dafür zu bekommen, gibt es diese Implementierung . Die Regeln, die dort verwendet werden, sind etwas ausgefeilter, aber sie sind ähnlich genug, um nützlich zu sein, denke ich.
Bestenliste
Letzte Aktualisierung: 01.09.2014, 21:29 UTC
Strecken im Benchmark: 25
Tie-Breaker-Größen: 290, 440
- 6.86688 - Kuroi Neko
- 8.73108 - user2357112 - 2. Einreichung
- 9.86627 - nneonneo
- 10.66109 - user2357112 - 1. Einreichung
- 12.49643 - Ray
- 40.0759 - Pseudonym117 (probabilistisch)
Detaillierte Testergebnisse . (Die Scores für probabilistische Einreichungen wurden separat ermittelt.)
quelle
400
, da dies mit der Art und Weise übereinstimmt, wie ich alle anderen Ziele bestimmt habe (mit Ausnahme des Tie Breakers). Ich werde den Hauptbeitrag aktualisieren, sobald ich alle anderen Beiträge erneut bearbeitet habe.C ++, 5.4 (deterministisch, optimal)
Dynamische Programmierlösung. Nachweislich optimal. Sehr schnell: Löst alle 20 Testfälle in 0,2s. Sollte auf 64-Bit-Rechnern besonders schnell sein. Angenommen, die Tafel hat weniger als 32.000 Stellen in jeder Richtung (was hoffentlich zutreffen sollte).
Dieser Rennfahrer ist etwas ungewöhnlich. Es berechnet den optimalen Pfad an der Startlinie und führt anschließend den berechneten Pfad sofort aus. Sie ignoriert die Zeitsteuerung und geht davon aus, dass sie den Optimierungsschritt rechtzeitig abschließen kann (was für jede einigermaßen moderne Hardware zutreffen sollte). Auf übermäßig großen Karten besteht eine geringe Wahrscheinlichkeit, dass der Rennfahrer einen Fehler macht. Wenn Sie es zu segfault überreden können, erhalten Sie einen Brownie-Punkt, und ich werde es beheben, um eine explizite Schleife zu verwenden.
Kompilieren mit
g++ -O3
. Möglicherweise ist C ++ 11 (für<unordered_map>
) erforderlich . Zum Ausführen führen Sie einfach die kompilierte ausführbare Datei aus (keine Flags oder Optionen werden unterstützt; alle Eingaben erfolgen über stdin).Ergebnisse
Neuer Testfall
quelle
Python 2 , deterministisch, optimal
Hier ist mein Rennfahrer. Ich habe es noch nicht im Benchmark getestet (ich waffle immer noch darum, welche Version und welches Installationsprogramm von Ruby installiert werden soll), aber es sollte alles optimal und unter dem Zeitlimit lösen. Der Befehl zum Ausführen lautet
python whateveryoucallthefile.py
. Benötigt das-s
Controller-Flag.Nachdem ich den Renner von nneonneo untersucht hatte (aber nicht getestet habe, da ich auch keinen C ++ - Compiler besitze), stellte ich fest, dass er eine fast erschöpfende Suche im Zustandsraum durchführt, egal wie nah das Ziel ist oder wie kurz es ist Ein Pfad wurde bereits gefunden. Ich habe auch festgestellt, dass die Zeitregeln bedeuten, dass das Erstellen einer Karte mit einer langen, komplexen Lösung ein langes, langweiliges Zeitlimit erfordert. Somit ist meine Kartenübermittlung ziemlich einfach:
Neuer Testfall
(GitHub kann die lange Reihe nicht anzeigen. Der Track ist
*S.......[and so on].....
)Zusätzliche Einreichung: Python 2, bidirektionale Suche
Dies ist ein Ansatz, den ich vor ungefähr zwei Monaten geschrieben habe, als ich versuchte, meine erste Einreichung zu optimieren. Für die Testfälle, die zu der Zeit existierten, bot es keine Verbesserung, so dass ich es nicht einreichte, aber für Kurois neue Karte scheint es sich gerade noch unter der Speicherkappe hindurchzuquetschen. Ich erwarte immer noch, dass Kurois Löser dies schlägt, aber ich bin daran interessiert, wie es hält.
quelle
n = 400
.) Bitte lassen Sie mich wissen, wenn Sie Optimierungen anwenden, damit ich die Tests wiederholen kann.Python 3: 6.49643 (Optimal, BFS)
Für die alte Benchmark-Datei mit 20 Fällen wurde eine Punktzahl von 5,35643 erreicht. Die Lösung von @nneonneo ist nicht optimal, da es 5.4 bekam. Einige Bugs vielleicht.
Bei dieser Lösung wird BFS zum Durchsuchen des Diagramms verwendet. Jeder Suchstatus hat die Form (x, y, dx, dy). Dann benutze ich eine Karte, um von Staaten zu Entfernungen abzubilden. Im schlimmsten Fall ist die zeitliche und räumliche Komplexität O (n ^ 2 m ^ 2). Dies wird selten passieren, da die Geschwindigkeit nicht zu hoch ist oder der Rennfahrer abstürzt. Tatsächlich kostete es 3 Sekunden auf meinem Computer, alle 22 Testfälle abzuschließen.
# Ergebnisse
quelle
O(√n)
die Ihre ImplementierungO(n³)
auf quadratischen Gittern erfolgen würde (wie bei den anderen, nehme ich an). Ich werde einen Tie-Breaker hinzufügen, um Ihre Einreichung mit der von user2357112 zu vergleichen.n=270
weshalb Sie jetzt hinter den beiden anderen "optimalen" Beiträgen zurückbleiben. Abgesehen davon ist Ihr Beitrag auch der langsamste der drei, wäre also sowieso der dritte gewesen, nur mit einem größeren Tie-Breaker.RandomRacer, ~ 40.0 (gemittelt über 10 Läufe)
Es ist nicht so, dass dieser Bot niemals einen Track beendet, aber definitiv viel seltener als einmal in 10 Versuchen. (Ich erhalte alle 20 bis 30 Simulationen oder so einen Nicht-Worst-Case-Score.)
Dies dient hauptsächlich als Basisfall und um eine mögliche (Ruby-) Implementierung für einen Rennfahrer zu demonstrieren:
Führen Sie es mit
quelle
Random Racer 2.0, ~ 31
Nun, das wird den veröffentlichten optimalen Löser nicht schlagen, aber es ist eine leichte Verbesserung gegenüber einem zufälligen Rennfahrer. Der Hauptunterschied besteht darin, dass dieser Rennfahrer nur willkürlich überlegt, wohin keine Mauer führt, es sei denn, er hat nicht genügend gültige Bewegungsplätze und kann sich in dieser Kurve zu einem Ziel bewegen. Es bewegt sich auch nicht, um an der gleichen Stelle zu bleiben, es sei denn, es ist kein anderer Zug verfügbar (unwahrscheinlich, aber möglich).
In Java implementiert, mit java8 kompiliert, aber Java 6 sollte in Ordnung sein. Keine Befehlszeilenparameter. Es gibt einen ziemlich guten Clusterfick von Hierarchien, also denke ich, dass ich Java richtig mache.
Die Ergebnisse (Bester Fall, den ich gesehen habe)
quelle
.class
irgendeinem Grund aus dem Verzeichnis ausführen musste, in dem sich die Datei befindet (anstelle des Verzeichnisses, in dem sich der Controller befindet). Pingen Sie mich an (mit einem Kommentar), wenn Sie einen Testfall hinzufügen möchten, damit ich ihn zum Benchmark hinzufügen kann. Ihre Punktzahl lag bei 33 über 10 Läufen (siehe Rangliste), dies kann sich jedoch mit jeder neuen Teststrecke ändern, die dem Benchmark hinzugefügt wird.java -cp path/to/class/file VectorRacing