Advent of Code 2021 - Day 5, in Kotlin - Hydrothermal Venture • Todd Ginsberg

Let’s get ready to draw some lines! In today’s solution we’ll learn about several powerful functions in the Kotlin standard library, and a couple of functional programming concepts. I hope you have fun with this one, I sure did. Just be aware that if you are trying to solve part one without spoilers for part two, I do jump ahead here. So just watch out.

If you’d rather just view code, the GitHub Repository is here .

Problem Input

Before we get into parsing, let’s define a class to represent a Point. We’ll call this Point2d and store it in a file called Geometry.kt. Remember, in Kotlin we can put as many classes or functions in a file as we want, so we’ll put all of our geometry and location work in there for Advent of Code 2021.

// In Geometry.kt

data class Point2d(val x: Int, val y: Int)

Don’t worry if that appears to be a bit sparse, we’ll add some functions later as we need them.

Now that we have that, we can parse our intput. Today, we’ll store each of the instructions into a List<Pair<Point2d, Point2d>>. Each row is a Pair and each side of the arrow is a Point2d within the Pair. Since we have a bunch of them, we’ll store them in a List.

class Day05(input: List<String>) {

    private val instructions = input.map { parseRow(it) }

    private fun parseRow(input: String): Pair<Point2d, Point2d> =
        Pair(
            input.substringBefore(" ").split(",").map { it.toInt() }.let { Point2d(it.first(), it.last()) },
            input.substringAfterLast(" ").split(",").map { it.toInt() }.let { Point2d(it.first(), it.last()) }
        )
}

The parseRow function makes use of two of my favorite Kotlin standard library functions - substringBefore and substringAfterLast. By using these two along with split, we can succinctly parse the String for today’s input without having to learn about Regular Expressions.

⭐ Day 5, Part 1

The puzzle text can be found here.

Before we get started, I want to warn you that we’re going to do more work than is strictly necessary to solve part one, for a couple of reasons. First, we’re being asked to filter out diagonal lines. Why put them in the puzzle if we’re not going to use them? We probably are, so let’s figure them out. Second, I know how part two goes, and it’s just easier to explain everything if we assume some things we could probably guess from the puzzle text.

First, let’s give our Point2d the ability to tell us if it shares an axis with another point. This should allow us to filter for points that are directly horizontal or vertical to one another:

// In Point2d:

infix fun sharesAxisWith(that: Point2d): Boolean =
    x == that.x || y == that.y

If you haven’t seen infix before, let me explain that. The infix keyword tells Kotlin that we might want to call this function in a special way. Both of these are valid ways to call sharesAxisWith

// EXAMPLE ONLY: 

somePoint.sharesAxisWith(someOtherPoint)   // Not using infix

somePoint sharesAccessWith someOtherPoint  // Infix

By using infix, our function looks more like it is part of the language itself and is easier to read (subjective: to me). Note that even though we define our function as infix, we can still call it the traditional way. Both ways I’ve illustrated above will work.

And now that we know that, we can add a function to draw lines between two Point2d objects:

// In Point2d

infix fun lineTo(that: Point2d): List<Point2d> {
    val xDelta = (that.x - x).sign
    val yDelta = (that.y - y).sign

    val steps = maxOf((x - that.x).absoluteValue, (y - that.y).absoluteValue)

    return (1 .. steps).scan(this) { last, _ -> Point2d(last.x + xDelta, last.y + yDelta) }
}

The first two lines of this function figure out what kind of delta we need to apply to x and y for each new Point2d we will generate. We can use the handy sign function (which I didn’t originally know about, thanks u/clouddjr!), which allows us to figure out how many to add or subtract from each point to move it one spot in the x or y direction. Next, we need to figure out how many points we will have on our line. This is done by finding the maximum distance between the x values for both points and the y values for both points. Finally, we set up a range from 1 to the number if steps we need to take and use scan, a nice new function in the Kotlin standard library. The scan function works almost like a fold (we iterate over something and carry state along for each iteration). The major difference is that fold only keeps the last value and scan keeps every value we generate. Perfect for drawing a line! The lambda we pass to scan generates a new point one-off from the previous point, and the whole function returns them as a List. Pretty handy! Oh, and if you’ve never seen _ before, that’s Kotlin-shorthand for “I don’t care”. We don’t care about the range value, we ignore it.

Before we solve part one, let’s get a brief lesson in a functional programming concept called Higher-Order Functions. A Higher-Order function is a function that either takes a function as an argument, or returns a function as a result. This can be very handy because we can write a function generically (as we are about to do) but let our caller provide a piece of the logic in the form of a function.

We now have enough to solve part one of our puzzle. Let’s encapsulate this logic into a function called solve, which takes a Higher-Order function telling us what instructions to work with (again: I’ve read ahead and we’ll need this for part two).

// In Day05

private fun solve(lineFilter: (Pair<Point2d, Point2d>) -> Boolean) =
    instructions
        .filter { lineFilter(it) }
        .flatMap { it.first lineTo it.second }
        .groupingBy { it }
        .eachCount()
        .count { it.value > 1 }

Our Higher-Order function in this case is lineFilter. This tells Kotlin: “Give me a function that takes a Pair<Point2d,Point2d> and returns a Boolean”. First, we use this to filter in anything we want. More on actually calling this function below. Next, we want to turn each Pair<Point2d,Point2d> into a List<Point2d> representing a line between them. We flatMap here rather than map because if we map we’ll end up with List<List<Point2d>> and we just want one single list - List<Point2d>, and flatMap handles that for us. This is a single list representing every point we’re going to look at. Next, we can use groupingBy and eachCount from the Kotlin standard library to group the points into a Map<Point2D, Int>, where the key is a point and the value is how many times we’ve seen it. Finally, we can count the number of values in that map that are more than 1 - meaning we’ve drawn a line over that Point2d more than once.

Calling this function with our line filtering logic solves part one:

// In Day05

fun solvePart1(): Int =
    solve { it.first sharesAxisWith it.second }

Our line filtering function is that sharesAxisWith infix function we wrote way back at the start of the solution. This tells our solve function to only keep lines that are not diagonals.

Star earned! Onward!

⭐ Day 5, Part 2

The puzzle text can be found here.

Because we wrote so much code to parse our input and solve part one, we’re all set for part two. The only difference between part one and two is which instructions we care about. In part one, we only want horizontal or vertical lines but in part two we want of the line instructions. Thankfully our line drawing algorithm handles both cases. This means that if we pass a filter to our solve function that accepts any line, we’re done.

// In Day05

fun solvePart2(): Int =
    solve { true }

In this case we don’t have to do any filtering so we can just pass true and the filter in solve will accept all of the lines. Does this mean we waste some time? Yes. Does this also lend itself to a nice clean solution? Also, yes.

Star earned!

⭐ Day 5, Part 1

⭐ Day 5, Part 2

Further Reading