Module aoc::year2021::day12

Passage Pathing

Our basic approach is a DFS through the cave system, exploring all possible permutations of the paths and finishing whenever we reach the end cave.

To speed things up, 2 strategies are used, one high level and one low level:

• Memoization (or caching) of the possible paths from each position, taking into account previously visited caves is the high level strategy to re-use work and save time.
• Bit Manipulation to store both the graph of cave connections as an adjacency matrix and the list of visited caves compressed into a single u32 is the low level strategy to quickly and efficiently store the small cardinality set of caves.

Structs

• Input
• State 🔒

Constants

• END 🔒
• START 🔒

Functions

• explore 🔒
  Convenience method to create initial state.
• parse
  Parse the input into an adjency matrix of edges compressed into u32 bitfields.
• part1
  Explore the cave system visiting all small caves only once.
• part2
  Explore the cave system visiting a single small cave twice and the other small caves only once.
• paths 🔒
  Core recursive DFS logic.