Modern C++ in Advent of Code: Day 16

It is day sixteen of Advent of Code and today we are releasing pressure in a volcano.

I do encourage you to try to solve it yourself first https://adventofcode.com.

Input

Our input today is a list of valves, each with a listed flow rate and neighbouring valves.

However, we need to process it further before we can work with this input. We need to filter for valves with non-zero flow rates since these are the only ones worth visiting, and we also need to calculate minimal distances between all nodes (we can use the Floyd-Warshall algorithm).

Finding the maximum flow rate

The maximum flow rate will result from a path that visits some of the valves with non-zero flows while remaining within the time limit.

We can use a simple depth-first search using the pre-calculated minimum distances. Besides finding the path, we must be careful with correctly calculating the flow rate based on the currently open valves.

This will explore all paths. However, due to the small number of valves, this is not an issue.

We have elephants

For part two, we get a helping elephant. Fortunately, this doesn’t complicate matters significantly.

Instead of trying to simulate us taking turns with the elephant, we can let the elephant try to close any open valves when we calculate our initial maximum (corresponding to not closing any more valves).

Note that this brute-force approach is very slow (~50 seconds on my machine). We could significantly speed it up by using bit-fiddling instead of unordered containers.

On top of that, I’m sure there is a more sensible solution that doesn’t rely on a depth-first search.

Links

The repository with a complete solution (including input parsing) is available here: https://github.com/HappyCerberus/moderncpp-aoc-2022.

I post daily Modern C++ content on Twitter, LinkedIn, Mastodon, Medium and Substack.