Das Spiel
Die meisten von uns kennen Frogger , das Arcade-Spiel aus den 80er Jahren, bei dem es darum geht, einen Frosch sicher über eine stark befahrene Autobahn und einen mit Gefahren gefüllten Teich zu hüpfen, um sicher zu Hause anzukommen.
Vor einigen Monaten wurde die Herausforderung gestellt , einen Frogger-Klon zu entwickeln. Aber warum Frogger klonen, wenn Sie Frogger spielen können ? :) :)
Betrachten Sie das folgende vereinfachte Spielraster:
XXXXXXXXXXXXXXXXXXXXXXX North Safe Zone
-----------------------
| | <<<< Express Lane West (Lane 1)
| | > Gridlock East (Lane 2)
| | << Freeflowing Traffic West (Lane 3)
| | < Gridlock West (Lane 4)
| | >>>> Express Lane East (Lane 5)
-----------------------
XXXXXXXXXXX@XXXXXXXXXXX South Safe Zone
\__________ __________/
'
23 cells horizontally
Wir haben fünf Fahrspuren mit jeweils 23 Zellen Breite und zwei Sicherheitszonen (in denen sich der Frosch sicher nach links und rechts bewegen kann), ebenfalls 23 Zellen breit. Sie können den rechten und den linken Rand ignorieren, da diese der Übersichtlichkeit dienen.
Unser Frosch beginnt in der südlichen Sicherheitszone in der mittleren (12.) Zelle, wie @in der obigen Abbildung durch a angegeben .
Die Zeit im Spiel ist in diskrete Schritte unterteilt, die als Frames bezeichnet werden. Froggy ist ein schneller Frosch und kann pro Bild eine Zelle in jede Richtung (nach oben, unten, rechts, links) hüpfen. Er kann sich auch dafür entscheiden, für jeden Rahmen stationär zu bleiben. Der Verkehr auf den fünf Fahrspuren bewegt sich wie folgt mit konstanter Geschwindigkeit:
- Der Verkehr auf der Express-Spur nach Westen (Spur 1) bewegt 2 Zellen nach links in jedem Frame
- Der Verkehr auf der Stau-Ostspur (Spur 2) bewegt jede Sekunde 1 Zelle nach rechts
- Der Verkehr in der Westspur mit frei fließendem Verkehr (Spur 3) bewegt sich in jedem Frame um 1 Zelle nach links
- Der Verkehr auf der Westspur (Spur 4) bewegt sich in jedem zweiten Frame um 1 Zelle nach links
- Der Verkehr auf der Express-Spur nach Osten (Spur 5) bewegt 2 Zellen in jedem Frame nach rechts
Der Verkehr selbst ist für ca. 3.000 Zeitschritte in dieser Textdatei . "Verkehr" besteht aus Fahrzeugen und Zwischenräumen zwischen den Fahrzeugen. Jedes Zeichen, das kein Leerzeichen ist, ist Teil eines Fahrzeugs. Die Textdatei enthält fünf Zeilen, die den fünf Fahrspuren entsprechen (mit derselben Reihenfolge).
Für die nach Westen führenden Fahrspuren betrachten wir zu Beginn von Frame 0 (dem Beginn des Spiels), dass sich das erste Fahrzeug auf der Fahrspur direkt hinter dem rechten Rand des Spielgitters befindet.
Bei Fahrspuren in Richtung Osten sollte die Verkehrszeichenfolge als "rückwärts" betrachtet werden, da die Fahrzeuge am Ende der Zeichenfolge erscheinen. Zu Beginn von Frame 0 betrachten wir das erste Fahrzeug in diesen Fahrspuren als knapp hinter dem linken Rand des Spielfelds.
Betrachten Sie als Beispiel:
Traffic Lane 1: [|==| =
Traffic Lane 2: |) = o
Traffic Lane 3: (|[]-[]:
Traffic Lane 4: <| (oo|
Traffic Lane 5: |==|] :=)
Dann erscheint das Spielraster wie folgt:
Start of Frame 0 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 1 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 2 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Start of Frame 3 XXXXXXXXXXXXXXXXXXXXXXX
[|==| =
|) = o
(|[]-[]:
<| (oo|
|==|] :=)
XXXXXXXXXXXXXXXXXXXXXXX
Nachdem der gesamte Verkehr in einer Spur "erschöpft" ist (dh die Zeichenfolge läuft ab), betrachten wir alle Zeichen in der Zeichenfolge als Leerzeichen.
Unser Frosch wird gequetscht, wenn eines der folgenden Ereignisse eintritt:
- Der Frosch besetzt eine Zelle, die von einem Fahrzeug besetzt ist, auf einem beliebigen Rahmen
- Der Frosch bleibt auf einer Schnellstraße stehen und ein Fahrzeug mit einer Zellenbreite fährt in diesem Rahmen über ihn hinweg
- Der Frosch springt nach Osten "durch" ein Fahrzeug in Richtung Westen oder nach Westen durch ein Fahrzeug in Richtung Osten
- Der Frosch springt außerhalb des 7 (Linie) mal 23 (Zelle) Spielgitters auf einem beliebigen Bild
Beachten Sie, dass dies die einzigen Bedingungen sind, unter denen ein Frosch gequetscht wird. Insbesondere ist ein Frosch, der mit dem Verkehr "hüpft", zulässig, ebenso wie ein Frosch, der in einer Express-Spur, die von einem Fahrzeug der Breite 1 im selben Rahmen überfahren wird, in eine Zelle hinein oder aus dieser heraus springt.
Ziel und Wertung
Ziel der Programmieraufgabe ist es, den Frosch so oft wie möglich über die Straße zu bringen, bevor das letzte Fahrzeug das Spielfeld verlässt . Das heißt, das Programm wird unmittelbar nach Abschluss von Rahmen X beendet , wobei Rahmen X der erste Rahmen ist, der das Gitter in einen Zustand versetzt, in dem keine Fahrzeuge mehr vorhanden sind.
Die Ausgabe Ihres Programms sollte eine Zeichenfolge (oder Textdatei) sein, die die Abfolge der Bewegungen für den Frosch mit der folgenden Codierung enthält:
< frog moves left
> frog moves right
^ frog moves up
v frog moves down
. frog remains stationary
Beispielsweise zeigt die Zeichenfolge <<^.^an, dass sich der Frosch zweimal nach links, dann nach oben, dann für einen Frame pausiert und dann wieder nach oben bewegt.
Ein Punkt wird erzielt, wenn der Frosch von der südlichen Sicherheitszone in die nördliche Sicherheitszone wechselt, und ein Punkt wird erzielt, wenn der Frosch von der nördlichen Sicherheitszone in die südliche Sicherheitszone wechselt.
Einige wichtige Regeln:
- Der Frosch darf nicht gequetscht werden.
- Bitte veröffentlichen Sie Ihre Lösung (Abfolge der Bewegungen) zusammen mit Ihrem Programmcode, entweder inline oder als Textdatei (z. B. über pastebin.com).
- Unser Frosch ist vorausschauend und vorausschauend, daher kann Ihr Programm alle Verkehrsdaten in jedem Frame verwenden, um nach Lösungen zu suchen. Dies schließt Daten für Verkehr ein, der das Spielraster noch nicht erreicht hat.
- Das Gitter wird nicht umwickelt. Das Verlassen des Gitters führt dazu, dass der Frosch gequetscht wird und ist daher nicht zulässig.
- Zu keinem Zeitpunkt wird der Verkehr "zurückgesetzt" oder der Frosch "teleportiert". Die Simulation ist kontinuierlich.
- Der Frosch kann nach dem Verlassen in die südliche Sicherheitszone zurückkehren, dies wird jedoch nicht als Punkt gezählt. Ebenso für die nördliche Sicherheitszone.
- Der Gewinner des Wettbewerbs ist das Programm, das die Bewegungssequenz mit der höchsten Anzahl von Kreuzungen generiert.
- Für weitere Fragen oder Bedenken wenden Sie sich bitte an den Kommentarbereich.
Für einen zusätzlichen Anreiz werde ich dem Gewinnerprogramm eine Prämie von +100 Wiederholungen hinzufügen , wenn ich dazu in der Lage bin.
Boni
+ 2,5% auf die Basispunktzahl * (bis zu + 10%) für jede Ecke des Spielgitters, die der Frosch berührt. Die vier Ecken des Gitters sind die Zellen ganz links und ganz rechts der beiden Sicherheitszonen.
+ 25% auf die Basispunktzahl *, wenn Ihre Bewegungssequenz den Frosch für die gesamte Simulation auf +/- 4 Zellen links oder rechts von seiner Startzelle beschränkt hält (er kann sich natürlich vertikal frei bewegen).
Kein Punktebonus, aber spezielle Requisiten im OP gehen an alle, die einen schnellen und schmutzigen Lösungsvalidator veröffentlichen, damit ich keinen programmieren muss. ;) Ein Validator würde einfach eine Folge von Zügen akzeptieren, seine Rechtmäßigkeit (gemäß den Regeln und der Verkehrsdatei) sicherstellen und seine Punktzahl (dh die Gesamtzahl der Überfahrten) melden.
* Die Gesamtpunktzahl entspricht der Basispunktzahl zuzüglich des auf die nächste Ganzzahl abgerundeten Bonus.
Antworten:
C ++: 176
Ausgabe:
Es gibt weniger als 8 Millionen
Zustandskombinationenvon Position X Zeit X Satz besuchter Ecken, sodass sie in weniger als 1 Sekunde vollständig durchsucht werden können. Wenn der Code keine Fehler enthält, sollte es unmöglich sein, ihn zu schlagen. Die optimale Strategie bestand darin, das gesamte Board zu verwenden, da Froggy 160 Mal die Straße überqueren kann, gegenüber etwa 120, wenn es auf das Zentrum beschränkt ist. Der Besuch der Ecken kostete keine Überfahrten, da der Verkehr so stark war.quelle