11
\$\begingroup\$

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:

  1. The frog must not be squished.
  2. Please post your solution (sequence of moves) along with your program code, either inline or as a text file (e.g. using pastebin.com).
  3. 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.
  4. The grid does not wrap around. Exiting the grid will cause the frog to be squished and hence is not permitted.
  5. At no point does traffic "reset" or the frog "teleport". The simulation is continuous.
  6. 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.
  7. The contest winner is the program that generates the move sequence yielding the highest number of crossings.
  8. 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!

\$\endgroup\$
  • \$\begingroup\$ To anyone who wants to post a solution validator: Please don't post it as an answer. \$\endgroup\$ – Geobits Sep 19 '14 at 17:24
  • \$\begingroup\$ Indeed. A link to the code in a comment, or as an addendum to a solution, would be the preferred way to submit a validator. \$\endgroup\$ – COTO Sep 19 '14 at 18:46
  • \$\begingroup\$ 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? \$\endgroup\$ – feersum Sep 20 '14 at 0:41
  • \$\begingroup\$ Also, is it possible to score by reaching the endzone on the first frame in which all cars have cleared the field? \$\endgroup\$ – feersum Sep 20 '14 at 4:37
  • \$\begingroup\$ @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. \$\endgroup\$ – COTO Sep 21 '14 at 1:53
5
+100
\$\begingroup\$

C++: 176

Output:

176
^^^^^^>vvvvvv>^^^^>^^>>>>>>><<<.vv>v<<<.vvv<<<<<<^.^.^.^.>.>^^<.>>>>>>v>v>.>v<<<<v.<.vv<<<<<^^.<^<<<<<<^.^^>>>>vv>.>.v<v.vv>>^>>^<^<<<<<<<^>.>^^<<<.>>>>>vv>v<vvv<<<<<^^.<^^^^.....vv>.>.>.>v<<vvv<<>>>>^>^<.<.^^>^^>>>>vv.>v<vv.v^>^<.<.<^<^>.>^^>>>>vv.v<<<<<<.vvv<<<<^^^<<v^^.>.^^..>>>>>>vv>.>.v.vvv>>>^>^^<<<<<<<<<^>.>^^>>>>vvv<<v.<.vv<<<<<<>>>>>^^^<<<^^^<<>>vv>.v<<>vvv<<><>>>>>>>^>^^<^^^<.>>>>>>>>vv>.>v<<<vvv<<<<<^^^<<v.<.<^<<^.^<<^...>>>>>>>>>>>>>vv>v<vvv<<<<<<<<^>^.<.^^>.>^^<<<<<<<..>>>>vv>.vvvv<<<<>^.v>>>^^.^^>^<^<>>>>>>>>>vv>vvvv<<<<^^^<^>^<<^.>>vv>v<vvv<<<<<<<>>>>>>>^>^^^.^^>>>>>vvv<<vvv<<<^^^^^^<vvv<<<<<<<vvv<<<>>>>>>>>^^.<.<.^.^.^<^<>>>>>>>>>>vvv<<.vvv<<<^^<^<<^^<<^<<<>>>>vv>.vvvv>>^>>^<.<.<^<<<<<.^^<<^.......>vv.>.>.>v<vvv>>>>>>^>^.<.<^<.^^^<.>>>>>>>vvv<<<v.<vv<<<^^<.<.<.<^<<<^>^^..........v<vvvv>v>>>>>^>>^^^>^^>>>vv>v<vvv<<<<<<<<>^^.<.<^<^^^<.........>vv.>.vvvv>>>>^^<.<.<^^^<^<<.v<v>.>.>.>.>.>.>.vvv.v<<<<<^^<^<^>.>.>.>.^<^.>>>>>>>>vv>v<<vvv<<>>>>>^^^.^.>^<^<<<<<<<<.vv.>.v<<<.vvv<>>>>>^>^.<.<.<.<^^.^<<^<.....>>vvv<.>>vvv<<<>>>>>>>>^^^<<<.^.>.>^^.>>>>>vv.>v<vvv<<<>>>>>>^>^<^<<^.^^<vvv<<<<<vv.v<>>>>>>>>>>^>^.^^>^^<<<<.>vv.>.vvvv>^>>^.<.<.<^<<<^>^^>>>vv>v<<<<<vvv<<<>>>>>^^<.<.<.<.<^<^>.^^.>>>>>vv>v<>vvv<<<<<<<^>^.<^<<<<<<<^^^.>>>>>vv>v<>vvv>>>^^<.<^<<<^>^^.>>>>vv>.v<<vvv<<<<<^^^<<<<<^>.^^<>>>>>>>vv>.>v<<vvv<<<<<<<>>>^>>.>^^^.>^^<>>>>>>vv>vv.<.<.vv>>>>^^<.<.<.<^<<^.>^^.>>>>>vv.>.>v<<vvv<<>>>>>^^<.<.<.^^>.>.>^^<<<<<<<<.>>>>>>vv>v<<v.<.<vv<<<<^^.<^<<<.^^^<.vv.>v<vvv<<<>>>>>>^>^<^<<^.^<^<<.>>vv>.>.>.>vvvv>>>>>>^>^^^^^<<<.vvv<<<<<<vvv>>>>>^>^<.<^<<^.>.>.^^>>>>vv>.>v<<<<<<vvv<<<<^^^<.^.>^^>>>>vvv<<v.vv<<<^>>^^<<<.^^<<^>>>>>>>>>vvv.v.vv<>>>>>^>^^<<<<<<<<<<<<<<<<^^^..>>>>>vv>.>.>.>v<<v.<.<.vv<<<<<^^^<^>.^^...>>>>>>>>vv.v<.vvv>>>^>^<.<^^^^>>>vv>v<<<vvv<<<<>>>>>>^>^.<.<^<^>.>^^.>>>>>vv.v<<<<<<<<vvv<<<<^^<^<<<<<><^>.>^^>>>>vv.>.>.vvv.v>>>>>>>^^<.<^<<^^^>>>vv>.>.>.>.>v<<v.<.<vv>>>>^^^<<<<<.^.>^^>>>vv>.>v<vvv<<<<^^<.<.<.^^>^^>>>vv>.>.v<<<v.<vv<<<<^^.<^<<<^^^>>>>vvvvvv<<<<<<<<>^^.^>>^^^<>>>>>>>vvv<<<v.vv>>>>>^>>^^<<<<<^>.^^>>>>vv>.>v<<<<vvv<<<^^<.<.<.<^<<<<<^>^^>>>>vv.>vv.v.v<^>.>^.<.^^^^>>>>vv>.>.>.v<<<<<<vvv>>>>^^<.<.<^<<^^<^>>>>>>vv>v<<.vvv^>^^<<<^>^^<<<<<<.vvv<<vv>.v>>>>>>^>.>^^<<<<<^>.>.>.>.>.^^>>>>vv>.>.>v<<<<<vvv<<<<^^<^<<^.^^>>>>vv>.>.>.>v<vvv<<<<<^^.<.<^<<^^^>>>>>>>>>>>vv>.>.>.>.>vvvv<<<<^^.<.<^<^^^<<<<<<vvv<v.<vv<<<<^v>>>>>>>>>>^^^<.^.>.>.^^>>>>vvv<<<<<<<vvv<<<<<<<>^^.<^<.^^^.>>>>vv>v<vvv<>>>>^^.<.^.^.>.^<^>>>>>>>>vvvv.<.<vv<<<<^^^<<<<<^>.^^<.vv>.v<<vvv<<><>>>>>^>>^.<^<^^^<<<.>>vv>.>v<<<<v.vv>^>>^.<^^.^^.>>>>>vv>.>.>.v<v.<vv<<<<<^.^^^.>^^<>>>>>>vv>.v<<<v.<vv<<<<>>>>>>>>>>>^^<.<.<.<.<^<<^^<^<<<>>>>>>>vv>v<<<vv.v>>>>>>>>^>^<.<^<<<<<<<<<<<.^.>^^<<<vvv.v.<vv<<<^.>>^.<^^.>.>^^<<......vv.v>vvv>>>^.v^>>^^<<^^^<.>>>>>>>vvv<v.<.<.vv<<<<^^<.<.<.^^^^<.>>>>>>>>vvv<v.<vv^.>^^<<^^^vv>vvvv^>>>>>>>^^^^^vvvvvv^^^^^^vvvvvv>>>>

There are under 8 million states combinations of position X time X set of visited corners, so they can be exhaustively searched in less than 1 second. If the code has no bugs, it should be impossible to beat. The optimal strategy was to use the whole board, as that allows froggy to cross the road 160 times, versus about 120 when confined to the center. Visiting the corners didn't cost any crossings since the traffic was so heavy.

/* feersum  2014/9
 https://codegolf.stackexchange.com/questions/37975/frogger-champion */

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <cstring>

#define B(F, CST, X, Y) best[ ((F)*NCST + (CST)) * BS + (Xmax-Xmin+1) * ((Y)-Ymin) + (X)-Xmin]
#define TL(i) ((int)t[i].length())
#define ABSPEED(I) (speed[i]<0?-speed[i]:speed[i])
#define errr(X) { cout<<"ERROR!!!!!!!!"; return X; }

#define DRAW 0
#if DRAW
    #include <unistd.h>
#endif


using namespace std;

int bc(int cs) {
    int c = 0;
    while(cs) {
        c += cs&1;
        cs >>= 1;
    }
    return c;
}

int main()
{
    const bool bonusTwentyfive = false;
    const int COLS = 23, T_ROWS = 5, YGS = T_ROWS + 2, XGS = COLS + 2;
    string t[5];
    int speed[] = {-4, 1, -2, -1, 4};
    ifstream f("t.txt");
    for(int i = 0; i < T_ROWS; i++)
        getline(f, t[i]);
    if(f.fail())
        return 1;
    f.close();
//for(int i = 0; i < 5; i ++)t[i]="xxx";

    char g[XGS][YGS];

    int mov[][3] = { {-1,  0, '<'},
                     {+1,  0, '>'},
                     { 0, -1, '^'},
                     { 0, +1, 'v'},
                     { 0,  0, '.'} };


    int Ymin = 0, Ymax = YGS-1;


    const int Xstart = 11, Xmaxmove = bonusTwentyfive ? 4 : 10;
    const int Xmin = Xstart - Xmaxmove, Xmax = Xstart + Xmaxmove;

    const int NCST = bonusTwentyfive ? 1 : 1<<4;

    int maxfr = 0;
    for(int i = 0; i < T_ROWS; i++) {
        if(speed[i] < 0) {
            for(int m = 0, n = t[i].length()-1; m < n; ++m,--n)
                swap(t[i][m], t[i][n]);
        }
        int carslen = TL(i);
        for(char*c = &t[i][speed[i]>0?TL(i)-1:0]; carslen; carslen--, speed[i]>0?--c:++c)
            if(*c != ' ')
                break;
        if(carslen)
            maxfr = max(maxfr, ( (carslen + COLS) * 2 + ABSPEED(i)-1 ) / ABSPEED(i));
    }
    const int BS = (Xmax-Xmin+1)*(Ymax-Ymin+1);
    int *best = new int[(maxfr+1)*NCST*BS];
    memset(best, 0xFF, (maxfr+1)*NCST*BS*sizeof(int));
    memset(g, ' ', sizeof(g));
    B(0, 0, Xstart, Ymax) = 0;

    for(int fr = 0; fr < maxfr; fr++) {
        for(int r = 0; r < T_ROWS; r++) {
            for(int x = 0; x < XGS; x++) {
                int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                g[x][r+1] = ind >= 0 && ind < TL(r) ? t[r][ind] : ' ';
            }
        }
        for(int x = Xmin; x <= Xmax; x++) {
            for(int y = Ymin; y <= Ymax; y++) {
                if(g[x][y] != ' ')
                    continue;
                for(unsigned m = 0; m < sizeof(mov)/sizeof(mov[0]); m++) {
                    int X = x + mov[m][0], Y = y + mov[m][1];
                    if(X < Xmin || X > Xmax || Y < Ymin || Y > Ymax)
                        continue;
                    if(!(mov[m][0]|mov[m][1]) && y > 0 && y > T_ROWS && g[x][y-speed[y-1]/4] != ' ')
                        continue;

                    int csor = ((X==Xmin|X==Xmax)&(Y==Ymin|Y==Ymax)&!bonusTwentyfive) << ((X==Xmax) + 2*(Y==Ymax));

                    for(int cs = 0; cs < NCST; cs++) {
                        int N = B(fr, cs, x, y);
                        if(!~N)
                            continue;
                        if((!(N&1) && y == 1 && Y == 0) ||
                              (N&1 && y == T_ROWS && Y == T_ROWS+1))
                            ++N;
                        if(N > B(fr+1, cs|csor, X, Y))
                            B(fr+1, cs|csor, X, Y) = N;
                    }


                }
            }
        }
    }

    int score = 0, xb, yb, cb, nb;
    for(int x = Xmin; x <= Xmax; x++) {
        for(int y = Ymin; y <= Ymax; y++) {
            for(int cs = 0; cs < NCST; cs++) {
                if(B(maxfr, cs, x, y) * (40 + bc(cs)) / 40 >= score) {
                    score = B(maxfr, cs, x, y) * (40 + bc(cs)) / 40;
                    xb = x, yb = y, cb = cs, nb = B(maxfr, cs, x, y);
                }
            }
        }
    }
    char *mvs = new char[maxfr+1];
    mvs[maxfr] = 0;

    for(int fr = maxfr-1; fr >= 0; --fr) {
        for(int r = 0; r < T_ROWS; r++) {
            for(int x = 0; x < XGS; x++) {
                int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                g[x][r+1] = ind >= 0 && ind < TL(r) ? t[r][ind] : ' ';
            }
        }
        for(int x = Xmin; x <= Xmax; x++) {
            for(int y = Ymin; y <= Ymax; y++) {
                if(g[x][y] != ' ')
                    continue;

                for(unsigned m = 0; m < sizeof(mov)/sizeof(mov[0]); m++) {
                    int X = x + mov[m][0], Y = y + mov[m][1];
                    if(X < Xmin || X > Xmax || Y < Ymin || Y > Ymax)
                        continue;
                    if(!(mov[m][0]|mov[m][1]) && y > 0 && y > T_ROWS && g[x][y-speed[y-1]/4] != ' ')
                        continue;

                    int csor = ((X==Xmin|X==Xmax)&(Y==Ymin|Y==Ymax)&!bonusTwentyfive) << ((X==Xmax) + 2*(Y==Ymax));

                    for(int cs = 0; cs < NCST; cs++) {
                        int N = B(fr, cs, x, y);
                        if(!~N)
                            continue;
                        if((!(N&1) && y == 1 && Y == 0) ||
                              (N&1 && y == T_ROWS && Y == T_ROWS+1))
                            ++N;
                        if(X==xb && Y==yb && N == nb && (cs|csor) == cb) {
                            mvs[fr] = mov[m][2];
                            xb = x, yb = y, nb = B(fr, cs, x, y), cb = cs;
                            goto fr_next;
                        }
                    }
                }
            }
        }
        errr(3623);
        fr_next:;
    }

    if((xb-Xstart)|(yb-Ymax)|nb)
        errr(789);
    #if DRAW

        for(int fr = 0; fr <= maxfr; ++fr) {
            memset(g, ' ', sizeof(g));
            for(int r = 0; r < T_ROWS; r++) {
                for(int x = 0; x < XGS; x++) {
                    int ind = speed[r] > 0 ? TL(r)-1 + x - fr*speed[r]/2 : x - (XGS-1) - fr*speed[r]/2;
                    ind >= 0 && ind < TL(r) ? g[x][r+1] = t[r][ind] : ' ';
                }
            }
            g[xb][yb] = 'F';
            for(int y = 0; y < YGS; y++) {
                for(int x = 0; x < XGS; x++)
                    cout<<g[x][y];
                cout<<endl;
            }
            cout<<string(XGS,'-')<<endl;
            usleep(55*1000);
            for(int i = 0; i < 5; i++) {
                if(mvs[fr] == mov[i][2]) {
                    xb += mov[i][0];
                    yb += mov[i][1];
                    break;
                }
            }
        }

    #endif
    cout<<score<<endl;
    cout<<mvs<<endl;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not sure how you're defining "states". If we consider the system state to be the time profile of the frog motion, there are approximately 5^3000 states, corresponding to the motion profile for the the 5^3000 possible inputs (five possible inputs per ~3000 frames). Obviously only a fraction of these will turn out to be admissible, but the number of admissible states would be impossible to search by many hundred orders of magnitude. When you submit your final answer, please submit a list of moves along with it. \$\endgroup\$ – COTO Sep 21 '14 at 2:03
  • \$\begingroup\$ Also, in case it isn't clear, note that the frog can jump left and right while in traffic, so long as none of the "squished" rules are violated. You aren't limited to waiting for windows where the frog is able to hop vertically across with no lateral motion. \$\endgroup\$ – COTO Sep 21 '14 at 2:06
  • \$\begingroup\$ @COTO In my calculation of "states" I did forget an important thing, namely the number of crossings so far, so I tried to give a clearer explanation. The spec was pretty well written. It seems I have interpreted all of these particular issues correctly the first time. \$\endgroup\$ – feersum Sep 21 '14 at 4:58
  • \$\begingroup\$ I compute the optimum as 162 + 10% = 178 crossings, but yours is close enough. I really didn't want this to turn out to be brute force-able, but evidently I should have given the problem more thought. In fairness, I'll award you the 100 rep. \$\endgroup\$ – COTO Sep 21 '14 at 18:41
  • \$\begingroup\$ Apparently I have to wait 24 hours before awarding the "bounty". For what reason: who knows. SE must not want answers rewarded punctually. If we did that, the terrorists would win. :O \$\endgroup\$ – COTO Sep 21 '14 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.