Advent of Code 2024 - Day 17, in Kotlin - Chronospatial Computer • Todd Ginsberg

I rather liked the first part of today’s puzzle. Writing an interpreter is kind of fun! I am not, however, a huge fan of the “disassemble the program and figure out what it is doing” puzzles. And that’s fine, there are plenty of people who like them and plenty of puzzles I do like instead. I do appreciate the amount of effort that went into designing this puzzle though.

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

Puzzle Input

We will take today’s input in as a List<String> and parse it into a Computer, which we will define in a moment.

class Day17(input: List<String>) {

    private val computer: Computer = Computer.of(input)

}

Our Computer will be a data class. Originally I had it as a regular class, but since we’ll need to create copies of the Computer in part 2, we can get that for free by making this a data class. It will house our three registers, the program we’re executing as a List<Int>, a private instructionPointer, and a private mutable list to store the output

// In Day17

    private data class Computer(
        var registerA: Long,
        var registerB: Long,
        var registerC: Long,
        val program: List<Int>
    ) {
        private var instructionPointer: Int = 0
        private val output = mutableListOf<Long>()

        companion object {
            fun of(input: List<String>): Computer =
                Computer(
                    input[0].substringAfterLast(" ").toLong(),
                    input[1].substringAfterLast(" ").toLong(),
                    input[2].substringAfterLast(" ").toLong(),
                    input[4].substringAfterLast(" ").split(",").map { it.toInt() }
                )
        }
    }

For parsing, we’ll go the usual route of adding an of function to the companion object. We’ll also use substringAfterLast to do most of the work.

We will add more to our Computer in Part 1.

⭐ Day 17, Part 1

The puzzle text can be found here.

Let’s add some functions to our computer. First up, an extension on Int to convert it to a combo operand. We’ll use a when expression to do this.

// In In Day17.Computer

private fun Int.toComboOperand(): Long =
    when (this) {
        in 0..3 -> toLong()
        4 -> registerA
        5 -> registerB
        6 -> registerC
        else -> throw IllegalArgumentException("Invalid operand: $this")
    }

Next, we’ll write a function to execute the instruction at the instructionPointer and return whether it was successful or not. Given the length, I won’t go through executeInstruction in detail, but I will cover some of the highlights:

Be really careful when implementing these, I got operand and comboOperand mixed up more than once, yielding wrong answers!
Rather than implement opcodes 0, 6, and 7 as written, you can do a bitwise right shift by the comboOperand which has the same effect.

// In Day17.Computer

fun executeInstruction(): Boolean {
    if (instructionPointer > program.lastIndex) return false
    else {
        val operand = program[instructionPointer + 1]
        val comboOperand = operand.toComboOperand()
        when (program[instructionPointer]) {
            0 -> {
                registerA = registerA shr comboOperand.toInt()
                instructionPointer += 2
            }

            1 -> {
                registerB = registerB xor operand.toLong()
                instructionPointer += 2
            }

            2 -> {
                registerB = comboOperand % 8
                instructionPointer += 2
            }

            3 -> {
                instructionPointer = if (registerA == 0L) instructionPointer + 2
                else operand
            }

            4 -> {
                registerB = registerB xor registerC
                instructionPointer += 2
            }

            5 -> {
                output.add(comboOperand % 8)
                instructionPointer += 2
            }

            6 -> {
                registerB = registerA shr comboOperand.toInt()
                instructionPointer += 2
            }

            7 -> {
                registerC = registerA shr comboOperand.toInt()
                instructionPointer += 2
            }
        }
        return true
    }
}

Now that we can execute a single instruction let’s write a function to run a program and return the output.

// In Day17.Computer

fun runToEnd(): List<Long> {
    var executed = true
    while (executed) {
        executed = executeInstruction()
    }
    return output
}

I attempted to implement runToEnd with a sequence but felt it was a bit messy and just ended up with this while loop.

Running the program and joining the output to a comma-separated String solves part 1.

// In Day17

fun solvePart1(): String =
    computer.runToEnd().joinToString(",")

Star earned! Onward!

⭐ Day 17, Part 2

The puzzle text can be found here.

For Part 2, I got help from Reddit, specifically this comment by /u/ThunderChaser . I’m not following /u/ThunderChaser around the internet or anything, it’s a complete coincidence that the same person has unwittingly helped me twice this year (see advent 2024, Day 13 )!

Basically, the theory is this: The least significant 3 bits of A eventually affect what ends up in the output. So if we work our way through the program instructions backwards, we should be able to figure out what value of A generates the last value of the program instructions to the output. It will be in the range of 0 to 7, so there aren’t that many possibilities. If we take all of those successful candidates, shift them left by 3, and repeat the process, we should be able to generate the last two digits of the program instructions. Keep doing that and we eventually end up with some value in A that reproduces our program in the output.

I was able to get it down to a single function, which I think is rather nice.

// In Day17

fun solvePart2(): Long =
    computer.program
        .reversed()
        .map { it.toLong() }
        .fold(listOf(0L)) { candidates, instruction ->
            candidates.flatMap { candidate ->
                val shifted = candidate shl 3
                (shifted..shifted + 8).mapNotNull { attempt ->
                    computer.copy().run {
                        registerA = attempt
                        attempt.takeIf { runToEnd().first() == instruction }
                    }
                }
            }
        }.first()

Since we’re going to go backwards through the program, we want to get the program.reversed(). And since our program is made of Ints, we convert them to Long. Next we set up a fold, seeding it with a list(0), zero being the first candidate we want to try our process on, and instruction being the next last program instruction that we are folding over. For each candidate, we shift it left by 3, and then range over that number to that number plus 8. We copy the computer, set A the number we want to attempt and run it. If the computer generates output that matches the instruction, we’ve found a valid attempt, and we take it.

We continue the process until all we have run through all the instructions. The value we generate is the value of A that will successfully reproduce our program instructions.

Star earned (with help)! See you tomorrow!

Puzzle Input

⭐ Day 17, Part 1

⭐ Day 17, Part 2

Further Reading