Advent of Code 2019 - Day 22, in Kotlin • Todd Ginsberg

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>.

We’ll start with cutting:

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.

⭐ Day 22, Part 1

⭐ Day 22, Part 2

Further Reading