8
votes
Day 18: Many-Worlds Interpretation
Today's problem description: https://adventofcode.com/2019/day/18
Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
Part 1: I solved this challenge by using Dijkstra's algorithm. I used the pathfinding Rust library for its implementation of that. Usually when you use Dijkstra's algorithm, your nodes are just your coordinates, but I made it so the nodes that I ran the algorithm over included which keys I had. This isn't the greatest use of a pathfinding algorithm, because this means the nodes before and after I grab each specific key are treated as entirely unrelated, so the algorithm can't make any use of the similarity of each of the pre-key and post-key graphs. My solution took a few seconds when run in release mode, which is the longest any of my solutions have taken so far.
Part 2: I adapted my code so each node stored the coordinates of several players, so that Dijkstra's algorithm would move one player each turn. ... This is really abusing the algorithm, because now if player 1 moves a step, the algorithm thinks player 2 is in a new world that it doesn't know anything about, etc. This is just compounding on top of the problem that it thinks all the players are in a new world whenever any pick up a key. My code worked on all of the test cases, but it never finished running on my real input because it was too inefficient. I probably should have actually switched away from abusing the pathfinding algorithm like this, but instead what I did was precompute a neighbor map between all the keys and doors on the map, and I ran the pathfinding algorithm over that instead. Now instead of pathfinding between every grid square one at a time, it pathfinds directly between points of interest. With this, part 1 now finishes in 1 second, and part 2 now finishes in 10 seconds. I was pretty surprised at first that part 1 had a slight improvement while part 2 had a practically infinite improvement, but I think it makes sense: with this change, in part 2, every time any player moves, it's because they're grabbing a key. This means that the "any player moving changes the world for everyone" and "any key being grabbed changes the world for everyone" issues come into perfect alignment, and only make one impact on performance instead of exponentially killing performance.
Maybe I'll come back to this problem later and try to solve it a better way. It's just too fun solving things with generic pathfinding algorithms.
Woot, I got my solution improved a lot. Both parts together now run in under half a second. During pathfinding, I now cull the neighbor map down (using Dijkstra's algorithm again, to calculate the new distances between the remaining nodes) as I pick up keys to remove the picked-up keys and opened doors. This means the algorithm no longer explores to and from and between keys and doors that no longer matter. Apparently the algorithm was spending nearly all of its time doing that before. I think this solution is now an efficient algorithm for this kind of problem.
Just doing part one took me long enough that I'm not sure I'll be able to finish p2 before the next puzzle.
My first pass was based on just looking at the requirements for each key, identifying which key will be the last to pick up, and then working backwards from there. I was very quickly able to produce correct answers for any map except the fourth sample (with equidistant keys) and my actual input (I'd get a "valid" path, but not the shortest).
Then I spent a lot of time trying to optimize it as if I was writing a single agent AI for a roguelike or something, it had a concepts of long and short term goals, where it was headed at any given time, and parameters for allowing it to notice and pick up keys that were a little ways off its path. This got me a little further, but not enough to reliably get the shortest path on the harder problems.
Eventually I gave in and began re-writing for a generalized graph search and started running into the combinatorial explosion issues that everyone else did. This was long and difficult but informative. My approach started with a DFS and lots of heuristics to select the preferred node, including hard limits on step count (since I knew from the site that my initial solvers answer was too high, I could rule out any path that required more steps).
Eventually I found myself on the wiki page for Dijkstra's algorithm, which still required me to figure out the optimal node representation during traversal so as not to blow up the space requirements with extra states, but I did get there in the end. My code is an absolute mess at this point, compared to previous days, but it does find the answer in ~2s.
The code is too messy to really be worth showing, but it's on my github for the morbidly curious.
If I come back and clean it up later I'll edit this comment with a more in-depth explanation of what it's actually doing.
On to part two I suppose, but I need a break first.
Edit: Part 2 is done, sort of. I took advantage of what looks like a (possibly intentional) quirk in the input that means the four quadrants can each be solved separately, using my algorithm from the first part. It's not pretty, but it works.
I think the only kind of interesting things in my solution were the pre-computed requirements map for each key, and the flood-fill distance maps for each key.
For each key, I ran a flood fill from its position out through the entire maze, storing the distance of each tile into a cache. This made finding the path distance from the robot or any other key a fast static lookup. I think this would've been more useful if I was still using my "wandering-agent" approach instead of the global dijkstra search that I ended up on. As it is, it's just used to help compute the scores/weights for each possible action.
Additionally, at the start I used a bfs path-finding from each key to the robot, tracking (but passing) each locked door on the way. The list of doors passed through is the requirements for that key, which is essential information for deciding what keys are available at any given time.