Day 18: Many-Worlds Interpretation
by Simon Berger
Links:
I wasn’t feeling all that well today and that considerably reduced the amount of fun I had while solving today’s puzzles. Today once again features a graph problem, but it’s a little more complex than day 6’s or day 15’s was. These puzzles involved graphs where the vertices would describe a particular state, but said state would usually only contain the position on the map.
Today we’re dealing with a much more complex state. It contains the robot’s position and which keys it has collected so far. In terms of graph theory, transitioning from one state to another means following an edge connecting two vertices. In our case this is the robot moving from one position to another. It can only move to positions that aren’t blocked by walls or doors which it doesn’t have the keys for. For simplicity’s sake we’ll also say that the robot only ever performs one step at a time. This means that each vertex (state) has at most four edges (if there is an outgoing edge to another vertex and an incoming one from the same vertex it only counts as one edge) to other vertices. These four vertices are the positions neighbouring the current position of the robot and there is no edge if a vertex describes an impossible state such as it being a wall or a closed door. We pick up keys but not drop them, therefore this is a directed graph and it’s also cyclic (the robot can move back to a previous position without picking up any keys).
What we’re looking for is the least amount of edges we have to follow to reach a state where the robot has collected all keys starting from the start state. We can use the lovely BFS (or any other path finding algorithm) to do that. The problem is that this graph has an incredible amount of edges and vertices. For each possible position in the vault there are vertices for each possible combination of keys. Some of these vertices are unreachable, yes, but it’s still an unfathomable amount.
The good news is that we don’t have to generate the entire graph beforehand. We can just create it as we go. The other thing is that we can use caching, specifically memoization. Once we know the amount of steps it takes to reach an end state (vertex) we store it so we don’t need to calculate it again. We can then use a recursive approach:
For all reachable keys, take the distance from the current position to the key and add the amount of steps required starting from this state (this is the recursive part). After doing this for each key, return the least amount of required steps. If there are no reachable keys, return 0.
This performs pretty badly but you know how it goes, Rust just deals with it.
You know it’s bad when you have to run your code with the ”--release” flag.
I even ended up removing some of the test cases as they took too long to run which would be quite annoying for future puzzles.
The second part is similar in concept. This time we have four robots so our state holds four different positions instead of just one. This turns the three degrees of freedom (two for the position and one for the keys) from before into nine. The graph just got a whole lot bigger. The saving grace here is that the vault is divided into four parts, so the amount of possible positions for each robot is limited. We can take the same memoized recursive approach from before, but this time we try each key for each different robot. That is, for each robot get the fewest steps required like before and then take the smallest option from those four.
This may sound like it’s much more inefficient than before, but because each robot only has a limited amount of positions and keys to deal with it ends up taking the same, if not less, time.
The first part is just a special case of the second part with only one robot instead of four. The second part in turn is a specialisation of the general case for N robots. The core idea stays the same. Because of this I rewrote the first part to re-use the same logic as the second part. I had already designed the code for the second part to be agnostic to how many robots there are. The only difference between the first and second part in my code is that the second part calls a special “split” function that splits the vault into the four different vaults and creates the corresponding robots first. This is necessary because both parts reuse the same input and you need to manually adjust it to get the input for the second part.
tags: graph theoryOverview
Previous day Next day