Modern C++ in Advent of Code: Day 20

On day twenty of Advent of Code we are decrypting the coordinates for the starfruit grove.

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

Input

Our input today is an encrypted message as a series of integers. We will take it as std::list<int64_t>.

Decrypting the message

Our goal for part one is to decrypt the message by reordering the elements based on their values.

Each element needs to move as many spaces as its value (to the right for positive and left for negative) while we process the elements in their original order.

This already points us to std::list as it provides cheap reordering of elements through std::list::splice and iterator stability.

To move elements around, we can implement a couple of helper functions. First, a generalized advance that also provides wrap-around semantics, then two helper functions that return the position for the splice operation. One for positive numbers and one for negative.

Putting this together, we first remember the stable ordering of the elements, then, one by one, find the correct splicing position for each element and splice it into place.

The code contains one optimization. Since moving an element by size-1 would leave in the same place, it is sufficient to move each element only by value%(size-1) positions.

To obtain the final decrypted coordinates, we re-use the advance helper function to pick out the 1000th, 2000th and 3000th elements, counted from the zero position.

Not quite decrypted

Apparently, our efforts were for nought. To properly decrypt the message, we need to multiply each element by a decryption key and then run the actual re-ordering process ten times.

Fortunately, this doesn’t affect our approach. Despite the decryption key being a very large number, we have no integer overflows on our input (if we did, we could also apply our modulo operation to the decryption key).

Re-using our previous solution, we first adjust the input using the decryption key and then apply our shuffle_once function ten times.

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.