Advent Of Code Day 18 2019, the real challenge
Advent Of Code is a yearly coding competition in december in which thousands of developers world wide participate. This year was the first year for me to participate every day to try to run for our private company leaderboard and I succeeded in getting the second place eventually. Aside from that it was really a lot of fun and I learned a lot along the way.
Out of all of the 25 challenges none was more challenging and exciting than day 18. I’d like to elaborate my train of thought which resulted in a solution which runs within 200 ms for part one and even under 20 ms for part 2.
The problem in part 1 is to find the minimum path in a maze of 80 x 80 positions which contains 26 keys (a-z) and 26 doors (A-Z) which can only be opened once the corresponding key has been acquired. This means that the optimum path through the maze continuously changes as you pickup keys along the way. At first glance it seems that the problem space is just too large to analyse given the 2²⁶ * 80 * 80 = 429496729600 possible unique combinations of keys in possession and coordinates to traverse, but of course there are optimisations which can be made.
As most problems related to finding shortest paths can be solved with a form of Breadth First Search (BFS) a quick way to think about the problem is that instead of navigating through a 2D maze, the keys/doors actually form another dimension and make it effectively a 3D space (x, y, keysInPossession). While this approach will in fact result in a working algorithm (which was my first try) it will at least take in the order of minutes to run and is certainly not optimal.
Thinking more carefully about the problem, I realised that the only coordinates which in fact really matter are the points in the maze were the keys are located, effectively forming a reduced maze (or graph) on top of the raw coordinates. Each path from key to key is a weighted path, with potentially unlimited weight (if a door along the way is closed for the current set of keys in possession). It was not really apparent to me at first glance how to form this insight into a working algorithm, because it may be the case that less optimal paths exist which circumvent some doors but will result in a shorter overall path (there can exist more than one connection between keys with different combinations of doors in between). If you would do a BFS from the 26 key locations (and the initial location), it would result in finding only the shortest paths and not the longer ones, while those longer ones could potentially produce a shorter overall path for the whole round trip.
So instead I implemented a recursive solution with lots of caching and even multi-threading involved which resulted in a running time of 10 seconds for part 1 and about 2 seconds for part 2, which is not really bad. However, the problem kept playing on my mind, knowing that a more optimal solution should exist.
After Advent Of Code finished I decided to revisit the puzzle and I found this algorithm to find not only the shortest path, but all paths from a source to a destination. I quickly realised that this would also hold for one source to multiple destinations if you would just let the algorithm run until all options were exhausted (instead of exiting when the destination was found).Thus, it would be possible to fully chart the maze into weighted graph by running this algorithm from 27 locations (the starting point and the 26 keys). This weighted graph would have conditional edges, which would have infinite weight for doors in case the required keys would not be in possession, but knowing all these connections up front would only require a filter on the edges given the keys in possession at a particular point in time.
A Dijkstra approach could be taken using this weighted graph, knowing that it is not needed to insert the entire graph at the start of the algorithm (it can be done along the way as certain nodes/edges are visited). The Dijkstra algorithm should consider the 3D points as stated above as unique locations. This means that each combination of (x, y, keysInPossession) is a point in this 3D maze. The algorithm should exit when the first point is encountered where keysInPossession is equal to all keys, and the path length at that point would be the minimum by definition.
It should be noted that keysInPossession can be represented as a 26 bit integer where each bit represents a key being present or not, which greatly improves performance.
It was very nice to see that this approach resulted in a working solution which ran under 1 second!
However, there are still more optimisations that can be made, which I thought of iteratively:
- It is not needed to pre-calculate all possible paths in the graph, because not all paths necessarily have to be traversed, so I decided on a lazy approach where paths would be calculated as necessary and cache them afterwards.
- When multiple paths exist between similar pairs of keys with the same doors in between, only the shortest has to be added. For longer paths, it only make sense to keep them if the keys required is not a subset of the keys required for the shortest path.
- At the time the paths are requested a certain number of keys would be in possession. Because of the way the Dijkstra algorithm works, at that point it’s certain that there exists no shorter path to obtain these keys, so it is only necessary to take paths into account to keys which are not yet in possession.
- The path calculation between keys can stop for each path if a key is encountered which is not yet in possession. The reason is that when that particular key is visited later on the same algorithm is performed on that key, so there is no need to go any further.
- Technical optimisations could be made, such as pre-allocating the optimum size for collection types, using a FibonacciHeap instead of an ordinary PriorityQueue for the Dijkstra algorithm, inlining functions with lambdas where it made sense, etc
After all these optimisations it was very nice to see that out of the 10¹¹ coordinates only 10⁵ actually have to be visited with about 10³ key locations resulting in a running time of under 200 ms!
For part 2 the problem statement is that instead of one initial location, there are now four and the robots positioned at those locations can take turns to collect the keys.
While this sounds more complicated it just adds 3 more pairs of coordinates to the problem and it actually requires a whole lot less calculations to be made!
The reason is that the big maze is now divided into 4 small ones and the options within those 4 small mazes to find unique paths are fairly limited.
Applying the algorithm to part 2 resulted in a run time of 15 ms! Which is really amazing considering the complexity of the problem statement. It only requires 10⁴ coordinates to be visited.
In summary, I learned a great deal from this exercise and I thank the creator of Advent Of Code for these fun puzzles.
The full code of the solution, with comments where possible, can be found on GitHub