Advent of Code 2021, Day 5

Day 5! I was really hoping that our friend the giant squid would show up again, perhaps with dolphin racing tips, or even have brought friends for a few rounds of blackjack, but alas, it was not to be.

No, this time around, it’s a navigation problem, and today we’re trying to steer around weirdly geometric hydrothermal vents. And, in the process, I received an object lesson on the importance of properly understanding the actual requirements before beginning.

So, reading through the problem description, it seems that the obstacles we’re trying to avoid always appear in straight lines, and we want to avoid the places where lines intersect, since those present the greatest problems for our submarine’s increasingly bizarre navigational computer.

Nice, I thought. The standard Java libraries have a fully featured 2D graphics library which can, among other things, represent lines in the plane and determine whether they intersect. Load the data with a quick regular expression to extract the numbers, plug those into a Line2D object, and check each pair of lines for intersections using two nested loops.

Part 1 specifies that only horizontal and vertical lines should count. This is a pretty clear sign that part 2 is going to relax that restriction, so I implement this in its own function that I can set to either filter non-horizontal and -vertical lines out or not as required. Run that, spit out the number of intersections, and done.

Uh oh. The test data expects 5 intersection points for its answer, but my code is only finding 3, and my test fails.

So, I go back to the problem description. It doesn’t want the number of lines that intersect. It wants the number of grid squares in which two or more lines intersect.

This isn’t just an academic distinction. I was treating these lines like ideal mathematical lines, with no width, but they’re actually lines of 1x1 grid square that are adjacent to each other. Two of those lines in the test data are colinear - they’re in line with each other but with different start and end points, and some overlap in between. They intersect, which I was counting once, but they do so across three squares.

So. What I need to do now is rasterize the lines. Great, you may think, I was already using the Java 2D graphics library for this, I can just render the lines and check which pixels are filled, right?

Well, no. If you know me, you know I wasn’t thinking that. My initial idea was already insufficiently needlessly elaborate. No, what I decided to do was implement the general case of Bresenham’s line algorithm, because of course I did.

So. I make my own Point and Line classes, completely ignoring the ones I was using before, and implement Bresenham’s on the Line class. Who knows, might need this in a future puzzle.

Bresenham’s algorithm is one of the foundational parts of computer graphics, and it’s so elementary that most people, even those doing computer graphics, never really think about it. Now, I’m going to let you in on something of an open secret in the software industry: when you need an implementation of a classic algorithm like this, the psudocode examples on Wikipedia are actually really good, and you can use something pretty close to them for a basic implementation.

Mine looks like this:

int dx = b.x - a.x;
int xStep = dx >= 0 ? 1 : -1;
dx *= xStep;
int dy = b.y - a.y;
int yStep = dy >= 0 ? 1 : -1;
dy *= yStep;

if (dx >= dy) {
    int D = 2 * dy - dx;
    int y = a.y;
    for (int x = a.x; xStep == 1 ? x <= b.x : x >= b.x; x += xStep) {
        points.add(new Point(x, y));
        if (D > 0) {
            y += yStep;
            D -= 2 * dx;
        }
        D += 2 * dy;
    }
} else {
    int D = 2 * dx - dy;
    int x = a.x;
    for (int y = a.y; yStep == 1 ? y <= b.y : y >= b.y; y += yStep) {
        points.add(new Point(x, y));
        if (D > 0) {
            x += xStep;
            D -= 2 * dy;
        }
        D += 2 * dx;
    }
}

Not bad. Not quite as elegant as someone who really worked at it could make it, but not bad. The basic case of Bresenham’s only works for lines that move down and to the right at an angle of 45° or less off of horizontal. You need to play around with the coordinates a bit to deal with the other seven octants of the circle.

So I wrote my test class with ten cases: horizontal lines, vertical lines, and a line offset a bit from each of the eight points of the compass rose with a slope of 5:2. That produces a very particular pattern when rendered with Bresenham’s which looks like ''··., and the coordinates are easy to write and test for. Then I started with the general case that worked for east on my compass, and added special cases to handle each of the transformations I needed to complete the set.

Complete overkill. So much fun. Entirely in the spirit of Advent of Code.

Once I’d done that, it was just a matter of rendering every line and checking for common points on the grid between them. Kept the conditional filtering because I was reasonably sure that part 2 would just be about relaxing the restriction, and all good.

And then, sure enough, part 2 rolls around, and the horizontal-or-vertical-only restriction is lifted, but it brings a new one: the remaining lines are all perfect 45° diagonals. As I suspected, implementing the full Bresenham’s algorithm was complete overkill, but it works for this. Set the filter flag to false, and it spits out the part 2 answer. My solution is in the usual place.

Maybe I’ll use this algorithm in a future part, maybe not, but that wasn’t really the point, was it?