Module 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.