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

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

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

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 the distances of galaxies while taking into account the universe's expansion.

Part one

Calculating the distance of two galaxies without the expansion is straightforward. We calculate the absolute difference between the two position coordinates.

To account for the expansion, we need a fast way to look up the number of empty rows and columns between two coordinates. This is a lookup based on a threshold, so the fast solution is to store the empty rows/columns in a sorted order (store their indexes) and lookup using lower_bound and upper_bound.

We can use views to filter for empty rows:

Filtering for empty columns is a bit more involved since while we can obtain a column view by using std::views::stride, to iterate over all columns, we have to combine std::views::drop with a range of offsets.

With empty rows and columns, we have enough information to implement the distance calculation. As a reminder, upper_bounds returns the first element where value < e, and lower_bound returns the first element where e < value is false (i.e. e >= value).

We are left with the final step. We have to calculate the distance between each pair of galaxies. One systematic way to do that is to iterate over all galaxies and, for each galaxy, produce the sum of distances to all previously seen galaxies.

The only thing we are missing is a way to get a list of galaxies, which we can obtain using a nested view. If we have a line, we can filter it for galaxies and then transform each galaxy into its coordinate. We can apply this to a view of lines, leaving us with a view of views of galaxy coordinates, which we can then flatten using std::views::join.

Part two

For part two, we have effectively nothing to do. The only thing that changed is that now we should count every empty row and column 1000000 times.

The only adjustment we need is in our distance helper.

Conclusion

How did you do with today’s problems? Did your solution for part one also work for part two?

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

---