Daily bit(e) of C++ | Advent of Code: Day 8
Daily bit(e) of C++ #341, Advent of Code using Modern C++: Day 8.
Welcome to day 8 of Advent of Code using Modern C++. Before you start reading, I highly encourage you to try to solve the two problems yourself: https://adventofcode.com/2023/day/8.
If you missed it, I have prepared a template repository for C++, with a development environment (through a devcontainer) with a bleeding edge version of the C++ toolchain: https://github.com/HappyCerberus/aoc-2023-cpp.
Today, we are counting the steps to reach our destination on Desert Island.
Parsing
Let’s start with parsing the input and implementing a step function (a function that takes one step in the specified direction) that we will need for both parts.
Fortunately, the input has a straightforward format, allowing us to skip over non-uppercase characters.
Part one
To implement the part one solution, we only need to repeatedly call the step function, starting in state “AAA”, until we reach the state “ZZZ” and then return the number of steps taken.
Part two
This part is a recurring type of problem that I honestly do not enjoy. The solution relies on patterns only present in the input we are processing.
The first observation is that if the ghosts are to meet up at all, they have to enter a loop at some point. The proper solution requires you to take two logical leaps. First, the loop ends aligned with the instructions, and the loop has no prefix (the only steps each ghost does are in its one loop).
Fortunately, these can be at least easily verified. However, once we know this is true, figuring out the first time the ghosts meet up is straightforward. It is simply the least common multiple of the loop lengths.
We have to adjust our parsing to extract all the starting positions.
Then, we can adjust the code from part one, adding verifications for our assumptions and calculating the least common multiple.
Conclusion
How did you do with today’s problems? Did you find the loop pattern in the input?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.