Advent of Code 2021 - Day 5

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Today we follow straight lines. Each is given by its endpoints as x, y coordinates. For the first part we only look at orthogonal lines (aligned with either axis), which suggests that in the second part we will use all, so we will build the method to read data considering an option to filter out the diagonal ones (the only non-orthogonal ones).

First we read each line: split on the ' -> ' to get the two endpoints, then split on the comma in each endpoint to separate the coordinates. We write it in a general way that would work for points in any dimension. We convert the endpoints to ints.

For each line we yield it, or skip it if it is not orthogonal and we have the flag. Checking orthogonality is just a matter of checking if both endpoints have the same x or y coordinate.

Part 1

The question we are asked is how many points are crossings of two or more lines. So, we will count how many lines pass each point. We start by creating a counter, a dictionary indexed by the points where we will add the lines passing. Points not in the dictionary have no lines passing, and are not relevant.

Now we only need to enumerate the points that each line passes, and add one to the corresponding counter. This is little more than a loop keeping the common coordinate constant, and the other one ranging from the minimum to the maximum of the endpoints (both included, careful of the off-by-one error: ranges in Python do not include the stopping point).

Finally, we count how many values in the counter dictionary are two or more.

Part 2

As we had foreseen, now we use all lines. The rest is just the same. Only two tweaks needed: first, remove the flag to filter non-orthogonal lines; second, we need to enumerate the points in diagonal lines, which we did not have before.

For the enumeration, we take the endpoints in the order given, and build the ranges for each x and y. The main issue is ensuring we go in the right direction. We look at the difference, and set the corresponding delta to 1 or -1 accordingly. And we add the delta to the second endpoint: adding 1 works when the range is increasing, but not if it's decreasing.

Just zip both coordinates to step along the line. The rest is just as before.