aoc::year2019

Module day20

Source
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§

Enums§

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§