# Advent of Code 2019 - Day 22, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2019, Day 22: 'Slam Shuffle'

Posted on

Who wants to spend the next three millennia waiting to brute force an answer to a math problem?! Put your hands down, I know nobody wants that, despite how awesome “brute force” tends to sound.

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

Problem Input

Unlike most days, we’ll parse our input as-needed in our solution. There is no special preparation needed.

#### ⭐ Day 22, Part 1

The puzzle text can be found here.

For Part 1, we’ll implement our deck of cards as a `List<Int>`. I chose this instead of `IntArray` because most of the operations I was doing on `IntArray` will return a `List<Int>` and I didn’t want to keep converting back and forth.

Let’s implement a function for each instruction we’re expecting. Each will be an extension on `List<Int>` and return a `List<Int>`.

``````private fun List<Int>.cut(n: Int): List<Int> =
when {
n > 0 -> this.drop(n) + this.take(n)
n < 0 -> this.takeLast(n.absoluteValue) + this.dropLast(n.absoluteValue)
else -> this
}
``````

This uses the handy kotlin build-ins: `drop`, `take`, `takeLast`, `dropLast`, and `absoluteValue`. Next, we’ll implement a function to re-deal the cards:

``````private fun List<Int>.deal(increment: Int): List<Int> {
val newDeck = this.toMutableList()
var place = 0
this.forEach { card ->
newDeck[place] = card
place += increment
place %= this.size
}
return newDeck
}
``````

This function does the math to figure out what cards go in the new slot in the new deck. Finally, we need to write a simple function to create our deck, which is just a list of `Int`:

``````private fun createDeck(length: Int = 10_007): List<Int> =
List(length) { it }
``````

Now let’s write a function to follow our input instructions. This will loop through them all and call our new functions in order to manipulate the deck:

``````private fun followInstructions(): List<Int> =
input.fold(createDeck()) { deck, instruction ->
when {
"cut" in instruction -> deck.cut(instruction.getInt())
"increment" in instruction -> deck.deal(instruction.getInt())
"stack" in instruction -> deck.reversed()
else -> throw IllegalArgumentException("Invalid instruction: \$instruction")
}
}
``````

As you can see, for “stack”, we simply reverse the deck, we don’t need another function for that. We do need a function to pick the variable number out from each instruction. We’ll define this as an extension function on `String`:

``````private fun String.getInt(): Int =
this.split(" ").last().toInt()
``````

Calling this function and finding where the 2019 card is solves part 1!

``````fun solvePart1(): Int =
followInstructions().indexOf(2019)
``````

Star earned!

#### ⭐ Day 22, Part 2

The puzzle text can be found here.

OK, here’s where things get crazy. The deck size (119,315,717,514,047) is larger than we can declare a List or Array for in Kotlin (or Java). And the number of shuffles (1,017,41,582,076,661), even at only 1 millisecond each would still take 3,226 years to complete. That must mean there’s a better way to do this.

I’ve admitted a few times during Advent of Code 2019 that I’m not so into the math heavy problems, so I had a lot of help with this.

Let’s declare constants for the number of cards in the deck, the number of shuffles we’ll perform, and 2 (as a `BigInteger`, because we’ll use it a few times). What’s interesting is that `BigInteger` already defines `TWO`, but it is `private`, so we can’t use it (or declare it as an extension).

``````companion object {
val NUMBER_OF_CARDS = 119315717514047.toBigInteger()
val SHUFFLES = 101741582076661.toBigInteger()
val TWO = 2.toBigInteger()
}
``````

And much like Part 1, we’ll need to parse out the number in each instruction. Since we’ll be dealing with `BigInteger` exclusively in this solution, we don’t want to use our existing `Int` version and keep converting because it looks cleaner to deal with one consistent type.

``````private fun String.getBigInteger(): BigInteger =
this.split(" ").last().toBigInteger()
``````

And now for the crazy. Try as I might to understand the Properties of Modular Arithmetic and how they apply to this problem, I had a lot of trouble figuring out the right approach to solve this puzzle. I ended up converting Simon Baars' excellent Java-based solution to Kotlin.

``````private fun modularArithmeticVersion(find: BigInteger): BigInteger {
val memory = arrayOf(ONE, ZERO)
input.reversed().forEach { instruction ->
when {
"cut" in instruction ->
memory[1] += instruction.getBigInteger()
"increment" in instruction ->
instruction.getBigInteger().modPow(NUMBER_OF_CARDS - TWO, NUMBER_OF_CARDS).also {
memory[0] *= it
memory[1] *= it
}
"stack" in instruction -> {
memory[0] = memory[0].negate()
memory[1] = (memory[1].inc()).negate()
}
}
memory[0] %= NUMBER_OF_CARDS
memory[1] %= NUMBER_OF_CARDS
}
val power = memory[0].modPow(SHUFFLES, NUMBER_OF_CARDS)
return ((power * find) +
((memory[1] * (power + NUMBER_OF_CARDS.dec())) *
((memory[0].dec()).modPow(NUMBER_OF_CARDS - TWO, NUMBER_OF_CARDS))))
.mod(NUMBER_OF_CARDS)
}
``````

While I do think the Java version I based this on is exceptionally well written, to me the Kotlin is just clearer. Why? Kotlin defines operators that call through to `BigInteger`’s equivalent functions, making these operations look more natural. Kotlin also has assignment operators so things like “modulus and assign” (`%=`) look cleaner. The code more or less does the same thing, and probably compiles to roughly equivalent bytecode.

And to get our solution:

``````fun solvePart2(): BigInteger =
modularArithmeticVersion(2020.toBigInteger())
``````

Star “earned”!

While I did have fun converting this code from Java into Kotlin, I can’t say I understood much of the modular arithmetic. I’ll have to put “get better at math” on my 2020 research list.

1. Index of All Solutions - All posts and solutions for 2019, in Kotlin.
2. My Github repo - Solutions and tests for each day.
3. Solution - Full code for day 22
4. Advent of Code - Come join in and do these challenges yourself!