Advent of Code 2020 - Day 22, in Kotlin - Crab Combat • Todd Ginsberg

Today we’re playing cards against a Crab With No Name, who I suppose is friendly if it hasn’t bitten us (yet). We’ll define a sequence and use recursion - all sorts of fun things!

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

Problem Input

We will read our input in as a List<String> today and parse it with a couple of one-liners. Our destination format is going to be a MutableList<Int>, rather than a List<Int> because we’ll be adding and removing cards from the deck frequently.

First, we’ll define a typealias so that we can refer to MutableList<Int> as Deck, which looks cleaner.

typealias Deck = MutableList<Int>

class Day22(input: List<String>) {

    private val deck1: Deck = input.drop(1).takeWhile { it.isNotBlank() }.map { it.toInt() }.toMutableList()
    private val deck2: Deck = input.dropWhile { it.isNotBlank() }.drop(2).map { it.toInt() }.toMutableList()

}

Next, we parse out the two decks from the input: Dropping the header for Player 1 and converting each following row to an Int until we hit a blank row. For player 2, we skip all of the Player 1 rows and do the same Int conversion.

⭐ Day 22, Part 1

The puzzle text can be found here.

When I hear a requirement that involves taking from two Iterables, I think about using zip, which will join two Iterables into a Pair for each pair of elements. However, since we will be both removing the elements we want to pair up and adding elements back into the Deck, zip isn’t going to cut it.

So let’s write our own version that works as a sequence so we can pull from is as long as we want, and manages to remove elements from the Deck before pairing them up.

private fun Deck.pairedWith(other: Deck): Sequence<Pair<Int, Int>> = sequence {
    while (this@pairedWith.isNotEmpty() && other.isNotEmpty()) {
        yield(Pair(this@pairedWith.removeFirst(), other.removeFirst()))
    }
}

Note that because this is a self-contained example, this is perfectly safe. However, if this code were shared we would need to do some locking because our Deck could empty out immediately after we check that it isNotEmpty and before we removeFirst. But since this is a private function and we control all access to the Decks, we’re safe.

Next, let’s write an extension function on our Deck to get its score.

private fun Deck.score(): Int =
    this.foldIndexed(0) { index, acc, current -> acc + (current * (size - index)) }

We’ll use a fold starting a 0. A fold allows us to call a lambda for each element in our Deck, and carry along the previous answer from call to call. The initial 0 is the starting carried value. In this fold variant called foldIndexed, we are also given the index of the element we are looking at. We can then use those three things to calculate the score.

Now, we can finally write a function to play our game!

private fun playGame(deckA: Deck, deckB: Deck): Boolean {
    deckA.pairedWith(deckB).forEach { (a, b) ->
        if (a > b) deckA.addAll(listOf(a, b)) else deckB.addAll(listOf(b, a))
    }
    return deckA.isNotEmpty()
}

The playGame function uses our new sequence via pairedWith to pair up the top card from deckA and deckB, while also removing them. Because this function gives us back a Pair<Int,Int>, and Pair supports destructuring, we can destructure the Pair into two Ints: a and b, just to make things a bit easier to read.

If a is greater than b, we add a,b to deckA, otherwise we add b,a to deckB.

Once one of our decks is out of cards, the sequence will stop producing values and we can see who won! Because there are only two states - either deckA wins or it doesn’t (deckB wins), we can use a Boolean for the return type.

Next we’ll write a function to play our game, interpret the results, and return the winning deck (which should be in the proper state because we’re using a MutableList), to the caller.

private fun playUntilWinner(): Deck =
    if (playGame(deck1, deck2)) deck1 else deck2

And with that, we can solve Part 1 by finding the winning deck and getting its score!

fun solvePart1(): Int =
    playUntilWinner().score()

Star earned, onward!

⭐ Day 22, Part 2

The puzzle text can be found here.

We’re going to have to make some changes to our playGame function to handle the recursive aspect of the game. Since we want to use the same playGame function for both Part 1 and Part 2, we’ll pass allowRecursive in as a Boolean parameter.

private fun playGame(deckA: Deck, deckB: Deck, allowRecursive: Boolean): Boolean {
    val history = mutableSetOf(Objects.hash(deckA, deckB))
    deckA.pairedWith(deckB).forEach { (a, b) ->
        val winner = when {
            allowRecursive && deckA.size >= a && deckB.size >= b ->
                playGame(
                    deckA.take(a).toMutableList(),
                    deckB.take(b).toMutableList(),
                    true
                )
            else -> a > b
        }
        if (winner) deckA.addAll(listOf(a, b)) else deckB.addAll(listOf(b, a))

        if(allowRecursive) {
            Objects.hash(deckA, deckB).also {
                if (it in history) return true else history += it
            }
        }
    }
    return deckA.isNotEmpty()
}

Let’s go over the changes.

There are two major additions to the playGame function

Keeping track of which decks have existed already and
The ability to play recursive games.

Let’s handle managing our deck history first. To do that, we’re going to create a MutableSet<Int> called history. We populate it with the state of both decks for every turn, and we do that by hashing them rather than storing copies of the deck over and over again. I’ve chosen to use Objects.hash() from Java in order to do this work. It’s a nice built-in function that we can call from Kotlin. If you’re not compiling for the JVM, you’ll probably have to find an alternative hashing function.

We start off our playGame function by declaring our history set and populating it with the hash of the two decks handed in. Strictly speaking, we are doing work we don’t need to here if we’re playing a game that doesn’t permit recursion. But it is one single call, and I can live with that.

We also need to manage our history as the game progresses. According to the rules we need to check the deck states before we deal cards. Because I like our pairedWith setup, I don’t want to alter the program flow here. So we’ll check the next state immediately before we loop around and play another round. We’ll only do that part if we allowRecursoin to save a bit of time and memory. If we’ve detected a loop, we end early by returning true - indicating that Player 1 has won this round.

The second part of the changes - allowing recursion, involve a bit more code. Because the winner of a specific hand isn’t always the one with the highest card, we’ll declare a winner flag and use a when clause to invoke our round playing logic. If recursion is allowed and both players have enough cards, we are going to play a recursive hand. This involves copying a specific amount of cards out of each deck and calling playGame with them. After playing a hand (either directly or through recursion), our winner flag holds a value we can test against, and add the two cards (still a and b) to the winner’s deck.

Because we have this new allowRecursive flag, we’ll also need to make a change to our playUntilWinner function to pass that along. So we don’t have to change the calling code from solvePart1, we’ll default allowRecursive to false, and pass that value along to playGame.

private fun playUntilWinner(allowRecursive: Boolean = false): Deck =
    if (playGame(deck1, deck2, allowRecursive)) deck1 else deck2

And finally, if we pass true (allow recursion) to our playUntilWinner function and call score on the winning deck, we’ve solved part 2!

fun solvePart2(): Int =
    playUntilWinner(true).score()

Star earned! See you tomorrow!

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading