Modern C++ in Advent of Code: Day 17

On day seventeen of Advent of Code we are simulating dropping rocks.

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

Input

Today’s input is a single line describing the jet patterns that will dictate how we move our pieces.

Simulating the dropping pieces

We are simulating our pieces in a narrow chamber.

We don’t need much functionality for the chamber itself, just the storage, and to simplify the rest of the code, two helper methods: one for checking whether a space is empty (and not out of bounds) and a second helper method to adjust the current maximum height of the pieces and to reserve enough capacity so that the next piece will fit.

We are working with five unique shapes.

One way to handle this is to introduce a custom class for each shape that encapsulates movement logic and collision detection. This approach is a bit verbose, but by establishing a common static interface, we can then use a variant of all the shapes and treat them uniformly.

With all the pieces implemented, we can now simulate a single piece by repeatedly moving it first left or right and then down. Once we are stuck on the move down, we know that the piece is in its final place.

At that point, we draw the piece and update the maximum height.

Simulating all the pieces is simply an iteration over the given number of pieces, simulating one after another.

Finding a cycle

We obviously cannot simulate 1000000000000 pieces. Even if we processed one per CPU cycle, it would still take infeasibly long.

We need to find a pattern, notably a cycle, in the simulation and then only simulate the start and end of the simulation, skipping over the repeating pattern in the middle.

We can split this approach into three pieces.

First, a simulation that uses detected cycle information and skips over the middle part.

Second, a verification function that validates whether a potential cycle is a proper cycle.

Finally, we can put this together in the third function. A search simulation that simulates until it detects a potential cycle (we can use the column positions of the last five pieces) verifies that it is indeed a cycle and, if it runs, simulates with the now detected cycle.

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.