Modern C++ in Advent of Code: Day 15

On day fifteen of Advent of Code we are looking for a distress beacon and working with intervals.

I do encourage you to try to solve it yourself first https://adventofcode.com.

Input

Our input for today is a list of sensors, each with a coupled (closest) beacon. We will create a custom type to represent a sensor, with the entire input being std::vector<Sensor>.

Supporting data structures

I already mentioned that we would create a type to present a sensor. With that, we will also need a type to represent a position, and finally, we can bring back the type representing intervals from day four.

The interval type will represent the coverage a given sensor has on a given row.

We use the std::optional to support empty coverage.

Calculating coverages

Calculating the coverage of a single sensor is easy, but we have many sensors, meaning that we will end up with many (potentially empty) intervals.

To get to something sensible, we need to merge them. This will leave us with (still potentially many) intervals that are not overlapping, which immediately gives us the solution to part one of today’s problem.

For part two, we need to find a specific row with a coverage gap. Notably, on the provided input data, all coverages on all rows merge into a single interval except for one.

Links

The repository with a complete solution (including input parsing) is available here: https://github.com/HappyCerberus/moderncpp-aoc-2022.

I post daily Modern C++ content on Twitter, LinkedIn, Mastodon, Medium and Substack.