Modern C++ in Advent of Code: Day 19

It is day nineteen of Advent of Code and we are looking for an optimal robot construction blueprint.

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

Input

Our input today is a series of blueprints. We will create a custom type to represent a blueprint and take the input as std::vector<Blueprint>.

Searching for the best possible outcome

The goal for today is to determine the highest number of geodes we can collect, given a specific robot blueprint.

Since we are looking for an optimal result, our simplest approach is an exhaustive search; however, that introduces a problem. At any time, we have up to five options: build one of the four robots or simply mine. With 24 time units, this means five to the power of twenty-four, which is completely infeasible.

We will need extensive search-space pruning, and to start with, we can avoid building unnecessary robots. Notably, since we can only build one robot per time unit, there is never a need to have more producing robots than the cost to build one robot.

We can encode this logic into a State data structure, which will provide methods to determine whether we can build a robot, whether we should build a robot and finally, mutating methods to build a robot and to mine.

With that, we can build our search algorithm.

To decrease the search space further, we can greedily build geode robots and even obsidian robots (notably important for part two). Greedily building obsidian robots is a bit dangerous, as there can be a corner case where this is not an optimal move; however, it did work for my input.

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.