Day 15: Oxygen System
by Simon Berger
Links:
Today’s puzzle is a pretty traditional graph problem again. Specifically it requires you to find paths in a graph. The twist is that you first have to discover the graph (a maze-like map) using an intcode controlled robot. You can only move the robot relative to its current position and all you get back is whether the robot hit a wall, found the target, or just moved. This makes it pretty difficult to get the graph.
The discovery itself can also be seen as a graph problem, but, as opposed to most problems, here you’re dealing with a stateful robot so you can only inspect positions neighbouring the robot’s current position. Because of this you can’t apply traditional algorithms like Flood fill as they require you to “jump” to a previous position. This isn’t actually true, you can “cheat” and create copies of the robot’s state to accomplish this. I’m using the word “cheat” very lightly here because this is also what I ended up doing, but it is kind of breaking the puzzle’s story which explicitly mentions: “A single remotely-operated repair droid is your only option […]” (emphasis mine). There are other ways to solve this, for example by using a backtracking algorithm, but let’s not go down this rabbit hole.
I’m using the aforementioned flood fill algorithm to discover the entire map. At the end of this step we know what’s at each position of the map.
When I say “map” I’m only referring to all reachable positions including the neighbours of those position. There might still be undiscovered parts of the map, but these are irrelevant for the tasks.
Now we need to find the shortest path to a special position in the map, the oxygen system. At first I was using Dijkstra’s algorithm for this. This turned out to be a complete overkill, but I thought maybe the second part would involve more complex path finding. But anyway, since we already know the full map finding the path isn’t difficult and that concludes the first part.
The second part demands something that sounds a lot more difficult than it actually is. What is wants is just the distance to the position that’s furthest away from the oxygen system.
It would be a lot more difficult if we hadn’t first discovered the entire map and instead tried to do both things at the same time.
Since I was already using Dijkstra’s for the first part, I used it for the second part again, this time letting it run until it has reached all positions. This gives us the distance from the oxygen system to every other position. All that’s left to do is to find the biggest distance and we’re done with the second part. That may sound really easy, but don’t forget you first have to find out that this gives you a valid solution.
After looking at my code for a bit I realised that using Dijkstra’s algorithm like this is just like doing a Breadth-first search with extra steps. Dijkstra’s is, in a way, just an extension of BFS for weighted graphs. We’re dealing with an unweighted graph though, so I switched to using BFS, which is a easier to implement.
Because this finds the distance to every position it will naturally also find the distance to the origin. Instead of having the first part be a separate thing entirely I instead decided to make it a subset of the second one. This makes it possible to reuse the mapping from position to its distance from the oxygen system for both parts.
The first part uses it to get the distance between the origin (0, 0) and the oxygen system and the second part looks at each distance and returns the biggest one.
Overview
Previous day Next day