It took me quite a long time to solve the CodinGame puzzle The Last Crusade. Since I found no walkthrough online, here is my own.
Indy needs your help to survive the maze.
The Challenge
“The Last Crusade” is one of the most difficult single-player challenges on CodinGame. Only 8% of attempts have been successful and only around 200 people have solved it in total. I found some solutions on GitHub, but they all either hardcode moves or fail to solve the higher levels.
The task is to guide Indiana Jones through a two-dimensional maze, which is seen from the side. The maze consists of rooms, each with its own rules for entry and exit. Indy enters the maze through a room at the top or the side and follows these rules; the exit direction of each room determines which room is entered next. The following overview shows the different room types.
There are 14 different room types
Indy can descend through multiple rooms in a row without problems; he has probably never skipped a leg day. He can also slide left and right across the entire maze at a constant speed. For some reason, he can never stop in any room. He also cannot change directions immediately from left to right or vice-versa; for this, he needs to go down at least one level. He can never go upwards either. This means that he can’t move in circles.
The “guiding” happens not by telling Indy where to go, but by rotating rooms in 90° steps, either clock- or counterclockwise. Some rooms are locked, so they can never be rotated. Rooms are also temporarily locked while Indy is inside.
Time advances after every rotation so that Indy moves to the next room. This means that some paths can be impossible to take, as there is not enough time to rotate all rooms correctly.
The submitted code is expected to respond in under 150 ms; otherwise, the test case fails.
“Broken sewer” is one of the first levels. The correct path is easy to spot for a human.
None of this sounds too difficult. What makes this puzzle challenging is the addition of rocks. Just like Indy, these rocks move through rooms, following their rules. If rocks collide with Indy, it’s “game over,” but if two rocks collide with each other, they are both removed from the maze. Rocks can enter the maze at any time, so it’s not possible to precompute all rotations on the first turn.
One Possible Solution
The most naive solution is to try all combinations of rotations until finding one where Indy reaches the exit. The largest maze has 14×14 rooms, of which 46 are rotatable. It takes Indy around 40 moves to successfully reach the exit. Checking all possible rotations for each turn would require checking 46^40 combinations, which is equal to around 3*10^66. This number is a little too large. For comparison, the number of atoms on Earth is estimated around 10^50.
We need a better way. Let’s start by ignoring rocks and focus on finding a path for Indy. If we let him slide through the maze without rotating any rooms, there is a specific set of rooms that he will traverse before the inevitable crash. These rooms are interesting for us because they can be rotated to change Indy’s path. The room where a crash happens is also interesting, because it might be rotatable to let Indy pass. Other rooms can be ignored, greatly reducing our search space.
Now we need a way to structure this search.
Graph Search
Each room that Indy enters has a limited number of possible exits, depending on its rotation. Each exit then leads to a new room, which again has possible exits. This means we have a graph of the rooms. To find all paths that lead Indy out of the maze, we can use a graph search algorithm, such as BFS or DFS. These two differ mainly in the order of path exploration. We have to search the entire graph for all paths, so either one will work. Assuming we use BFS, we will have a queue, which contains states. On each iteration, a state is consumed from the queue and all states it can lead to are added to the end of it. We can define such a state as:
- x, y: The current location of Indy
- entry_dir: Either left, right or top; this is the direction from which Indy entered the room
- traveled_path: The list of directions that Indy has taken so far. When the exit is reached, this becomes a result.
We start with just one state, where x, y and entry_dir are Indy’s starting position, and traveled_path is an empty list. The search then runs until the queue is exhausted. When a path is found that leads Indy to the exit, it is added to the result.
The graph search will find two paths for Indy to get through “Broken secret passage”
The image above shows the two results that the graph search will produce for the maze shown on the left. They only differ in the four lower rows.
Rotations
Now we have paths, but we need rotations. For this, we follow each path and check each room. If it is already rotated correctly, we can skip it. Otherwise, we need to apply either one or two rotations to let Indy pass.
Here we are able to check if a path is possible. We can start with a “budget” of zero steps. For each room in the path, we add one to the budget; for each rotation, we subtract either one or two. If we ever reach a negative number, we know that the path is impossible to traverse.
Some room types allow different rotations. Imagine Indy traversing room type 7 from top to bottom. If there is time, the room could also be rotated twice to room type 9, which would also let Indy fall through. Similarly, room types 8 and 9 let Indy enter on the left side and leave at the bottom. For now, these options are irrelevant, but they will be important later when we also account for rocks.
For the two paths above, we will find the following six results. Notice how they are almost identical.
The two paths will be expanded into six paths when checking possible rotations
Any one of these paths is a valid solution. To derive an action, we just need to rotate the first room that is oriented differently.
To validate this approach, we can use a test server I wrote. It simulates the CodinGame backend and works offline. For our current solution, it will produce output similar to this:
Summary: * Success in 0.001 seconds in level broken_well.in * Success in 0.006 seconds in level broken_sewer.in * Success in 0.018 seconds in level broken_secret_passages.in * Success in 0.027 seconds in level broken_mausoleum.in * Success in 0.006 seconds in level underground_complex.in * Fail in 0.005 seconds in level rocks_1.in * Fail in 0.007 seconds in level rocks_2.in * Fail in 0.006 seconds in level avoiding_rocks.in * Fail in 0.002 seconds in level rock_interception.in * Success in 0.008 seconds in level multiple_choice_and_rocks.in * Fail in 0.040 seconds in level only_one_way.in * Fail in 0.046 seconds in level only_one_way_validator.in
For now, we have successfully solved every level that does not contain rocks. We have even solved a level that does contain them, but were probably just lucky. Notice how the runtime is well below the given limit of 150 ms per response.
Taking Rocks into Account
Now it gets tricky. We need to find rotations that not only let Indy pass but also destroy any rocks that would collide with Indy by using walls or even other rocks. Let’s think about this new search space for a moment.
Using the path search that we already have, we could find paths that let rocks reach the exit. This does not help much. But we could modify the search to instead return all paths where a rock crashes into a wall or leaves the maze.
This sounds interesting. But how can we investigate the interaction between all these paths?
Let’s try to generate all path combinations. If there are, for example, two rocks with 10 paths each and 6 possible paths for Indy, this would mean we have 600 combinations to check.
Each combination is first checked for its rotations. We can apply the “budget” idea from earlier again. Each room has to be in a certain state by a certain time. We also need to check if the same room ever needs to be in two different states at the same time, which would render a combination impossible.
Each combination also needs to be checked for Indy’s survival. We can simulate the maze and check to see if Indy would ever crash into a rock.
Sometimes rocks need to crash into each other. The rightmost rock cannot be stopped by other means.
In theory, this should work. There is no possible solution that is not checked. Let’s see if the performance is still okay, as we have added quite a lot of calculations for some test-cases. Running the test-server now gives us output like this:
Summary: * Success in 0.001 seconds in level broken_well.in * Success in 0.007 seconds in level broken_sewer.in * Success in 0.012 seconds in level broken_secret_passages.in * Success in 0.030 seconds in level broken_mausoleum.in * Success in 0.006 seconds in level underground_complex.in * Success in 0.106 seconds in level rocks_1.in * Success in 0.012 seconds in level rocks_2.in * Success in 0.012 seconds in level avoiding_rocks.in * Success in 0.005 seconds in level rock_interception.in * Success in 0.015 seconds in level multiple_choice_and_rocks.in * Success in 155.882 seconds in level only_one_way.in * Longest turn was slow at 123.650 seconds * Success in 335.674 seconds in level only_one_way_validator.in * Longest turn was slow at 254.228 seconds
It looks like we solved everything! That’s great news! The only thing we need to improve is the performance.
Optimization
We have seen in the test server’s output that our code is way too slow for the test-case “Only one way.” We need to find an optimization that improves performance while not slowing down other test-cases. Let’s first have a look at what’s going on. We can observe a very high response time when the fourth rock enters the maze.
In this state, it takes our current code several minutes to find a valid combination
In the image above, we see Indy and four rocks. While there are 36 paths for Indy, the rocks have 1, 14, 14 and 421 paths. This results in 2,970,576 combinations, which all need to be checked. The rock adding the most paths is actually the one directly behind Indy. Our current code sees each unlocked room as a possible place to crash it, but during the simulation, it becomes clear that this would not work without also blocking Indy’s path.
The rock behind Indy can actually never be crashed. It can also never crash into Indy, as he is always one field ahead and the rock can never take a different path. It is also not possible to crash it into any other rock that is in any way relevant to Indy reaching the exit.
So the rock behind Indy can be completely ignored. This lowers the number of combinations down to 7,056.
This could be the optimization we were hoping to find. Implementation will at first lead to an error, because the rock cannot be completely ignored, as it still blocks the room it falls through from rotations. Taking this into account, the code will now produce the following output:
Summary: * Success in 0.001 seconds in level broken_well.in * Success in 0.005 seconds in level broken_sewer.in * Success in 0.009 seconds in level broken_secret_passages.in * Success in 0.028 seconds in level broken_mausoleum.in * Success in 0.008 seconds in level underground_complex.in * Success in 0.024 seconds in level rocks_1.in * Success in 0.013 seconds in level rocks_2.in * Success in 0.012 seconds in level avoiding_rocks.in * Success in 0.005 seconds in level rock_interception.in * Success in 0.013 seconds in level multiple_choice_and_rocks.in * Success in 0.197 seconds in level only_one_way.in * Success in 0.267 seconds in level only_one_way_validator.in * Longest turn was slow at 0.144 seconds
Which is good enough! The solution might still be rejected by the last validator, but this happens at random, and you can submit the solution multiple times until it works.
I hope I’ve made it clear how I solved this puzzle. If you have questions, please leave a comment.
About the Author:
I like to find simple algorithms that are “just good enough” to solve complex problems. In my free time, I struggle with growing a beard and getting better at Rocket League.