Daily bit(e) of C++ | Advent of Code: Day 16

Daily bit(e) of C++ #349, Advent of Code using Modern C++: Day 16.

Welcome to day 16 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/16.

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 melting some rocks by tracing beam paths.

Part one

I decided to use a straightforward BFS search for both parts, which works fine; however, I suspect that the intended solution is to compute (and cache) sections of beams.

When we exit an active component (mirror, splitter), we next hit a wall or another component. We can either pre-compute or cache these sections of beams and then traverse the sections instead of traversing all positions the beam will enter.

However, as I said, the straightforward BFS is good enough to brute-force the solution for this problem.

We start with the representation of beam positions; we need these to be hashable.

After that, we need a basic BFS search, starting at position {0,0} and advancing to the right.

Part two

As I mentioned, I brute-forced both parts. So the only thing left for part two is to iterate over all starting positions, keeping track of the maximum.

Conclusion

How did you do with today’s problems? Did you also brute-force the problem?

Share your solutions and insights. Check out the repository with solutions and links to all articles: https://github.com/HappyCerberus/aoc-2023-cpp-solutions.

---