Skip to Content

# Advent of Code 2020 - Day 3, in Kotlin - Toboggan Trajectory

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 3: 'Toboggan Trajectory'

Posted on

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 `Int`s 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!

#### Further Reading

1. Index of All Solutions - All posts and solutions for 2020, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 3
4. Advent of Code - Come join in and do these challenges yourself!