Module day20

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 🔒

Maze

Enums

Kind

Tile 🔒

Functions

parse

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.

part1

Straight BFS with no caching or any optimization tricks.

part2

BFS with memoization of previously seen states.

Type Aliases

Key 🔒