Module aoc::year2022::day16

Proboscidea Volcanium

Parsing

First we simplify the graph formed by the valves. With the exception of AA there’s no need to stop at any zero valve, so we’re only interested in the distance between non-zero valves. This significantly reduces the complexity of the solution space as there are only around 15 non-zero valves versus around 60 valves total.

For each valve we find the distance to its immediate non-zero neighbors. Then we use the Floyd Warshall algorithm to find the distance between any two non-zero valves, storing this information in an adjacency matrix for fast lookup.

Part One

The approach is branch and bound enumerating every possible combination combined with a heuristic to prune those combinations in order to achieve a reasonable running time.

The heuristic assumes that we can visit all remaining valves in descending order of flow, taking only the minimum possible time to reach each valve. As this will always be better than the actual maximum possible we can immediately prune any branch that would still be less than the current high score.

Part Two

Part two uses an ingenious approach from @korreman.

First calculate the maximum value for any possible combination of valves reachable in 26 minutes by a single entity. Then calculate a second score from the remaining unopened valves.

The neat part is using this second score as the heuristic threshold for a search over all possible valve combinations. This works as the sum of the first two searches provides a minimum baseline. If a branch can’t do better then it can be pruned.

Then we check every possible pair formed by those values, considering only the pairs where the sets of valves are disjoint, which is when you and the elephant have visited different sets of valves.

Structs

• Input
  Simplified graph of valves. Valves are stored in descending order of flow so the valve at index 0 has the highest flow, valve at index 1 the second highest and so on. This descending order is used by the heuristic to prune branches.
• State 🔒
  State of a single exploration path through the valves.
• Valve 🔒
  Intermediate struct for parsing only.

Functions

• explore 🔒
• parse
• part1
  Explore the tunnels, finding the highest possible score for a single entity.
• part2
  Return the maximum possible score from two entities exploring the tunnels simultaneously.