11
1
The Game
Most of us know about Frogger, the 80's era arcade game where the objective is to hop a frog safely across a busy highway and a hazard-filled pond to arrive safely at home.
A challenge was issued some months ago to develop a Frogger clone. But why clone Frogger when you can play Frogger? :)
Consider the following simplified playing grid:
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
We have five lanes of traffic, each 23 cells wide, and two safe zones (where the frog can move safely left and right), also 23 cells wide. You may ignore the right and left borders as these are for pictorial clarity.
Our frog starts in the southern safe zone, on the center (12th) cell, as indicated by a @ in the above figure.
Time in the game is divided into discrete steps called frames. Froggy is a fast frog and can hop one cell in any direction (up, down, right, left) per frame. He may also choose to remain stationary for any frame. The traffic in the five lanes moves at constant speeds as follows:
- the traffic in the express lane west (lane 1) moves 2 cells left every frame
- the traffic in the gridlock east lane (lane 2) moves 1 cell right every second frame
- the traffic in the freeflowing traffic west lane (lane 3) moves 1 cell left every frame
- the traffic in the gridlock west lane (lane 4) moves 1 cell left every second frame
- the traffic in the express lane east (lane 5) moves 2 cells right every frame
The traffic itself is uniquely defined for approx. 3,000 timesteps in this text file. 'Traffic' consists of vehicles and spaces between the vehicles. Any character that is not a space is part of a vehicle. The text file contains five lines, corresponding to the five lanes of traffic (with the same order).
For the westbound lanes, at the start of frame 0 (the start of the game), we consider the first vehicle in the lane to be just beyond the right edge of the playing grid.
For eastbound lanes, the traffic string should be considered "backwards" in the sense that the vehicles appear starting at the end of the string. At the start of frame 0, we consider the first vehicle in these lanes to be just beyond the left edge of the playing field.
Consider as an Example:
Traffic Lane 1: [|==| =
Traffic Lane 2: |) = o
Traffic Lane 3: (|[]-[]:
Traffic Lane 4: <| (oo|
Traffic Lane 5: |==|] :=)
Then the playing grid will appear as follows:
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
After all the traffic in a lane is "depleted" (i.e. the string runs out), we consider all characters in the string to be spaces.
Our frog is squished if any of the following occurs:
- the frog occupies a cell occupied by a vehicle, on any frame
- the frog remains stationary in an express lane and a vehicle of 1 cell width passes over him in that frame
- the frog jumps east "through" a vehicle heading west, or jumps west through a vehicle heading east
- the frog jumps outside of the 7 (line) by 23 (cell) playing grid, on any frame
Note that these are the only conditions under which a frog is squished. In particular, a frog hopping along "with" traffic is permissible, as is a frog jumping into or out of a cell in an express lane that is passed over by a width-1 vehicle in the same frame.
Objective and Scoring
The objective of the programming challenge is to get the frog across the road as many times as possible before the last vehicle exits the playing grid. That is, the program terminates immediately after the completion of frame X, where frame X is the first frame that takes the grid to a state where no more vehicles are present.
The output of your program should be a string (or text file) containing the sequence of moves for the frog using the following encoding:
< frog moves left
> frog moves right
^ frog moves up
v frog moves down
. frog remains stationary
For example, the string <<^.^ indicates that the frog moves left twice, then up, then pauses for one frame, then moves up again.
One point is scored whenever the frog crosses from the south safe zone to the north safe zone, and one point is scored whenever the frog crosses from the north safe zone to the south safe zone.
Some important rules:
- The frog must not be squished.
- Please post your solution (sequence of moves) along with your program code, either inline or as a text file (e.g. using pastebin.com).
- Our frog is prescient and precognizant, hence your program may make use any and all traffic data in any frame while seeking out solutions. This includes data for traffic that hasn't yet reached the playing grid.
- The grid does not wrap around. Exiting the grid will cause the frog to be squished and hence is not permitted.
- At no point does traffic "reset" or the frog "teleport". The simulation is continuous.
- The frog may return to the south safe zone after exiting it, but this is not counted as a point. Likewise for the north safe zone.
- The contest winner is the program that generates the move sequence yielding the highest number of crossings.
- For any additional questions or concerns, please feel free to ask in the comments section.
For some added incentive, I'll add a bounty of +100 rep to the winning program when I'm able to do so.
Bonuses
+2.5% to the base score* (up to +10%) for every corner of the playing grid the frog touches. The four corners of the grid are the leftmost and rightmost cells of the two safe zones.
+25% to the base score* if your sequence of moves keeps the frog confined to within +/- 4 cells left or right of his starting cell for the entire simulation (he can of course move freely vertically).
No scoring bonus, but special props in the OP will go to anyone who posts a quick n' dirty solution validator so that I don't have to program one. ;) A validator would simply accept a sequence of moves, ensure its legality (per the rules and the traffic file), and report its score (i.e. the total number of crossings).
*Total score is equal to base score plus the bonus, rounded down to the nearest integer.
Good luck frogging!
COTO
Posted 2014-09-19T15:44:29.937
Reputation: 3 701
To anyone who wants to post a solution validator: Please don't post it as an answer.
– Geobits – 2014-09-19T17:24:34.380Indeed. A link to the code in a comment, or as an addendum to a solution, would be the preferred way to submit a validator. – COTO – 2014-09-19T18:46:21.063
Shall the first frame in which the slow lanes advance be the same as the first frame in which the other lanes advance, or one frame later? – feersum – 2014-09-20T00:41:54.997
Also, is it possible to score by reaching the endzone on the first frame in which all cars have cleared the field? – feersum – 2014-09-20T04:37:16.077
@feersum: The slow lanes advance one frame later. They remain motionless in the very first frame, as indicated in the example. As for the frog scoring on the very last frame: yes, it is possible. If the frog has moved into a safe zone on the same frame that the last vehicle exits the playing field, one point is scored. – COTO – 2014-09-21T01:53:14.227