Daily bit(e) of C++ | Advent of Code: Day 21
Daily bit(e) of C++ #354, Advent of Code using Modern C++: Day 21.
Welcome to day 21 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/21.
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 calculating reachable spaces.
Part one
We aim to determine how many spaces are reachable in exactly N steps. This sounds like BFS; however, unlike BFS, we can waste our steps by stepping forward and back.
If you want an optimal solution, you can consider that spaces belong into two categories: spaces reachable in an even number of steps and spaces reachable in an odd number of steps. Once a space is reached, it will keep getting revisited every two cycles (the space visits a neighbour, and the neighbour pays back the favour the next cycle).
However, the number of steps is low enough that we can brute-force the solution.
Part two
If you just read the problem description, it might seem completely intractable. That is, until you have a look at the input.
Our input is a square with some interesting properties. The row and column with our start are otherwise empty. The outside rows and columns are also empty. On top of that, all spaces that are 65 away from the start and from each corner are also empty (forming a neat diamond shape).
Now, consider which spaces will be reached in 65 and 65+131 steps.
This is a suspiciously regular structure. If you investigate the requested number of steps, that number has the form q*131+65.
You could calculate the number of reachable spaces in each shape chunk, considering the odd/even pattern, which will form a checkerboard structure between tiles.
However, the structure is so regular that we can extrapolate the result if we calculate the values for 65+0*131, 65+1*131 and 65+2*131. We can use a tool like Wolfram Alpha to produce the quadratic formula expressing the number of reachable spaces.
The specific values will differ based on your input; ultimately, the result is just a formula.
Conclusion
How did you do with today’s problems? Did you use the mathematical approach?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.
