Advent of Code 2022 - Day 9, in Kotlin - Rope Bridge • Todd Ginsberg

I enjoyed today’s puzzle, this is one of my favorites of 2022 so far! In our solution we’ll perform some refactoring between Part One and Part Two to make our solution easier to manage.

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

Puzzle Input

In today’s puzzle, we receive our input as a set of instructions, one per line, which we’ll import as a List<String>.

class Day09(input: List<String>) {

    private val headPath: String = parseInput(input)
}

We’ll parse this input from a List<String> to a single String called headPath, where each character of the headPath represents a single instruction. Why do we do this? Personally, I find "UUUU" easier to deal with than "U 4".

// In Day09

private fun parseInput(input: List<String>): String =
    input.joinToString("") { row ->
        val direction = row.substringBefore(" ")
        val numberOfMoves = row.substringAfter(' ').toInt()
        direction.repeat(numberOfMoves)
    }

To parse the input, we call joinToString over the List<String> taking care to specify that the delimiter we want is "" (no delimiter). For each element in the input, we calculate the direction via substringBefore and the numberOfMoves via substringAfter, and then converting it to an integer via toInt. Because there is a repeat function on String, we can use that to multiply our direction by the numberMoves. Joining all of these together gives us a nicely formatted String of headMoves.

⭐ Day 9, Part 1

The puzzle text can be found here.

The first thing we know for a fact we need is a Point class to keep track of where we are on the grid. Some things to remember are that the grid is unbounded, and we don’t really care what the actual place values are, just how they relate to each other. I’m tempted to pull this Point class out into its own top-level definition as I’m pretty sure we’ll need another. However, I’m going to leave this as a private inner class in Day09 because I suspect we’ll want a more fully-featured Point2D (or Point3D) class like we’ve had in years past. I’ll wait until that happens.

// In Day09

private data class Point(val x: Int = 0, val y: Int = 0) {
    fun move(direction: Char): Point =
        when (direction) {
            'U' -> copy(y = y - 1)
            'D' -> copy(y = y + 1)
            'L' -> copy(x = x - 1)
            'R' -> copy(x = x + 1)
            else -> throw IllegalArgumentException("Unknown Direction: $direction")
        }
    }

At first, we’ll define Point to have two properties (x and y representing coordinates) and a move function. The move function takes a Char representing the direction we want to move relative to the Point it is being called on, and returns a brand new Point. We take advantage of Kotlin’s when for this, looking for all of the valid inputs and throwing an exception if we get an invalid input. While I can guarantee that the Advent of Code input won’t throw any surprises at us (unlike real production code!), Kotlin can’t know that and demands that our when expression be what’s called “exhaustive”. Meaning, it always produces a result no matter what.

Note that the default values for the x and y properties is 0. We do this because that is the origin spot, and we create a few Point instances today and it saves us the hassle of specifying it during instantiation. Because we don’t actually care what x and y are when we start, you can pick anything for these! Zero just makes the most sense for me and is helpful for debugging.

To do the actual movement, we take advantage of the fact that Point is a data class and comes with a copy function. With this we can just specify what changes during our move. Granted, there are only two properties so copy isn’t all that useful here. But if you have a data class with more than a handful of properties and only a couple of them change, you’ll be thankful that copy exists.

At this point, lets stop and write our main logic for Part One in a function called followPathToBeRefactored. Maybe you can see where this is going? In Part Two we’ll replace this version with a newer, better version. I just don’t want to explain line-by-line replacements later so instead I’m writing this function knowing we’ll throw the whole thing away. Fair warning, this function refers to some other functions on Point that we haven’t written yet (we will below) because I think it might be easier to understand the logic of the whole process before we implement the details. And indeed, this is usually how I write my code - algorithm first, and then implement the details later.

// Day09

private fun followPathToBeRefactored(): Int {
    var head = Point()
    var tail = Point()
    val tailVisits = mutableSetOf(Point())

    headPath.forEach { direction ->
        head = head.move(direction)
        if (!head.touches(tail)) {
            tail = tail.moveTowards(head)
        }
        tailVisits += tail
    }
    return tailVisits.size
}

Let’s go over followPathToBeRefactored. First, we set aside two new Point instances to represent the head and the tail of the rope. We also create a MutableSet<Point> called tailVisits to hold all of the unique Points that the tail has visited. Ultimately, the size of this set will give us our answer.

Next we start in on following instructions. We loop through each direction command in the headPath and do what it says. The first order of business is to move the head in the direction specified. We’ve already written move so this should work already.

With the head taken care of we need to take care of the tail. The puzzle calls for a somewhat complicated set of actions to take place with the tail after the head, but if you think about it, it comes down to “If the head and tail don’t touch, move the tail towards the head”. So we know eventually we know we’ll need two new functions on Point - one called touches to see if two Point objects touch one another, and one called moveTowards to move a Point in the general direction of another Point.

At the end of this loop we add the tail to the tailVisits set to record where it has been. At the end of this function, we return the size of the tailVisits set.

Now let’s write our touches function on Point:

// In Day09.Point

fun touches(other: Point): Boolean =
    (x - other.x).absoluteValue <= 1 && (y - other.y).absoluteValue <= 1

To figure out how touches works lets imagine a grid with two spots filled that happen to be next to one another. Looking at it, we can see that they touch. But how do we know? What if we’re only presented with coordinate data? We know if two spots touch if their x and y coordinates are at most 1 away from each other. If either x OR y are farther away that one place, the points on the grid don’t touch. We’ll use that to derive our answer. For both x and y, we subtract the current value from the other value (or vice versa, it doesn’t matter) and take the absoluteValue of the result. If both of these calculations results in 0 or 1, the Point objects touch one another.

Now let’s write moveTowards:

// In Day09.Point

fun moveTowards(other: Point): Point =
    Point(
        (other.x - x).sign + x,
        (other.y - y).sign + y
    )

The first thing to notice is that moveTowards returns a new Point object. To calculate the new x and y coordinates after a movement takes place, we subtract the source (this) x and y coordinates from the target (other) x and y coordinates. We don’t really care about the actual values here, per se, just the sign of them (so if the answer is -3, we only care that it is negative, so -1 will do). Thankfully, Kotlin has a handy sign function on Int to do this work. We can add that sign value to both x and y and that results in a new Point that has moved towards the other point.

And now we can solve Part One!

// Day09

fun solvePart1(): Int =
    followPathToBeRefactored()

Star earned! Onward!

⭐ Day 9, Part 2

The puzzle text can be found here.

OK, so basically we’re following the same logic we just implemented but with a few more knots, and not just a head and tail. But if you think about it, each knot (except the ends) is both a head and a tail, depending no how you look at it. It is a tail the first time it is pulled along by its head, and then becomes a head relative to the knot behind it, which becomes the tail.

So let’s rewrite our followPath function with that in mind.

// Day09

private fun followPath(knots: Int): Int {
    val rope = Array(knots) { Point() }
    val tailVisits = mutableSetOf(Point())

    headPath.forEach { direction ->
        rope[0] = rope[0].move(direction)
        rope.indices.windowed(2, 1) { (head, tail) ->
            if (!rope[head].touches(rope[tail])) {
                rope[tail] = rope[tail].moveTowards(rope[head])
            }
        }
        tailVisits += rope.last()
    }
    return tailVisits.size
}

Before we set up a head and tail as individual values. Here, we’re going to create an Array of Point objects to represent the entire rope, all at the origin. We’ll keep the concept of tailVisits from the previous version. We still generally do the same work by iterating through each direction in the headPath and moving the head. The head is always going to be the first element of the rope array, so we can move it and set rope[0] to the new location of the head.

But what about the knots that follow? Kotlin Standard Library to the rescue! We’ll look at all the knots in the rope and get the indices of them. This just gives us numbers instead of actual points, but since we’re going to write over the spots in the rope array, this is what we want. We take a windowed view of these indices of width 2, sliding over 1 place each time. So if we start with [0, 1, 2, 3, 4...] we end up with [0,1], [1,2], [2,3], [3,4].... The first element in the windowed array is the index in the rope of the head and the second element is the index of the tail. We use Kotlin’s support for destructuring to pick these out and name them head and tail.

The logic we do with head and tail is identical to Part One, except we have to deal with the fact that they are elements in rope now. So our logic stays the same but we refer to their positions rather than the actual head and tail points themselves.

And now we can solve Part Two by passing 10 (the number of knots) to the followPath function! I’ve also included what Part One looks like now for completeness. You can delete the followPathToBeRefactored function.

// In Day09

fun solvePart1(): Int =
    followPath(2)

fun solvePart2(): Int =
    followPath(10)

Star earned! See you tomorrow.

⭐ Day 9, Part 1

⭐ Day 9, Part 2

Further Reading