Advent of Code 2020 - Day 13, in Kotlin - Shuttle Search • Todd Ginsberg

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!

⭐ Day 13, Part 1

⭐ Day 13, Part 2

Further Reading