Modern C++ in Advent of Code: Day 21

Today is the twenty-first day of Advent of Code and we are trying to guess what the monkeys are up to.

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

Input

Our input today is a list of monkeys, where each monkey either reports an integer value or calculates an expression based on the values of other monkeys. Since, in either case, we are interested in the final value, we will hide this distinction inside of a Monkey class using a std::variant. We then take the input as std::unordered_map<std::string, Monkey> since we will need to look up monkeys by their names.

Calculating

To calculate the result of the root monkey, all we need is to implement the recursive logic of a monkey evaluating its expression. The only tricky part is how a monkey gets hold of the values it needs to calculate its expression.

Since we already have a lookup map with the monkeys, we could give each monkey a pointer to it; however, a cleaner solution is to give each monkey a query function that takes the name of the monkey and returns the value (this added complexity will come in handy in part two).

What’s the magic number?

For part two, we have a trickier goal. Instead of “humn” being a monkey, it’s us, and we need to come up with a number that will make the root monkey end up with equal operands.

Before we start solving, we need two things.

First, we need to adjust the logic for the root monkey (we can change it to minus, making it produce zero when the operands are the same).

Second, we need a way to inject our human value into the evaluation process. Since we already give each monkey a query function, we can do it there.

Finally, let’s try to solve the problem of finding the correct value. Let’s assume that the expression containing our value is monotonic. If it isn’t, we are in proper trouble.

However, if the expression is monotonic, we can use binary search. If we start with two inputs that produce values with different signs, we know that our solution is somewhere between them. We can then bisect this interval, always choosing the interval that produces values with different signs until we find our input that produces zero.

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.