The Historians push the button on their strange device, but this time, you all just feel like you're falling.

"Situation critical", the device announces in a familiar voice. "Bootstrapping process failed. Initializing debugger...."

The small handheld device suddenly unfolds into an entire computer! The Historians look around nervously before one of them tosses it to you.

This seems to be a 3-bit computer: its program is a list of 3-bit numbers (0 through 7), like 0,1,2,3. The computer also has three registers named A, B, and C, but these registers aren't limited to 3 bits and can instead hold any integer.

The computer knows eight instructions, each identified by a 3-bit number (called the instruction's opcode). Each instruction also reads the 3-bit number after it as an input; this is called its operand.

A number called the instruction pointer identifies the position in the program from which the next opcode will be read; it starts at 0, pointing at the first 3-bit number in the program. Except for jump instructions, the instruction pointer increases by 2 after each instruction is processed (to move past the instruction's opcode and its operand). If the computer tries to read an opcode past the end of the program, it instead halts.

So, the program 0,1,2,3 would run the instruction whose opcode is 0 and pass it the operand 1, then run the instruction having opcode 2 and pass it the operand 3, then halt.

There are two types of operands; each instruction specifies the type of its operand. The value of a literal operand is the operand itself. For example, the value of the literal operand 7 is the number 7. The value of a combo operand can be found as follows:

• Combo operands 0 through 3 represent literal values 0 through 3.
• Combo operand 4 represents the value of register A.
• Combo operand 5 represents the value of register B.
• Combo operand 6 represents the value of register C.
• Combo operand 7 is reserved and will not appear in valid programs.

The eight instructions are as follows:

The adv instruction (opcode 0) performs division. The numerator is the value in the A register. The denominator is found by raising 2 to the power of the instruction's combo operand. (So, an operand of 2 would divide A by 4 (2^2); an operand of 5 would divide A by 2^B.) The result of the division operation is truncated to an integer and then written to the A register.

The bxl instruction (opcode 1) calculates the bitwise XOR of register B and the instruction's literal operand, then stores the result in register B.

The bst instruction (opcode 2) calculates the value of its combo operand modulo 8 (thereby keeping only its lowest 3 bits), then writes that value to the B register.

The jnz instruction (opcode 3) does nothing if the A register is 0. However, if the A register is not zero, it jumps by setting the instruction pointer to the value of its literal operand; if this instruction jumps, the instruction pointer is not increased by 2 after this instruction.

The bxc instruction (opcode 4) calculates the bitwise XOR of register B and register C, then stores the result in register B. (For legacy reasons, this instruction reads an operand but ignores it.)

The out instruction (opcode 5) calculates the value of its combo operand modulo 8, then outputs that value. (If a program outputs multiple values, they are separated by commas.)

The bdv instruction (opcode 6) works exactly like the adv instruction except that the result is stored in the B register. (The numerator is still read from the A register.)

The cdv instruction (opcode 7) works exactly like the adv instruction except that the result is stored in the C register. (The numerator is still read from the A register.)

Here are some examples of instruction operation:

• If register C contains 9, the program 2,6 would set register B to 1.
• If register A contains 10, the program 5,0,5,1,5,4 would output 0,1,2.
• If register A contains 2024, the program 0,1,5,4,3,0 would output 4,2,5,6,7,7,7,7,3,1,0 and leave 0 in register A.
• If register B contains 29, the program 1,7 would set register B to 26.
• If register B contains 2024 and register C contains 43690, the program 4,0 would set register B to 44354.

The Historians' strange device has finished initializing its debugger and is displaying some information about the program it is trying to run (your puzzle input). For example:

1
2
3
4
5
Register A: 729
Register B: 0
Register C: 0

Program: 0,1,5,4,3,0

Your first task is to determine what the program is trying to output. To do this, initialize the registers to the given values, then run the given program, collecting any output produced by out instructions. (Always join the values produced by out instructions with commas.) After the above program halts, its final output will be 4,6,3,5,6,3,5,2,1,0.

Using the information provided by the debugger, initialize the registers to the given values, then run the program. Once it halts, what do you get if you use commas to join the values it output into a single string?

Output: []

The only tricky thing with this problem was using JavaScript's % operator. While Python implements this as the modulo operator, JavaScript implements this as the remainder operator. As such, I used my own modulo function (the same formula that MDN specifies).

1
2
3
export function modulo(n: number, d: number) {
    return ((n % d) + d) % d;
}

The bulk of the code is very simple. I found that putting the exact instructions into the code as comments helped make it extremely readable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
const parser = z.array(z.coerce.number());
const values = parser.parse(input.replace("Program: ", "").split(","));

class Program {
    instructionPointer: number;
    program: Array<number>;

    registerA: number;
    registerB: number;
    registerC: number;

    running: boolean;
    output: Array<number>;

    constructor() {
        this.instructionPointer = 0;
        this.program = JSON.parse(JSON.stringify(values));

        this.registerA = registerA;
        this.registerB = registerB;
        this.registerC = registerC;

        this.running = true;
        this.output = [];
    }

    comboOperand(operand: number) {
        switch (operand) {
            case 0:
                return 0;

            case 1:
                return 1;

            case 2:
                return 2;

            case 3:
                return 3;

            case 4:
                return this.registerA;

            case 5:
                return this.registerB;

            case 6:
                return this.registerC;

            default:
                throw new Error(`Unknown operand: ${operand}`);
        }
    }

    step() {
        const opcode = this.program[this.instructionPointer];
        const operand = this.program[this.instructionPointer + 1];

        // If the computer tries to read an opcode past the end of the program, it instead halts
        if (opcode === undefined || operand === undefined) {
            this.running = false;
            return;
        }

        switch (opcode) {
            case 0: {
                // The numerator is the value in the A register
                const numerator = this.registerA;

                // The denominator is found by raising 2 to the power of the instruction's combo operand
                const denominator = 2 ** this.comboOperand(operand);

                // The result of the division operation is truncated to an integer and then written to the A register
                this.registerA = Math.floor(numerator / denominator);;

                break;
            }

            case 1: {
                // Calculates the bitwise XOR of register B and the instruction's literal operand
                const value = this.registerB ^ operand;

                // Then stores the result in register B
                this.registerB = value;

                break;
            }

            case 2: {
                // Calculates the value of its combo operand modulo 8
                const value = modulo(this.comboOperand(operand), 8);

                // Then writes that value to the B register
                this.registerB = value;

                break;
            }

            case 3: {
                // Does nothing if the A register is 0
                if (this.registerA === 0) break;

                // It jumps by setting the instruction pointer to the value of its literal operand
                // If this instruction jumps, the instruction pointer is not increased by 2 after this instruction
                // NOTE - decrement by 2 so the +2 below evens out
                this.instructionPointer = operand - 2;
                break;
            }

            case 4: {
                // Calculates the bitwise XOR of register B and register C
                const value = this.registerB ^ this.registerC;

                // Then stores the result in register B
                this.registerB = value;

                break;
            }

            case 5: {
                // Calculates the value of its combo operand modulo 8
                const value = modulo(this.comboOperand(operand), 8);

                // Then outputs that value
                this.output.push(value);

                break;
            }

            case 6: {
                // Works exactly like the adv instruction except that the result is stored in the B register
                // The numerator is the value in the A register
                const numerator = this.registerA;

                // The denominator is found by raising 2 to the power of the instruction's combo operand
                const denominator = 2 ** this.comboOperand(operand);

                // The result of the division operation is truncated to an integer and then written to the B register
                this.registerB = Math.floor(numerator / denominator);;

                break;
            }

            case 7: {
                // Works exactly like the adv instruction except that the result is stored in the C register
                // The numerator is the value in the A register
                const numerator = this.registerA;

                // The denominator is found by raising 2 to the power of the instruction's combo operand
                const denominator = 2 ** this.comboOperand(operand);

                // The result of the division operation is truncated to an integer and then written to the C register
                this.registerC = Math.floor(numerator / denominator);;

                break;
            }

            default:
                throw new Error(`Unknown opcode: ${opcode}`);
        }

        this.instructionPointer += 2;
    }
}

Digging deeper in the device's manual, you discover the problem: this program is supposed to output another copy of the program! Unfortunately, the value in register A seems to have been corrupted. You'll need to find a new value to which you can initialize register A so that the program's output instructions produce an exact copy of the program itself.

For example:

1
2
3
4
5
Register A: 2024
Register B: 0
Register C: 0

Program: 0,3,5,4,3,0

This program outputs a copy of itself if register A is instead initialized to 117440. (The original initial value of register A, 2024, is ignored.)

What is the lowest positive initial value for register A that causes the program to output a copy of itself?

Program: [2,4,1,1,7,5,1,5,4,3,0,3,5,5,3,0]

Output:  []

I don't have a code-solution for Part 2. Instead, I played around with the output and noticed a few things:

• The number of digits in the starting value of register A roughly corresponded to the number of values in the output
• As the starting value of register A increased, the first values in the output changed far more quickly than the later values

I also noticed that the example input had a *solution* that gave a decent starting value for my input. In this example:

1
Program: 0,3,5,4,3,0

I could get an exact answer for the starting value of register A with this code:

1
2
3
4
5
6
const parser = z.array(z.coerce.number());
const values = parser.parse(input.replace("Program: ", "").split(","));

const fastResult = sum(values.map((value, index) => {
    return value * 8 ** (index + 1);
}));

The math works out to be this:

1
2
3
4
5
6
7
8
  0 * 8 ^ 1
  3 * 8 ^ 2
  5 * 8 ^ 3
  4 * 8 ^ 4
  3 * 8 ^ 5
+ 0 * 8 ^ 6
-----------
    117,440

When I ran this on my real input, I got 130502131946256. This wasn't my real answer, but it gave me a good starting value to work with.

To get my real answer, I (painstakingly) modified my input by hand and ran the input through my Part 1 solution to see how that affected the output. If the digits of the output got further away from the input program, I adjusted my input in the other direction.

As the right-most digits of the output aligned with the input program, I move down the input value (starting from the left side and working right), making smaller adjustments to the value until I eventually landed on the correct number.

I'm sure I could've done this through some iterative code, but it was just easier to do it by hand.

I took a big hit on Part 1 with the final ask:

...what do you get if you use commas to join the values it output into a single string?

I somehow interpreted that to mean don't use commas, just join the output into one number. Finally figured it out tho, just wasted 20+ minutes 🙃

Part 2 was interesting. This was the first problem where I did a large chunk of it by hand!

It wasn't fun, but it also wasn't awful ¯\_(ツ)_/¯. It just took awhile, but I didn't need to use much brain power while working on it. So I'm okay with that.

I did see on the subreddit that some people used z3, which is super cool! I can totally see how this would make for a good z3-solver problem, but I have no idea how I'd implement that myself.