≡ Day 17 of Advent of Code in q

Author - Rory Kemp

Original Problem Statement

--- Day 17: Chronospatial Computer ---

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:

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:

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:

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?

The first step is to read the input.

show (A;B;C;::;P):{get last ": "vs x} each read0 `17.txt
729
0
0
::
0 1 5 4 3 0

Now, define functions for all of the various operations. Each will take the current instruction pointer and the operand.

We define two helper functions, one to convert from a literal operand to a combo operand, and one for xor, as it isn't built in.

combo:{(0 1 2 3,A,B,C)x}

xor:{2 sv (<>)./:2 vs (x;y)}

Now, define each of the 8 instructions, and a list storing them all.

adv:{A::A div prd combo[y]#2; x+2}

bxl:{B::xor[B;y]; x+2}

bst:{B::combo[y] mod 8; x+2}

jnz:{$[A=0; x+2; y]}

bxc:{[x;y] B::xor[B;C]; x+2}

OUT:(); out:{OUT,:combo[y] mod 8; x+2}

bdv:{B::A div prd combo[y]#2; x+2}

cdv:{C::A div prd combo[y]#2; x+2}

ops:(adv;bxl;bst;jnz;bxc;out;bdv;cdv)

They are all simple to implement, directly translating the specification for each from the problem description. We are storing A, B, C, and the OUT variable as globals. Passing around a state "object" would also work, but would be slightly clunkier.

Now, we need to run the "program".

{x<count P}{ops[P x;x;P x+1]}\0
0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 0 2 4 6

While the instruction pointer is within range, we select the function required, and call it.

Now, we can view the output.

","sv string OUT

Part 2:

Part 2 Original Description:

--- Part Two ---

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:

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?

Let's wrap the process in a function, that takes in the value for A, and returns the OUT value.

run:{A::x; B::C::0; OUT::(); {x<count P}{ops[P x;x;P x+1]}/0; OUT}

Now, set the program to the new example.

P: 0,3,5,4,3,0

We can check that with an input of 117440 it should return itself.

run 117440

There are various ways to approach this, but one would be to guess that given we seem to be working with base 8 and with bit operations (shifting/xor) we should examine the base 8 representation of A.

8 vs 117440
3 4 5 3 0 0

This doesn't seem that helpful, other than noting it is the same length as the program.

We can also try encoding from base 8, and seeing what happens.

run each 8 sv' (1 2 3;1 2 3 4;1 2 3 4 5)
2 1 0
3 2 1 0
4 3 2 1 0

This seems useful. It seems like appending a new value prepends a value to the output. This makes sense if it is doing some sort of process from the low bits to the high bits.

Let's write a function that takes a partial input and searches for new values that partially match the program.

new:{new where (neg[1+count x]#P)~/:run each 8 sv' new:x,/:til 8}

And run it count P times starting from the empty list.

count[P] {raze new each x}/ enlist til 0
3 4 5 3 0 0
3 4 5 3 0 1
3 4 5 3 0 2
3 4 5 3 0 3
3 4 5 3 0 4
3 4 5 3 0 5
3 4 5 3 0 6
3 4 5 3 0 7

We can see we get the base 8 value from before. All that's left is to convert back to integers and take the minimum. 

min 8 sv' count[P] {raze new each x}/ enlist til 0
117440

Recap:

The full solution is this. 
(A;B;C;::;P):{get last ": "vs x} each read0 `17.txt
combo:{(0 1 2 3,A,B,C)x}
xor:{2 sv (<>)./:2 vs (x;y)}
adv:{A::A div prd combo[y]#2; x+2}
bxl:{B::xor[B;y]; x+2}
bst:{B::combo[y] mod 8; x+2}
jnz:{$[A=0; x+2; y]}
bxc:{[x;y] B::xor[B;C]; x+2}
OUT:(); out:{OUT,:combo[y] mod 8; x+2}
bdv:{B::A div prd combo[y]#2; x+2}
cdv:{C::A div prd combo[y]#2; x+2}
ops:(adv;bxl;bst;jnz;bxc;out;bdv;cdv)
{x<count P}{ops[P x;x;P x+1]}\0
","sv string OUT
run:{A::x; B::C::0; OUT::(); {x<count P}{ops[P x;x;P x+1]}/0; OUT}
new:{new where (neg[1+count x]#P)~/:run each 8 sv' new:x,/:til 8}
min 8 sv' count[P] {raze new each x}/ enlist til 0