Chronospatial Computer

Part 1

Instead of creating a program, we’ll be creating the computer it’s running on. Or at least, an emulator for the computer it’s running on. Believe it or not, this task is nowhere near as scary as it sounds.

First, let’s parse the input. Today, it’s in the form of two blocks separated by two newlines: the initial values of the computer’s registers, and the program itself. Once you split the input into those two blocks (which I can configure my solution framework to do for me), all we want are the numbers from each block; we can use a relatively simple one-liner to extract them.

import re

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_1(self) -> str:
        registers, program = (
            tuple(map(int, re.findall(r"\d+", block)))
            for block in self.input
        )
        ...

Now we have the register values and program values, both as tuples of ints. Once our emulator for the Historians’ computer is finished, it’ll need this information to run the program.

Let’s start work on our emulator, which will be in the form of a function. Because the computer will be outputting a number of successive values as it runs the program, a generator function that yields those output values seems like a good fit.

from collections.abc import Iterator

def run(registers: tuple[int, ...], program: tuple[int, ...]) -> Iterator[int]:
    a, b, c = registers
    ...  # TODO Write emulate-Historians'-computer code

Our emulation function will consist of one main loop, where the following things will happen:

1. An instruction pointer (which starts at 0) will read an “opcode” and an “operand”.
2. Based on the opcode, one of eight different instructions will be performed.
3. The instruction pointer will increase by 2, and this process will loop until the instruction pointer moves past the end of the program.

This is already enough to create a simple sketch of the function. We can use some slick slicing syntax to read the current opcode and operand, and we can use a match statement to do different things based on the opcode we find (rather than a large, unwieldy if...elif chain).

And while we’re at it: some instructions will need a “combo operand” based on the value of operand, so let’s also figure out the value of the current combo operand. Because we’re only considering integer values of operand from 0 to 6, a tiny lookup table is all we need here.

from collections.abc import Iterator

def run(registers: tuple[int, ...], program: tuple[int, ...]) -> Iterator[int]:
    a, b, c = registers

    pointer = 0
    while pointer < len(program):
        opcode, operand = program[pointer : pointer + 2]
        combo = [0, 1, 2, 3, a, b, c][operand]

        match opcode:
            case 0:  # adv (A DiVide)
                ...
            case 1:  # bxl (B Xor Literal)
                ...
            case 2:  # bst (B STore)
                ...
            case 3:  # jnz (Jump if Not Zero)
                ...
            case 4:  # bxc (B Xor C)
                ...
            case 5:  # out (OUTput)
                ...
            case 6:  # bdv (B DiVide)
                ...
            case 7:  # cdv (C DiVide)
                ...
            case _:
                assert False, f"unexpected opcode {opcode}"

        pointer += 2

All that’s left is to implement the instructions for each opcode. And thankfully, the puzzle prompt tells us the exact behavior of each instruction, so the implementations are very straightforward — though it may help to familiarize yourself with bitwise operations, and how to use the bitwise operators in Python.

0. adv: Integer-divide a by pow(2, combo), and store the result back to a.
   • I actually implement this slightly differently than described; integer-dividing by 2 (or a power of 2) is equivalent to a rightward bit shift, which we can do with the >> operator. So my implementation of adv is a >>= combo — that is, take a, bit-shift it by combo bits to the right, and store the result back to a.
1. bxl: Do a bitwise XOR with b and operand, and store the result back to b.
   • Python’s bitwise XOR operator is ^, so bxl can be implemented as b ^= operand.
2. bst: Calculate combo modulo 8 (which keeps only its lowest 3 bits), and store the result to b.
   • I also implement this slightly differently than described — not with the modulo operator %, but with the bitwise AND operator &. It may not be obvious why I did it that way, but a bitwise AND is often used to keep certain bits of a number and discard others — and here, we want to keep the lowest 3 bits of combo and discard all the other bits. So my implementation of bst is b = combo & 0b111, which does exactly that.
3. jnz: If a is nonzero, set the instruction pointer to operand (and don’t increase it by 2 afterward like normal); otherwise, do nothing.
   • I use if a to test whether a is nonzero, pointer = operand to set the instruction pointer, and continue to ensure the pointer += 2 part at the end of the loop is skipped. Super simple.
4. bxc: Do a bitwise XOR with b and c, and store the result back to b.
   • Similarly to bxl, bxc can be implemented as b ^= c.
5. out: Calculate combo modulo 8, and output the result.
   • Similarly to bst, I use a bitwise AND instead of a modulo to keep the lowest 3 bits. So my implementation of out is yield combo & 0b111 — keeping in mind that we want to yield each outputted number!
6. bdv: Do the same calculation as adv, except store the result to b.
   • My implementation of bdv is b = a >> combo — using the >> operator for the reasons I stated above.
7. cdv: Do the same calculation as adv, except store the result to c.
   • My implementation of cdv is c = a >> combo — using the >> operator for the reasons I stated above.

from collections.abc import Iterator

def run(registers: tuple[int, ...], program: tuple[int, ...]) -> Iterator[int]:
    a, b, c = registers

    pointer = 0
    while pointer < len(program):
        opcode, operand = program[pointer : pointer + 2]
        combo = [0, 1, 2, 3, a, b, c][operand]

        match opcode:
            case 0:  # adv (A DiVide)
                a >>= combo
            case 1:  # bxl (B Xor Literal)
                b ^= operand
            case 2:  # bst (B STore)
                b = combo & 0b111
            case 3:  # jnz (Jump if Not Zero)
                if a:
                    pointer = operand
                    continue
            case 4:  # bxc (B Xor C)
                b ^= c
            case 5:  # out (OUTput)
                yield combo & 0b111
            case 6:  # bdv (B DiVide)
                b = a >> combo
            case 7:  # cdv (C DiVide)
                c = a >> combo
            case _:
                assert False, f"unexpected opcode {opcode}"

        pointer += 2

And just like that, the emulation function is done! We can now call run(registers, program) to generate the outputs of our Historians’-computer program. Then we’ll want to convert the outputs to strings (which I do with the map function), and str.join them all together with commas.

import re

class Solution(StrSplitSolution):
    separator = "\n\n"

    def part_1(self) -> str:
        registers, program = (
            tuple(map(int, re.findall(r"\d+", block)))
            for block in self.input
        )
        return ",".join(map(str, run(registers, program)))

Not so scary, right?

Part 2

It seems the value of the A register is wrong, because the output was supposed to look like the program itself; in other words, the program is supposed to be a quine!¹ Now this sounds pretty scary.

It wouldn’t be practical to brute-force all possible values of the A register, as it would take a long time — and possibly never finish, if the provided program ever happened to loop forever. So perhaps we can make this search easier by noticing some non-trivial features of the puzzle input.² In other words… what is our program actually doing?

Let’s disassemble our program — rewrite it so it uses instructions, rather than opcode/operand numbers. For purposes of illustration, I’ll be using the program 0,3,5,4,3,0 from the example input;³ the features I point out should still apply to the program from your puzzle input. The result should look a little something like this:

A few things to notice:

• The last instruction is jnz 0, which jumps back to the beginning of the program if the A register is nonzero.
  • This means the whole program is one big loop, which always runs at least once, and continues to loop until the A register is zero at the end.
• The only instruction that changes the A register is an adv 3 instruction, which shifts A to the right by 3 bits on each pass of the loop.
  • This means the loop won’t run forever, because doing adv 3 repeatedly will eventually shift out all the bits of A and leave A at zero.
• Before the loop ends, an out instruction is performed, which outputs a single number on each pass of the loop.
  • This means the length of the output will depend on how big A is; in other words, one number will be outputted for every 3-bit chunk of A.

This is a lot to take in, but the short version is: the program looks at each 3-bit chunk of A from right to left, and outputs a single number per chunk. This suggests that we can use some approach similar to depth-first search (DFS) to build a working value of A one 3-bit chunk at a time. Let’s get to it.

First thing’s first: I’ll convert this solution to a unified solve function for both parts.

...

class Solution(StrSplitSolution):
    ...

    def solve(self) -> tuple[str, int]:
        registers, program = (
            tuple(map(int, re.findall(r"\d+", block)))
            for block in self.input
        )
        program_output = ",".join(map(str, run(registers, program)))

        ...

        min_quine_input = -1  # TODO Write find-quine-input code
        return program_output, min_quine_input

Now for the interesting part: searching for A values that’ll give us back our program as an output. The way I’ll do this similar to DFS; in fact, I’ll be using a recursive function for this, which will take an A value and the number $n$ of matched program digits so far.

• Base case: If (given this A value) the program’s output matches the program exactly, this A value is a “quine input”.
• Recursive case: If (given this A value) the program’s output matches the last $n$ digits of the program, try appending another 3-bit chunk to A (in each different possible way) and looking for a match of $n + 1$ digits. Otherwise, we’re at a dead end.

Because I’m rather fond of generator functions, I’m using yet another generator function for this; it’ll yield all of our “quine inputs”, and we can pass them directly to min to find the smallest one. Some notes about my implementation:

• program[-n:] gets the last n items of program — unless n is 0, in which case it gets every item of program. Because of this little quirk, I do a check for whether num_digits is 0 before I use it in this way.
• The way I append the next 3-bit chunk (which I call next_a_bits) to the A value is by shifting A leftward by 3 bits, and then doing a | (bitwise OR) with that chunk — i.e. (a_input << 3) | next_a_bits. This is a pretty standard way to do this with bitwise operations.

...

class Solution(StrSplitSolution):
    ...

    def solve(self) -> tuple[str, int]:
        ...
        # HACK To make the problem tractable, we must make several
        # assumptions about the structure of the program: it is a loop
        # that, on each pass until A is 0, consumes 3 bits of A and
        # outputs one number. This allows us to build an A value 3 bits
        # at a time until the output matches the program.
        ADV_OPERAND = 3  # Our program will include an "adv 3"
        _, b, c = registers

        def quine_inputs(
                a_input: int = 0,
                num_digits: int = 0,
        ) -> Iterator[int]:
            output = tuple(run((a_input, b, c), program))
            # If the output matches the program, this A is a quine input
            if output == program:
                yield a_input
                return
            # If the output matches the program's last few digits, try
            # assigning the next bits of A
            if num_digits == 0 or output == program[-num_digits:]:
                for next_a_bits in range(1 << ADV_OPERAND):
                    yield from quine_inputs(
                        (a_input << ADV_OPERAND) | next_a_bits,
                        num_digits + 1,
                    )

        min_quine_input = min(quine_inputs())
        return program_output, min_quine_input

Not the easiest thing in the world… but hey, we managed to figure out the right input value without the Historians’ computer breaking down! That’s always what you want when debugging a program.