Skip to Content

# Advent of Code 2020 - Day 13, in Kotlin - Shuttle Search

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 13: 'Shuttle Search'

Posted on

It took me a while to find a solution to part 2 today, but I’m happy with what I ended up with. It’s probably not the solution most mathematicians would have gone with, but it solves our puzzle quickly enough, and I can explain it, which is always an important factor.

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

Problem Input

We’ll take our input from the file into our solution class as a `List<String>` today. From there, we will grab the first line as-is and convert it to an `Int`. Next, we will filter out any non-digits in the second line of input and turn that into a `List<Int>`, where each `Int` represents a bus:

``````
class Day13(input: List<String>) {

private val startTime: Int = input.first().toInt()
private val busses: List<Int> = input
.last()
.split(",")
.mapNotNull { s -> if (s == "x") null else s.toInt() }
}
``````

I really like things like `mapNotNull` because it greatly simplifies the parsing and filtering.

#### ⭐ Day 13, Part 1

The puzzle text can be found here.

Our approach to Part 1 will be to increase the `time` until we find one where any bus shows up. We’ll take the first answer we can generate this way.

``````fun solvePart1(): Int =
generateSequence(startTime) { it + 1 }
.mapNotNull { time ->
busses
.firstOrNull { bus -> time % bus == 0 }
?.let { bus -> Pair(time, bus) }
}
.first()
.run { (first - startTime) * second }
``````

We use a `generateSequence`, staring with `startTime` and increasing by 1 each time through. We could probably have used a `while` loop here, but I like that this is one single expression.

Next we take that `time` and we either find a bus that shows up in that time, or we discover that none of them do. Supposing a bus shows up, we map the `time` and the `bus` to a `Pair<Int,Int>` by using `let`. We will take the first non-null value this sequence/map will generate for us. Using `run`, we take our `Pair<Time,Bus>` and do the math for our answer.

Star earned! Onward!

#### ⭐ Day 13, Part 2

The puzzle text can be found here.

Because we need to know not only the bus number but where it was in the input, we’ll need to re-parse our input. We could potentially use this new structure to solve part 1, but I’m not going to do that here.

First, let’s define a data class to represent a bus and its indexed in the original input. We could use a `Pair<Int,Long>` for this, but I think this looks cleaner, and is effectively the same thing for the purposes we have in mind.

``````// In Day13

data class IndexedBus(val index: Int, val bus: Long)
``````

We’re using Long here because it helps with the types when we solve the puzzle later. Since the numbers we will be generating are potentially very large, we’ll shift from `Int` to `Long`.

Now we can parse input for part 2:

``````// In Day13

private val indexedBusses: List<IndexedBus> = input
.last()
.split(",")
.mapIndexedNotNull { index, s -> if (s == "x") null else IndexedBus(index, s.toLong()) }
``````

Take the last line of input, split it on comma, and for each element that is not “x”, convert both its `index` and its id (converted to Long) to an `IndexedBus`.

Usually when I’m done solving these problems I go look and see what other people have done. Sometimes I’ll find some function I forgot about that can simplify my solution. For math-heavy problems like this one though, the answers can be somewhat confusing. I’m not the strongest mathematician, that’s for certain. A lot of people ended up using the Chinese Remainder Theorem to solve these puzzles.

It’s an alternative approach that you might find interesting if you are more into math than I am. It is probably more efficient than what we’ll cover here, but for the input size, I wouldn’t optimize just for that.

Now that we have that done, let’s talk about how we’ll solve this. The first thing to notice is that each of our bus numbers is prime. Let’s come up with an even smaller example than was given with the puzzle: `3,5,13`

For bus numbers `3, 5, 13`, we’re being told to find some `time` where:

``````time+0 % 3  == 0
time+1 % 5  == 0
time+2 % 13 == 0
``````

Let’s assume that we only have to solve the first problem: `time % 3 == 0`. Since we’re just focusing on one factor, we can set that answer to 3. Now we’ll expand our horizons a bit and consider the next bus, 5. We already know that when looking for `time+1 % 5 == 0`, we can skip any `time` that is not a multiple of 3. Expanding on that, let’s try multiples of `time` (3) until we get one that works: 6? Nope. 9? Yes! Because `(9+1) % 5 == 0`! What does that mean? It means that we now know how much time must pass for both bus 3 and bus 5 to show up one minute apart - 9 minutes.

So what now? Well, what should we search, given what we need to calculate `time+2 % 13 == 0`, given what we know about the first two numbers? We know we can skip some numbers because otherwise the other two equations won’t work out. So, starting at `time` 9, we can skip over any times that our previous times multiply to - `15`.

We can start examining possibilities at `time` 9, skipping by `15` each time.

So for the bus 13, indexed at place 2, and time starting with 9, does that work? No (because (9+2) % 13 != 0). So we skip time ahead by `15` and `time` is now `24`. Does that work? YES!

Because:

``````24+0 %  3 == 0
24+1 %  5 == 0
24+2 % 13 == 0
``````

(Note that if I had picked `11` instead of `13` for the last bus, we could have stopped at time 9).

Let’s implement that!

``````// In Day13:

fun solvePart2(): Long {
var stepSize = indexedBusses.first().bus
var time = 0L
indexedBusses.drop(1).forEach { (offset, bus) ->
while ((time + offset) % bus != 0L) {
time += stepSize
}
stepSize *= bus // New Ratio!
}
return time
}
``````

We start things off by setting our `stepSize` to the number of the first bus, and our `time` to 0. Then we start looping through all of our `IndexedBus` classes, taking care not to re-examine the first one! We use Kotlin’s ability to destructure data classes by breaking an `IndexedBus` into its components - `offset` (its index) and `bus`.

Then, we loop through time, increasing by our `stepSize` each time until we find a `time` that matches the equation: `(time + offset) % bus == 0`. Once we have that, we have a new `time` where we can start finding the next bus from. We have to remember, however, to adjust our `stepSize` at the end to include the `bus` we just found a time for.

Running this solves part 2!

See you tomorrow!

#### 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 13
4. Advent of Code - Come join in and do these challenges yourself!