Advent of Code 2020 - Day 23, in Kotlin - Crab Cups • Todd Ginsberg

Today we’ll write a focused linked list which we will index with a list in order to improve performance. There are some nice features in Kotlin that makes this effort a bit easier, and the new Kotlin function runningFold makes an appearance.

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

Problem Input

Today all of our inputs are parsed by a class we used to represent the circle of cups, which we will do in Part 1. We will simply hold our input as a single String as a property on our Day23 class.

class Day23(private val input: String)

We will also define one extension function that could be generally useful - a function on Char to turn it into an Int.

// In Extensions.kt

fun Char.asInt(): Int =
    this.toString().toInt()

This looks just like the Char.asLong() we defined the other day, and only exists because Char.toInt() converts the Char to its underlying Int representation, rather than its digit as an Int.

⭐ Day 23, Part 1

The puzzle text can be found here.

Given that we have a circle of cups, and that we have to move small groups of them around and still maintain a circle, it makes sense to model today’s data structure as a linked list. A linked list is a data structure where there is a notion of a node that holds a value. Each node also stores a reference to the next node in the list. There is another variant of the linked list called a “doubly linked list” in which node also stores its previous node, so it can be traversed backwards. There are several other variants where multiple forward references exist to optimize searching (called “skip lists”) but we won’t go that far today. Instead, because at the end we will link the final node back up with the first node, we are creating a “circularly linked list”.

Because we only need to search forwards through our circle (our linked list), we will only implement a next reference.

// In Day23

private class Cup(val value: Int) {
    lateinit var next: Cup
}

Why are we defining the next Cup as a lateinit var? Two reasons. First it has to be a var because we are going to be relinking Cups and changing the next reference. Second, we want to be able to construct a Cup before linking it to the next Cup (which may not exist yet when we create it), and lateinit permits us to create a Cup with a non-nullable next reference without having to specify that reference at construction time. The deal we’ve made with the compiler by using lateinit is that we promise to set that value before getting it (otherwise, there will be an error).

To store the Cup objects as a circular linked list, we will define another object called Cups (original, I know). The Cups object will be responsible for creating instances of Cup and playing the game.

// In Day23

private class Cups(order: String) {
    val cups: List<Cup> = List(order.length+1) { Cup(it) }
    var currentCup: Cup = cups[order.first().asInt()]

    init {
        val cupIdsInOrder = order.map { it.asInt() }
        cupIdsInOrder
            .map { cups[it] }
            .fold(cups[order.last().asInt()]) { previous, cup ->
                cup.also { previous.next = cup }
            }
        cups[cupIdsInOrder.last()].next = cups[cupIdsInOrder.first()]
    }

The first thing we do is create our List<Cup>. Since we know all of the ids of the cups we want to generate, we can do that with the handy List constructor that lets us specify the size of the List and a lambda that is executed for each index in the list. In our case, we will be storing cups in a List according to their id. This will allow us to easily say “find me cup 1” or “find me cup 9” without having to search the whole linked list.

Note here that we are defining one more cup than we really need. Cup 0 will be defined but unused, and not linked to other cups. This is so the indexing can be 1-based and we won’t have to remember to keep subtracting 1.

Next, we set the currentCup to the first cup in the list. This will become handy later when we play the game, and it is a var because it changes over time.

Finally, the init block is used to link the cups together. We know the order from the variable handed in, so we convert each Char in the order string in to an Int to get the cup ids in the order we want them linked. We iterate through these ids, converting them to Cup instances by looking them up in the cups list by their id. Then we fold over the resulting Cup objects, linking each current cup to the previous cup. I like fold for this because it lets us build the chain as we go.

The last step of linking our cups together is to link the next reference of last cup in the list to the first cup in the list, by its id (NOT the first cup in the list!). Now we have a circular linked list of Cup objects, each of which contains a value and points to the next Cup in the circle. Because we’re also storing them in a List, we can access them by id without having to scan the linked list.

Let’s play a round of the game:

// In Day23.Cups

private fun playRound() {
    val next3: List<Cup> = currentCup.nextAsList(3)
    val destination = calculateDestination(next3.map { it.value }.toSet())
    moveCups(next3, destination)
    currentCup = currentCup.next
}

We’ll have to define some more functions to play the game in a minute, but this gives us a good framework to work off of. To play a round of the game, we need to get the next three cups clockwise from the current cup. So we’ll write a function called nextAsList() on Cup to do this. It will return a List<Cup> for us. Next, we’ll write a function called calculateDestination which will calculate the destination based on the currentCup and the values that our next3 cups have. Once we have that information we can call moveCups with our next3 cups and the destination and expect that those 3 cups are unlinked from their current location and re-linked to follow the destination cup. Once that is done, we can advance the currentCup reference to the next cup in the circle.

// In Day23.Cup

fun nextAsList(n: Int): List<Cup> =
    (1 .. n).runningFold(this) { cur, _ -> cur.next }.drop(1)

Here we get to see a new function in Kotlin 1.4 called runningFold. A runningFold does the same work as a fold but keeps all of the intermediate results. This lets us traverse the chain of next calls, and get back a List<Cup> rather than a single Cup at the end, like we would with a normal fold! We have to take care to drop the starting cup, as we want the next few cups, exclusive of the current cup.

Calculating the destination is up next:

// In Day23.Cups

private fun calculateDestination(exempt: Set<Int>): Cup {
    var dest = currentCup.value - 1
    while(dest in exempt || dest == 0) {
        dest = if(dest == 0) cups.size-1 else dest -1
    }
    return cups[dest]
}

Essentially, we keep generating candidate cups until one of them works. If we hit 0, we know we need to loop back around to the highest value cups. Since the cups are numbered and there are no gaps, we can use our cups size (-1 because we have that 0 value) to figure out what that value is. Otherwise we keep decrementing until we find a cup that we are not exempt from picking. We return that Cup to the caller.

Moving cups is a bit tricky:

// In Day23.Cups

private fun moveCups(cupsToInsert: List<Cup>, destination: Cup) {
    val prevDest = destination.next
    currentCup.next = cupsToInsert.last().next
    destination.next = cupsToInsert.first()
    cupsToInsert.last().next = prevDest
}

This function will move the cupsToInsert to right after the destination cup. Because we’ll be moving next references around, we need to save off the original destination.next so we’ll have it at the end of the re-linking. We take the currentCup and make its next reference point to the cup immediately after the end of our cupsToInsert. This effectively means that the cups in cupsToInsert are not in our circle of cups any longer. To re-link them we point the next reference of the destination cup to the first cup in our cupsToInsert. To complete the re-linking, we link the next cup after our cupsToInsert to the original value we saved off.

Let’s add a way to play multiple rounds of the game to our Cups class:

// In Day23.Cups

fun playRounds(numRounds: Int): Cup {
    repeat(numRounds) {
        playRound()
    }
    return cups[1]
}

This plays numRounds of the cup game and returns Cup #1 to the caller (because ultimately that is the only cup they care about).

We’re close to being able to solve part 1, we just have to find a way to turn our linked list into a String. To do that, we’ll override toString() on Cup.

// In Day23.Cup

override fun toString(): String = buildString {
    var current = this@Cup.next
    while(current != this@Cup) {
        append(current.value.toString())
        current = current.next
    }
}

We use the new buildString function in Kotlin to loop through our cups, appending the current cup’s value (as a String) to the builder. Every time we do so, we advance the current cup reference to the next cup in the list. We stop when we’ve run back into the cup we called this function on.

And now we can solve part 1!

// In Day23

fun solvePart1(roundsToPlay: Int): String =
    Cups(input)
        .playRounds(roundsToPlay)
        .toString()

Star earned! Onward!

⭐ Day 23, Part 2

The puzzle text can be found here.

To play part 2, we need to provide a way for our Cups object to generate more cups than we give it.

We’ll have to make a few slight modifications:

private class Cups(order: String, numberOfCups: Int = order.length) {
    val cups: List<Cup> = List(numberOfCups+1) { Cup(it) }
    var currentCup: Cup = cups[order.first().asInt()]

    init {
        val cupIdsInOrder = order.map { it.asInt() } + (order.length + 1 .. numberOfCups)
        cupIdsInOrder
            .map { cups[it] }
            .fold(cups[order.last().asInt()]) { previous, cup ->
                cup.also { previous.next = cup }
            }
        cups[cupIdsInOrder.last()].next = cups[cupIdsInOrder.first()]
    }

    // Rest is the same...

The first change is to take in a new parameter called numberOfCups. For Part 1, this will default to the length of the order property (don’t create more cups), but in Part 2, we’ll tell it how many cups we want.

The next change is to the cupsInOrder value in the init block. We need to add all of the extra cups we are supposed to generate. Thankfully in Kotlin this is easy with ranges. We define a range for the extra cups and just add it to the ids we generated from our order parameter. The rest of this function, and the rest of the code we’ve done, is the same!

Now we can solve part 2.

fun solvePart2(roundsToPlay: Int): Long =
    Cups(input, 1_000_000)
        .playRounds(roundsToPlay)
        .nextAsList(2)
        .map { it.value.toLong() }
        .product()

We can pass 1_000_000 to the Cups constructor, telling it we want a million total cups (maybe we store them all in our Shiny Gold Bag from a few days ago? ). One nice feature about Kotlin that I use regularly is the ability to split up large numbers with an underscore. I find 1_000_000 easier to read than 1000000.

Next, we play as many rounds as we’re told at which point we are returned Cup #1. Take the next two Cups, map their values from Int to Long, and use our product() extension function from a few days ago to get the answer to part 2!

Star earned! See you tomorrow!

⭐ Day 23, Part 1

⭐ Day 23, Part 2

Further Reading