The winners of The Last Crusade, Gangrene, NewbOo and azukun, return to their code and tell us how they went about saving the skin of Indy.

Gangrene‘s Debrief:
(1st place on the podium | France | Python | 2:22:54)

For the first task, I stored the different rooms in an 8×3 table (8 rooms, 3 entrances top, left, right). Each cell of this table indicates whether there is an exit and, if applicable, the calculation needed to obtain the new coordinates.


For the first task, it was therefore sufficient to read the cell corresponding to Indiana’s current coordinates.For the second task, one now needed to find a path that did not yet exist.

I decided to perform a depth-first search. I travel as far as the current path permits. As soon as I reach a room that does not provide an exit, I look, if possible, to turn it, and if not I go back. Of course, to avoid losing turns, I am careful to first test the room without turning it, then pivoting it a sole notch to the left or right, and finally turning it completely as a last resort. I always keep in mind the number of turns I have to reach this room (number of turns of moving minus the number of pivots already made).

When the exit is reached, I return the length of my recursion while sending back as a result the first pivot made, and the number of turns I have before doing it.

The result is then analyzed.

If I have turns at my disposal and only boulders are present, then I like to occupy myself with these.

At this stage, the ordeal had already started two hours ago, and I thought to myself that given the previous challenges, the top spots had already been taken. I thus do not go for subtleties. I test the boulders in the order they appear. For each one I calculate its path until the first rotating room. If this room provides an exit, I turn it to block the stone (this is possible in 1 stroke regardless of the room and its position), if not I test the next stone.

If all of the stones around are already blocked, I pivot the previously taken room to free Indiana’s passage.

If no room is to be moved, nothing to do but WAIT, it is won.

My code isn’t perfect, and I realize this even more while analyzing it in order to write this. For example, if a room needs to be turned by a notch and the next by two, my function will return that I need one turn to rotate the first room, while another two will be needed to start the movement of the following room.

The situation posed with the boulders could have been much more complex, forcing Indiana to follow one route and not another, a trap into which I would have fallen.

Once again, CodinGame has presented us a great challenge, very complex on paper, but fortunately simplified by the situations given.

———–

Newboo‘s Debrief:
(2nd place on the podium | France | PHP | 2:34:57) Best to admit it right away: I was initially a little lost. Unlike the previous editions where the playing field was globally fixed, here it was variable and one didn’t have control over poor Indy, which ultimately meant reversing the classic path-searching problems. Fortunately, the first exercise tended to put us on the right track by teaching us to simulate the movement of Indy (and thus of the boulders as well).

Definition of constants

Before actually tackling the solution, I began with one step important for the rest: to define two tables according to the different types of rooms. – A first to give the type of movement in accordance with the type of room and the point of entry, which can read $move(type of room)(point of entry)=(delta x, delta y, point of entry in the following room) – A second for the rotations of rooms, because to turn a room was, in reality, to change its type.Search for a path

I initially occupied myself only with tests 1 to 5, leaving out (almost) completely the case of the boulders. I chose to begin with a depth-first search, with optimizations so as to have a minimum number of branches to test and thus the complete solution from the first turn. To summarize simply, I contented myself with simulating Indy’s movement and at each new room I would check to see what would keep him alive:-WAIT if all is well

-LEFT in this room
-RIGHT still in this room
-Or finally a 180, for example, twice RIGHTYes, turning the room two times is possible, if we ever have at least one WAIT in our provisory solution! Instead of simply adding an instruction, I also transform a WAIT into a rotation, which returns, as it were, to backtrack and explore another branch instantaneously. Note that I replace the most recent “WAIT”, so as to have other “WAIT’s” as soon as possible to take care of the boulders.

The boulders 

It was now left for me to include the boulders, knowing that they are not all there from the first turn. Taking advantage of the fact that the cases with boulders were really very kind (To convince you I invite you to take a look at the bonus level ^_^), I was happy with a very minimalist solution that happens to work in these two famous tests 6 and 7. I still continue to calculate the solution during the first turn, and then when I have a WAIT to spare, I check if there are boulders to eliminate. To eliminate a boulder, I simulate its movement and I turn the first unlocked room to the left or right if necessary (if not necessary, I can take care of another boulder). The following turn, I recalculate the solution for Indy in order to integrate the potential changes to his initial route.I thus absolutely do not preoccupy myself with knowing whether a boulder will or will not cross Indy’s route, nor if one is of higher priority than another (being happy simply with eliminating the first in the list), nor again if it might not be better to turn a room farther along the path of a boulder than the first possible. But, as I said, the cases were very kind and a quite simplistic algorithm just made it through.

The final word I was really very surprised to finish 2nd with such a “long” time compared with previous editions, especially with some time foolishly lost on my tree traversal in which, originally, I never tested the rotations if the WAIT was working… but whatever the ranking, I would in any case have taken much pleasure in saving Indy. Thanks to CodinGame for the always-original subjects (and the “Dark mode” of the IDE ^_^).

————–
Azukun‘s Debrief: 
(3rd place on the podium | Russia | C# | 2:39:01) 

Level 1: For the warming up task one just needed to carefully implement Indy’s movement through all room types for all possible directions, I did it with a 14×3 matrix:

int[,] way = new int[,] {
{ -1, -1, -1 },
{ 1, 1, 1 },
{ 2, -1, 0 },
{ -1, 1, -1 },
{ -2, 0, 1 },
{ 1, 2, -2 },
{ 2, -2, 0 },
{ -1, 1, 1 },
{ 1, -1, 1 },
{ 1, 1, -1 },
{ -2, 0, -1 },
{ -1, 2, -2 },
{ -1, -1, 1 },
{ 1, -1, -1 },
};

Three columns stand for three possible ways to enter a room (Indy can’t move upwards). Positive matrix’ element value designates new direction, -2 stands for forbidden movements, -1 for impossible ones.
Having matrix like this, each turn I do following to calculate new Indy’s coordinates:
int w = way[tunnel[r][c], p];
r += dr[w];
c += dc[w];
Level 2: So we’ve got a labyrinth, but instead of controlling the player, we control the labyrinth itself – another nice task from CodinGame! While sounds intimidating, we do as usual iterate through possible moves until we reach exit. I did it with a simple recursive DFS. But what took me and other competitors so long – is abundance of details requiring very careful implementation and… rocks! I’ve spent more than an hour to pass the last two tests. While they move only from right to left in a very simple tunnel, my code required a lot of modifications – a notable one is to rotate rooms of type 6 and 8 to type 9, not type 7 in order to block some rocks.
Anyway, kudos to CodinGame team for yet another exciting coding feast, looking forward to Shadows of the Knight!