Advent of Code 2020 - Day 10, in Kotlin - Adapter Array • Todd Ginsberg

We’re ten days in to Advent of Code today, 2/5ths of our way through! We’ll learn the value of not letting the text of the puzzle push us towards a solution.

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

Problem Input

We will import our data as a List<Int> and make some small changes to make both parts 1 and 2 easier to manage.


class Day10(input: List<Int>) {

    private val adapters: List<Int> = input.plus(0).plus(input.maxOrNull()!! + 3).sorted()

}

Because the puzzle input does not account for the plug (0) and the end adapter (max + 3), we will add those manually. We will also sort the adapters into ascending order, because both parts will depend on that as well.

⭐ Day 10, Part 1

The puzzle text can be found here.

I love part 1 because it has a very long worked example that is hiding a straight-forward solution in plain sight. Essentially that big long description tells us to sort the adapters in order (done!) and figure out the number of gaps of size 1 and 3.

Because there are a lot of operations here, we’ll turn our List<Int> into a Sequence<Int> via .asSequence() so it does not create so many temporary lists between steps.


fun solvePart1(): Int =
    adapters
        .asSequence()
        .zipWithNext()
        .map { it.second - it.first }
        .groupingBy { it }
        .eachCount()
        .run {
            getOrDefault(1, 1) * getOrDefault(3, 1)
        }

First, we need to pair up each consecutive set of adapters in our list, so we’ll use zipWithNext for that. Once we have that, we can map each of those pairs into a number - the gap between the adapters. We’ll use groupingBy and eachCount again to end up with a Map<Int,Int> where the key is the gap, and the value is how many we ran into. Finally, we get the number of times a gap of 1 showed up and multiply it by the number of times a gap of 3 showed up. We’ll use getOrDefault here, taking care to default to 1 (the multiplicative identity) in case for some reason we don’t have any gaps of 1 or 3.

Star earned, onward!

⭐ Day 10, Part 2

The puzzle text can be found here.

I know it says a brute force solution is not practical but I’ve got a ton of AWS credits burning a hole in my pocket so let’s give it a try.

I’m only kidding. There is a fairly quick way of solving this if we stop and think about the problem first.

Let’s consider the following smaller example using 1, 4, 5, 6, 7. We’ll add the ends on to make that 0, 1, 4, 5, 6, 7, 10.

The first part of the chain will always be this, because there are no alternatives:

(0) -> 1, 4, 5 -> ???

This shows that there is one single way to get to any of 0, 1, 4 or 5. But here’s where it gets fun. From 5 we can go to 6 or 7. And that’s where the problem breaks down and gets complicated for larger sets of adapters.

Let’s pretend we pick 6 as our next step. There is still one way to get there:

(0) -> 1, 4, 5, 6 -> ???

But if we continue to 7, there are two ways ways! Directly from 5 to 7 and from 5 to 6 to 7.

(0) -> 1, 4, 5, 7 -> ???
(0) -> 1, 4, 5, 6, 7 -> ???

What this shows us is that for any given adapter, we can figure out how many ways there are to get there by knowing how many ways to get to the sum of all adapters in range of it (within 3)!

So if we work through the list of adapters in order, the number of ways to get to Adapter n is the sum of the adapters that come before it in the list, if they are in range.

And knowing all this, we can now solve part 2:

fun solvePart2(): Long {
    val pathsByAdapter: MutableMap<Int,Long> = mutableMapOf(0 to 1L)

    adapters.drop(1).forEach { adapter ->
        pathsByAdapter[adapter] = (1 .. 3).map { lookBack -> 
            pathsByAdapter.getOrDefault(adapter - lookBack, 0) 
        }.sum()
    }

    return pathsByAdapter.getValue(adapters.last())
}

I had originally based this same solution on the use of a LongArray, but @Nir from the #advent-of-code room on the Kotlin language slack showed me a much simpler way to execute the same algorithm using a map. It reduced the complexity of the “lookback” part of the code I had.

Thanks @Nir!

First we will declare a mutable map to store how many possible paths each adapter can have, taking care to set the first adapter to have one single path, or none of this will work!

Next, we drop the adapter we’ve already manually calculated and look at every other adapter we know about. For each one of those, we want to get the number of possible paths any other adapter that is in range has. We do this by creating our own IntRange and adding the path values for those adapters to our own path count. We need to take care here to account for the fact that one of the 3 adapters in range of us might not actually exist, so we assume it has zero paths.

At this point we have a map that can tell you how many paths there are to any one specific adapter. Returning the path count for the last adapter in our list gives us our answer.

Star earned!

I hope you had fun with that. I spent a good amount of time drawing graphs before I realized this was a set of running sums.

See you tomorrow!

⭐ Day 10, Part 1

⭐ Day 10, Part 2

Further Reading