Modern C++ in Advent of Code: Day5

It is day five of Advent of Code. Today, we will be solving some equations to figure out line intersections.

As always, please try to solve the problem before looking at the solution. For all articles in this series, check out this list.

Day5: Part1

We are given a list of lines in the format x1,y1 -> x2,y2 and are tasked with determining all the points where multiple lines intersect. For Part1, we will ignore all lines that are not axial (horizontal or vertical).

When do two lines intersect? Consider a point [x,y] that is part of the intersection. Naturally, it must be true that: line1.x1 <= x <= line1.x2, line2.x1 <= x <= line2.x2, line1.y1 <= y <= line1.y2 and line2.y1 <= y <= line2.y2. If we put these formulas together, we get:

• max(line1.x1,line2.x1) <= x <= min(line1.x2,line2.x2)
• max(line1.y1,line2.y1) <= y <= min(line1.y2,line2.y2)

Given that, the intersection is then either non-existent or the line max(line1.x1,line2.x1),max(line1.y1,line2.y1) -> min(line1.x2,line2.x2),min(line1.y2,line2.y2).

Note that this works only if x1<x2 and y1<y2, which is something we can easily enforce while reading the input.

For simplicity (also, I couldn’t find the motivation to do something more complex for such a small input), we will test each line we read against all the previously read lines and keep the resulting intersection points in an unordered_set.

We will need a representation of a point and also make that point hashable since we want to store points in an unordered_set.

And we will need a representation of a line:

Since an intersection can be empty, we use std::optional to avoid complicating our Line structure (to represent empty line segments).

With our declarations done, we can write our tests:

First, we need our I/O implementation:

We read in the expected format and return early if we encounter a problem. When we run across an unexpected delimiter, we also need to set std::ios_base::badbit on the input stream (lines 11 and 35). As already mentioned, we modify the input so that start.x <= end.x and start.y <= end.y. Please note that this only works for Part1 and only for axial lines.

Finally, we implement the formulas we already discussed.

In our main, we read all lines, skip the ones that are not axial, and store all points part of an intersection.

Day5: Part2

In part2, the problem becomes more complex with diagonal lines. Because of that, we need a bit more generic solution for figuring out intersections.

There are two types of intersections to consider: single point intersections, where two line segments with different orientations intersect in a single point, or overlay intersections, where line segments with the same orientation overlap in one or more points.

We can solve overlay intersections similarly to part1, but we need a generic solution for a single-point intersection.

Consider this point of intersection [x,y]. It must be reachable on both of the lines. Therefore x = line1.start.x + m*line1.xdir and x = line2.start.x + n*line2.xdir, where m and n is the distance of this point from the line start in line1 and line2, respectively. Same for y: y = line1.start.y + m*line1.ydir and y = line2.start.y + n*line2.ydir.

We can put these equations together:

• line1.start.x + m*line1.xdir = line2.start.x + n*line2.xdir
• line1.start.y + m*line1.ydir = line2.start.y + n*line2.ydir

With two equations, we can now solve for m and n. We end up with a fraction that has two corner cases. We can be dividing by 2, but the numerator isn’t even. This happens when the diagonals cross visually, but the crossing point is on the corner of our “pixels” (e.g. lines 0,0 -> 5,5 and 0,5 -> 5,0). And we can also be dividing by zero, which happens for parallel lines. Finally, this equation can be satisfied by points that lie outside the line segments (these equations work for lines).

While our Point struct remains the same, we need to extend our Line struct. Overlay style intersections are handled by does_overlay, does_intersect and intersect , point-based intersections are handled by single_point_intersect and is_within.

Tests are more extensive for this part. I had to create special test cases to hunt down specific bugs in my code (lines 16–22).

Starting with is_within, that checks whether a point lies within a line segment. We need to make sure we don’t divide by zero when dividing by xdir() and ydir(). We check whether the point doesn’t lie outside the segment and double-check if both axes match up.

Another piece of new functionality is checking for overlay intersections. Only line segments with the same directionality and only diagonals on the same diagonal (line 10) can overlay.

Finally, our two intersection computations:

We are introducing the additional does_overlay check (line 2) and adjust the result for diagonals that slope to zero on the y axis (lines 6–8).

We check for the already-mentioned corner cases: parallel lines, an intersection in a grid corner, and outside line segments. Other than that, we are just 1:1 implementing the mathematical formula.

And we bring it all together in our main:

We again read the lines one by one and check against all already read lines. If the lines don’t overlay each other (line 6), they still might have a single point intersection (line 21).

Links and technical notes

The repository with daily solutions is available at: https://github.com/HappyCerberus/moderncpp-aoc-2021.

Check out this list for articles about the other days in Advent of Code.

And please don’t forget to try Advent of Code for yourself.

Thank you for reading

Thank you for reading this article. Did you enjoy it?

I also publish videos on YouTube. Do you have questions? Hit me up on Twitter or LinkedIn.