Daily bit(e) of C++ | Advent of Code: Day 20
Daily bit(e) of C++ #353, Advent of Code using Modern C++: Day 20.
Welcome to day 20 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/20.
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 simulating digital signals.
Part one
The first part is a bit misleading since it implies loops in the input. However, our proper input doesn’t loop within 1000 pushes of the button.
One way to solve this problem is to build a small simulator. We can represent each module type with a class. Each class then implements a method for processing one signal, and we will also need a helper to determine the incoming connections for Conjunction modules.
All the above modules refer to ConnectionMesh, our central state. We need a place to hold the current queue of unprocessed signals, handle parsing and implement the dispatch of signals.
This leaves us with our main loop, where we click the button 1000 times (waiting for all signals to be processed after each click).
Part two
The second part requires you to think a bit outside the box. If you try and brute-force the answer, you will quickly realize that none is forthcoming. So, let’s do a bit of snooping. “rx” in the input is connected to a Conjunction module.
A Conjunction module will generate a low signal only when it receives a high signal and the last signal from all other connected modules was high. And this is a point when we need to make a leap of faith. For this problem to be solvable, the high signals must come with periodic timings. Our result would then be the least common multiple of the periods.
We can keep track of the high signals observed by the Conjunction module (in my case, it was “zr”).
With this information tracked, we can now detect the loops and calculate the lowest common multiple of the periods.
I should note, however, that this is a bit loosey-goosey. Technically, I’m not exactly checking the correct period. The high signals must also line up inside the signal processing loop, i.e. on the correct signal count offset. However, the answer this approach generated was accepted as correct.
Conclusion
How did you do with today’s problems? Did you notice the crucial Conjunction module?
Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.