Advent of Code 2020 - Day 3, in Kotlin - Toboggan Trajectory • Todd Ginsberg

Today we get to go tobogganing! If you’re anything like me, you’ve spent the last few minutes going down the Wikipeida Rabbit Hole trying to figure out what the difference is between a sled and a toboggan. Let me save you a trip - a sled is a flat surface with runners and can be steered. Riders on a sled are a few inches off the ground. A toboggan, on the other hand, lays flat on the ground (it is a runner) and cannot be steered as well as a sled can. The word toboggan itself comes from the Mi’kmaq First Nations people in Northern Canada.

Kotlin-wise, today we’ll override a couple of operators to make our code look nice, and write a sequence to generate paths for our toboggan!

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

Problem Input

Today we won’t do much with our input as we can use it to look up where the trees are without modification. We’ll just call our input forest today instead of our usual input, because it makes the resulting code look more fun.

class Day03(private val forest: List<String>) {

    private val width: Int = forest.first().length
    private val height: Int = forest.size

}

While we’re here talking about input, lets declare values for the width and height of the forest so we can refer to them later. Both of those values are used in calculations we’ll write when we solve Part 1. To measure the width of the forest, we take the first String from the list (the top row) and see how wide it is. To measure the height of the forest, we get its size or how many rows it has.

⭐ Day 3, Part 1

The puzzle text can be found here.

As I mentioned in the introduction, we’re going to use a sequence to generate paths through the forest, given a slope. First, let’s talk about how we’re going to represent points on the path. We’re going to use the Kotlin Pair class to do this. It has two values first and second, and we’ll type it with Ints so, it will really be a Pair<Int,Int>. Where first represents the left/right value and second represents up/down. We could have gone with our own data class to make this a bit cleaner, but Pair is a nice handy abstraction here. If this pair of numbers had meaning outside of this one class, I would define a data class.

One thing about Pair<Int,Int> though is that we can’t add them together without writing some code. To solve that, we’re going to override the plus operator on Pair<Int,Int>. We could write an addPairs(pair1, pair2) function of some kind, but this looks nicer, and does the same thing at no additional cost.

private operator fun Pair<Int,Int>.plus(that: Pair<Int,Int>): Pair<Int,Int> =
    Pair(this.first+that.first, this.second+that.second)

Kotlin lets us override a specific set of operators and plus is one of them. Now we can do things like thisPair + thatPair or myPair += diffPair. We just had to provide the code to add them together, which is done by adding the first and second values and returning a new Pair<Int,Int>.

Let’s calculate the points on our slope:

private fun path(slope: Pair<Int,Int>): Sequence<Pair<Int, Int>> = generateSequence(Pair(0,0)) { prev ->
    (prev + slope).takeIf { next -> next.second < height }
}

If you look at the very end of the first line of our function, you can see we are using the generateSequence builder and providing it a starting point of PairM(0,0). The generator also takes a lambda (what looks like the body of our function). This is used by Kotlin to create a lazy sequence. It will only generate as many values as we ask for, and only when we ask for them. Now, in principle, we could have created a List<Pair<Int,Int>> today instead because we know that these paths through the forest aren’t infinite, or that we’ll have to terminate them early. But I figured this is a good opportunity to introduce this concept as I’m pretty sure we’ll run into a more legitimate need for it in the 22 days remaining.

The good thing about the generateSequence function is that each time it is called we have access to the previous value generated (or the starting point). All we have to do is provide the next point by adding our slope to the previous location! Since our sequence will stop generating values when a null is returned, this is a good place to check that we haven’t run off the bottom of the forest. We do that by calling takeIf and calculating if we’ve reached the limit.

If you are interested in how takeIf and its counterpart takeUnless work, I’ve got post that goes into detail.

You might have noticed that while we have accounted for the fact that we might run off the bottom of the forest, we have not addressed the fact that we might run off the side of the forest yet. We’ll do that when we calculate the positions of the trees.

Given a path, we need to figure out how many trees are on it. Because our forest is represented as a List<String>, we can use the Pair<Int,Int> to index into the forest and figure out if there is a tree in our way. To make that a bit cleaner, we’re going to override another operator.

private operator fun List<String>.contains(location: Pair<Int, Int>): Boolean =
    this[location.second][location.first % width] == '#'

In this case, we’re overriding the contains operator on List<String>. Overriding contains allows us to use the in and !in operators with List<String> and Pair<Int,Int>! Do we strictly need to do this? No, but it sure will make the next step look nice and clean! Note that when we check for the location of a tree, we have consider the fact that we night have run over the width of the forest. Because the forest repeats, we will use the modulus (%) operator to calculate our index value given our true width.

Now that we have all that sorted, we can generate a path and count the number of trees on it. We’ll use the count function from the Kotlin standard library to count the number of times we run into a tree (it in forest).

private fun treesOnSlope(slope: Pair<Int,Int>) =
    path(slope).count { it in forest }

And to solve Part 1, we call treesOnSlope with our input of 3 to 1. The to infix function is provided by Kotlin and will create a Pair(3,1) for us!

fun solvePart1(): Int =
    treesOnSlope(3 to 1)

Star earned! Onward!

⭐ Day 3, Part 2

The puzzle text can be found here.

Luckily, we have almost everything we need already written. To solve Part 2, we need to run our existing Part 1 code a few times and multiply all the results together. One can presume there is no completely safe path down this mountain (which is super unfair considering we’ve saved Christmas four years in a row, but I’m not complaining) or we would end up with 0 as our answer!

Let me show you how I solved Part 2, and then we’ll go over the interesting parts.

fun solvePart2(): Long =
    listOf(1 to 1, 3 to 1, 5 to 1, 7 to 1, 1 to 2)
        .map { treesOnSlope(it).toLong() }
        .reduce { a, b -> a * b }

First we create a List<Pair<Int,Int>> (all of the slopes we need to check) by using the to infix function again. Next, we transform that slope into the number of trees we hit via map. Finally we reduce our answer by multiplying all of our answers together. If you have never seen reduce it can come in very handy! The reduce function operates over an Iterable of some type, and reduces it down to a single instance of that type. So in our case, Int (how many trees on the slope). In our case we are multiplying two numbers (a and b) together to form our answer. Kotlin will take care of calling this lambda function for us for each pair of numbers in our list.

For example, if our list is [2,3,7], our lambda will be called with (2,3) the first time. We will return 6 as the answer (2*3==6). Next, Kotlin will call our lambda with (6,7), the 6 being the answer from the last time through and 7 being the last element in the original list. The answer in this case is, of course, 42.

One thing to note here is that we return a Long and convert our treesOnSlope response to a Long as well. Originally I had kept everything as an Int but a coworker of mine mentioned that his input happened to overflow an Int here, so I made this change.

Running this code quickly solves part 2!

I hope you had fun tobogganing today, I know I did!

⭐ Day 3, Part 1

⭐ Day 3, Part 2

Further Reading