# Advent of Code 2020 - Day 22, in Kotlin - Crab Combat

Kotlin solutions to parts 1 and 2 of Advent of Code 2020, Day 22: 'Crab Combat'

Posted on

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 `Iterable`s 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) ->
}
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(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

1. Keeping track of which decks have existed already and
2. 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!