Expand description
§Donut Maze
The approach to this solution is very similar to Day 18 however parsing the maze
cleanly is quite tricky.
We first simplify the problem by running a breadth first search from each portal creating a list of distances between each pair of portals.
Then a second BFS over this list efficiently solves both parts. For part two we use a cache to memoize previously seen values. We optimize part two further by not recursing deeper than the number of portals as this would mean a redundant trip to an already visited portal.
Structs§
- Edge 🔒
Enums§
- Tile 🔒
Functions§
- Parsing takes two passes. First we find the location of each portal. Then we BFS from each portal to build a list of distance pairs.
- Straight BFS with no caching or any optimization tricks.
- BFS with memoization of previously seen states.
Type Aliases§
- Key 🔒