Skynet Revolution | Top CodinGamers Code reviews

Thanks to the team for the challenge!

—–

Manger’s debrief:
(2nd place on the podium | France | C#,C | 1:36:40)

For the first exercise, my first program was initially content to simply accelerate until reaching a speed equal to the distance of the jump (size of the chasm + 1), then to brake after the jump. This was not enough because, to pass the chasm with a speed equal to the distance of the jump, one must initiate the jump at the spot exactly before the chasm.

For this, I calculate in SpeedDist the distance of acceleration needed to attain exactly the desired speed from the current speed. The moto, then, must begin to accelerate just when its distance from the chasm is equal to this distance for acceleration. In practice, with my program, the moto would never be able to reach a situation where the acceleration distance is equal to the distance from the chasm. One could thus probably come up with test cases in which this program no longer responds to the problem.

Final point, the test case where the moto starts at a very high speed. In this case, I was content to have it slow down until reaching a speed sufficient for the jump, and which allows it to pass the last tests.

The second exercise was more difficult. As for me, I hesitated between two methods:

– Start with a simple strategy allowing one to pass the first tests, and then fiddle with it during the course of the test cases to pass them all. This can work, one has the time for execution without difficulty if you don’t enjoy doing heavy calculations (which need not arise too much with this method), but it can quickly end in a code that is quite illegible (a kind of undrinkable soup of if/else/while) and a few headaches.

– With each round of the game, there were only six possible movements (SPEED/SLOW/JUMP/UP/DOWN/WAIT): one has a tree of possibilities (each node having six stems, one per possible movement) that one will traverse with a depth-first search (DFS) (while limiting the traversal depth). In the present case, this method seems worthy of consideration because there are only a few possible choices: the complexity being in O(Number of choices ^ traversal depth), a high number of choices eliminates this method. The advantage is that one is assured of always finding the solution if it exists, provided that one has a sufficient traversal depth, the downside being the risk of not keeping to the time constraint if one provides a traversal depth that is too large. Thus, if one meets with a test case that necessitates a traversal depth for which one cannot keep to the time restraint, one risks being stuck.

Systematically finding counterexamples to simple strategy ideas that occurred to me, I decided to turn to the second solution. For a DFS, the simplest option is to use a recursive function. By using this recursive function, one risks a stack overflow, but in the present case, this is not a concern since the traversal depth must be low if one wants to meet the time limit. One can in any case fiddle around to change the size of the stack if need be.

This recursive function will take the state of play as argument, returning a choice of SUCCESS if a possible choice is found or DEFEAT if not, and will continue thus:

– If the maximum depth is reached, return SUCCESS

• Simulate the new state of play with the choice
• If the new state corresponds to a defeat, continue to the following choices
• If the new state corresponds to the end of the track (victory), exit the function while sending back the executed choice
• Make a recursive call with, as an argument, the new state of play

The overall state of the game (position of motos, motos dead or living, speed of the group) is described in very few variables. During the simulation of the new state of play, one has two choices:

– Simulate the new state of play in a copy of the state of play that one can “trash” afterwards.
– Modify the current state with the simulation, then, knowing the movement that was effected, backtrack.

The second option takes up little memory space and never copies the state of play, and is thus efficient when the states of play are quite large. The first uses more space and makes more copies, but is much simpler to code (no need to backtrack after having simulated the new state of play). As the states are small, I decided on the first choice. To the extent that there were going to be frequent copies and that there is a risk of keeping within the time restraints for execution, I chose to code the program in C++. In C++, by coding the state of play in a structure/class with fixed tables, a simple assignment suffices for copying the state of play in an efficient enough manner, seeing as all the data is contiguous in memory. In C#, if the structures are also copied by assignments, the tables are allocated dynamically and the copy of a structure containing a table will copy only the reference to this table. One would thus have to write a cloning function for the state of play that, although short, would probably be significantly less efficient that a copy in C++ (necessity to reallocate the tables). There is also the possibility of using unsafe blocks in C++, but I have no experience in this subject.

Here, all said and done, is my commented solution:

#include <iostream>
#include <string>
#include <string.h>

using namespace std;

// A list of #defines instead of an enum because the compiler complained about the implicit casts from int to enum
#define SPEED 0
#define WAIT 1
#define JUMP 2
#define SLOW 3
#define UP 4
#define DOWN 5

int M;
int V;
char R[4][1024];
int LEN[4];

// Structure describing the state of play. No member allocated dynamically so as to be able to recopy it entirely with a simple assignment

struct GameState
{
int S;
int X[4];
int Y[4];
bool A[4];
// Simulation of the new game state if one chooses the action “action”
GameState Update(int action)
{
GameState newState = *this; // The copy

// Here’s the point where I lost a lot of time: I often had the tendency to forget the “newState” in the modifications of the variable. Technique for avoiding this: use instead a constructor for the update:
GameState(GameState &orig, int action) {*this = orig; …}

if(action == SPEED)
newState.S++;
if(action == SLOW)
newState.S–;
if(newState.S < 0)
newState.S = 0;

for(int i=0; i<M; i++)
{
newState.X[i]+=newState.S;
}

char dy = 0;
if(action == UP)
dy = -1;
if(action == DOWN)
dy = 1;
for(int i=0; i<M; i++)
{
newState.Y[i] += dy;
if(newState.Y[i] >= 4)
newState.Y[i] = 3;
if(newState.Y[i] < 0)
newState.Y[i] = 0;
}
// One checks to see if the motos are dead on the route

if(action != JUMP)
{
for(int i=0; i<M; i++)
{
for(int x=X[i]+1; x<newState.X[i]; x++)
{
if(R[newState.Y[i]][x])
newState.A[i] = false;
if(x < newState.X[i] && R[Y[i]][x])
newState.A[i] = false;
}
}
}

for(int i=0; i<M; i++)
{
if(R[newState.Y[i]][newState.X[i]])
newState.A[i] = false;
}

return newState;
}

// Our DFS. SUCCESS = WAIT here. DEFEAT = -1. * this “corresponds” to the state of play, MaxDepth-depth at the current traversal depth.

// Did we lose? Win? With the description above, this block will normally be located in the “for” loop below        int survivors = 0;
int winners = 0;
for(int i=0; i<M; i++)
if(A[i])
{
survivors++;
if(X[i] > LEN[Y[i]])
winners++;
}

if(survivors < V)
return -1;
if(winners >= V)
return WAIT;

// Browse the possible choices
for(int a=0; a<=5; a++)
{

// If one doesn’t do the following, the algorithm can very well choose to remain doing nothing permanently. Indeed, one is sure never to lose if one does nothing, seeing that one doesn’t take into account the constraint of the limit on the number of rounds.

GameState s = Update(a); // Simulation with the choice made

if(s.IsFeasible(depth-1) != -1)
{
s.Print();
return a;
}
}

return -1;
}    void Print()
{
fprintf(stderr, “New state: %d – “, S);
for(int i=0; i<M; i++)
{
fprintf(stderr, “[%d,%d,%d]”, X[i], Y[i], A[i]);
}
fprintf(stderr, “n”);
}
};

#include <time.h> // / Add time.h for time measurements
int main()
{
const char *acts[] = {“SPEED”, “WAIT”, “JUMP”, “SLOW”, “UP”, “DOWN”};

// Read init information from standard input, if any
scanf(“%d”, &M);
scanf(“%d”, &V);
for(int i=0; i<4; i++)
{
scanf(“%s”, R[i]);
LEN[i] = strlen(R[i]);
fprintf(stderr, “Road %d: %d lengthn”, i, LEN[i]);
for(int j=0; j<LEN[i]; j++)
{
R[i][j] = (R[i][j] == ‘0’ ? 1 : 0); // 1 : hole, 0 : ok
}
}

struct timespec start, end;
while (1) {

GameState s;
scanf(“%d”, &s.S);
for(int i=0; i<M; i++)
{
int a;
scanf(“%d %d %d”, &s.X[i], &s.Y[i], &a);
s.A[i] = (a == 1);
}

clock_gettime(CLOCK_MONOTONIC, &start);
int a = s.IsFeasible(10); // Max depth : 10
clock_gettime(CLOCK_MONOTONIC, &end);
if(a == -1)
printf(“WTF?n”);
else
printf(“%sn”, acts[a]);

fprintf(stderr, “Took %d usn”, (end.tv_sec-start.tv_sec)*1000+(end.tv_nsec-start.tv_nsec)/1000);
}

return 0;
}

In the end, a maximum traversal depth of 10 was sufficient. I didn’t try to look with less during the competition; however, after having tested in training mode, a depth of 4 was the minimum sufficient. The time constraints are very easily met (a few microseconds for the search itself), which shows that in the end, in this case, one shouldn’t have worried about efficiency. The debugging of C++ code being more delicate than the code in Java/C#, it probably would have been more profitable to tackle the problem in one of these two languages, even if it meant coding the short copy function for the state of play.

1st exercise: Not much more to add than the algorithm explained on the blog. I expected, however, cases where it would be necessary to insert waiting time into the middle of the approach to arrive just at the edge of the chasm before jumping, but it remained unimplemented seeing as all the tests passed without this consideration.

2nd exercise: For the record, I was a little knackered the night of the ordeal and I chose to use brute force out of laziness alone (it goes to show, sometimes it’s better not to think to much). There were nonetheless several subtleties that made it possible to obtain a solution more quickly and without having to preoccupy oneself with the depth, even if I didn’t include them all in my final code (the 150ms of the first round were sufficient, even in PHP). The ideal order to test actions was SPEED, JUMP, UP, DOWN, SLOW:

– Privilege SPEED to explore first the shortest branches
– Privilege JUMP because the test is quick (one position per moto rather than several positions on the route)
– Do not test WAIT because JUMP always gives the same final position

In the end I stayed with SPEED, UP, DOWN, WAIT, JUMP, SLOW for aesthetic reasons (because these remain bikes, not goats ^_^)

A final word: A big thanks to the whole CodinGame team for the great exercises that are offered with each edition. I discovered the site by chance 3 months ago and I’ve become a fan.