Go With The Flow

Advent of Code 2018 Day 19

Skipping days, still?

• I intended to move from Day 22 to 21
• Day 21 referenced Days 16 and 19
• I skipped to Day 16 and, delightfully, solved both parts
• It felt most sensical to continue on to 19
• I'll try to solve both parts of today, then move back to Day 21, then continue my backwards movement

Task: Solve for X where...

Part 1

X = the value left in register 0 when the background process halts - starting with 0 in register 0

Part 2

X = the value left in register 0 when the background process halts - starting with 1 in register 0

Example input

#ip 0
seti 5 0 1
seti 6 0 2
addi 0 1 0
addr 1 2 3
setr 1 0 0
seti 8 0 4
seti 9 0 5

It represents:

• A program comprised of instructions that updated a device's registers
• Instructions are comprised of an opcode, two inputs and an output register
• The first line specifies the register that the instruction pointer will be bound to

Part 1

1. Trying to understand how the instruction pointer works
2. Using the example walkthrough to solidify understanding
3. Feeling confident enough to attempt updating my existing algorithm

Trying to understand how the instruction pointer works

New player has joined:

• This puzzle introduces an instruction pointer
• It is a number that points to the next instruction to be processed

What state I have to track:

• registers as a 6-element array, where each value starts as 0: 0,0,0,0,0,0
• 16 opcodes that each operate on up to 3 values: two inputs and one output in one of two modes: immediate (value) or position (register)
• The numeric value of an instruction pointer before and after an instruction is processed
• The register that has the instruction pointer bound to it

How the instruction pointer starts and generally behaves:

• The instruction pointer starts at 0
• The instruction pointer is 0 during the first instruction, 1 during the second, and so on

The condition that would cause the program to halt:

• If the instruction pointer ever causes the device to attempt to load an instruction outside the instructions defined in the program, the program instead immediately halts

How the instruction pointer is accessed and updated:

When bound to a register
  Before executing instruction:
    Write instruction pointer value to register
  After executing instruction:
    Write register value to instruction pointer

After executing instruction
  Increment the instruction pointer by 1

I'm fuzzy on the explanation above.

And I'm fuzzy on the caveat below.

Because of (the final increment step), instructions must effectively set the instruction pointer to the instruction before the one they want executed next.

Using the example walkthrough to solidify understanding

The example, again:

#ip 0
seti 5 0 1
seti 6 0 2
addi 0 1 0
addr 1 2 3
setr 1 0 0
seti 8 0 4
seti 9 0 5

Initial state

ip = 0
ip_register = 0
registers = [0,0,0,0,0,0]
             * <-register bound to ip
opcodes = { 16 4-letter opcode methods(A,B,C) }

Round 1

Since the value of ip is 0, the instruction at location 0 is next to be executed:

seti 5 0 1

seti (set immediate) stores value A into register C. (Input B is ignored.)

Before running it:
Update register 0 to the current value of ip: 0

[0,0,0,0,0,0]

seti stores 5 into register 1:

[0,5,0,0,0,0]

After running it:
Set ip to register 0's current value: 0
Add 1 to ip

ip = 1
registers = [0,5,0,0,0,0]

Round 2

Since the value of ip is 1, the instruction at location 1 is next to be executed:

seti 6 0 2

seti (set immediate) stores value A into register C. (Input B is ignored.)

Before running it:
Update register 0 to the current value of ip: 1

[1,5,0,0,0,0]

seti stores 6 into register 2:

[1,5,6,0,0,0]

After running it:
Set ip to register 0's current value: 1
Add 1 to ip

ip = 2
registers = [1,5,6,0,0,0]

Round 3

Since the value of ip is 2, the instruction at location 2 is next to be executed:

addi 0 1 0

addi (add immediate) stores into register C the result of adding register A and value B

Before running it:
Update register 0 to the current value of ip: 2

[2,5,6,0,0,0]

addi stores 3 into register 0:

[3,5,6,0,0,0]

After running it:
Set ip to register 0's current value: 3
Add 1 to ip

ip = 4
registers = [3,5,6,0,0,0]

Round 4

Since the value of ip is 4, the instruction at location 4 is next to be executed:

setr 1 0 0

setr (set register) copies the contents of register A into register C. (Input B is ignored.)

Before running it:
Update register 0 to the current value of ip: 4

[4,5,6,0,0,0]

setr stores 5 into register 0:

[5,5,6,0,0,0]

After running it:
Set ip to register 0's current value: 5
Add 1 to ip

ip = 6
registers = [5,5,6,0,0,0]

Round 5

Since the value of ip is 6, the instruction at location 6 is next to be executed:

seti 9 0 5

seti (set immediate) stores value A into register C. (Input B is ignored.)

Before running it:
Update register 0 to the current value of ip: 6

[6,5,6,0,0,0]

seti stores 9 into register 5:

[6,5,6,0,0,9]

After running it:
Set ip to register 0's current value: 6
Add 1 to ip

ip = 7 (Outside of program)
registers = [6,5,6,0,0,9]

Program halts because instruction pointer points outside the program.

Feeling confident enough to attempt updating my existing algorithm

• Walking through that example was a huge help
• I now have repeatable pseudocode for how my algorithm must work
• It's time to expand my code and test on this example in hopes of generating the same registers at each step

Regular expression, really?

I feel so silly.

In attempts to extract the opcode and each parameter from a string like this:

seti 0 1 0

I used this regular expression:

/(\w{4}) (\d+) (\d+) (\d+)/g

Then I realized I could have split the string at each space character.

I'll take it as a sign of progress that I defaulted to using a regular expression.

The main loop

Do as long as the value of instruction pointer is within the bounds of the list of instructions
  Update the bound register to the current value of instruction pointer
  Execute the instruction using the two inputs and output
  Set instruction pointer to the bound register's current value
  Increment instruction pointer by 1

Testing the loop

• Running it on the example: instant success!
• Running it on my input: delayed success!

Part 2

1. It can't be that easy...can it?
2. Looking for clues at specific intervals

It can't be that easy...can it?

• Change the first value from 0 to 1 in registers, and re-run? Ok!

...
...
...

Seemingly runs forever. That's what I was afraid of.

What's going on?

Looking for clues at specific intervals

How many times does the loop run in Part 1?

• Over 6 million times!

How does registers seem to change?

• I log the state of registers whenever the value at register 0 is updated
• This reveals an interesting pattern

[ 1,  888, 7, 888,   1, 1 ]
[ 3,  444, 7, 888,   2, 1 ]
[ 6,  296, 7, 888,   3, 1 ]
[ 10, 222, 7, 888,   4, 1 ]
[ 16, 148, 7, 888,   6, 1 ]
[ 24, 111, 7, 888,   8, 1 ]
[ 36,  74, 7, 888,  12, 1 ]
[ 60,  37, 7, 888,  24, 1 ]
[ 97,  24, 7, 888,  37, 1 ]
[ 171, 12, 7, 888,  74, 1 ]
[ 282,  8, 7, 888, 111, 1 ]
[ 430,  6, 7, 888, 148, 1 ]
[ 652,  4, 7, 888, 222, 1 ]
[ 948,  3, 7, 888, 296, 1 ]
[ 1392, 2, 7, 888, 444, 1 ]
[ 2280, 1, 7, 888, 888, 1 ]

Interesting:

• The values at indices 1 and 4 are in reverse-identical order!

When I attempt to run the program with register 0's value as 1, I see this much output before the program stops:

[   0, 0, 34, 10551288, 0, 10550400 ]
[   1, 10551288, 7, 10551288,  1, 1 ]
[   3,  5275644, 7, 10551288,  2, 1 ]
[   6,  3517096, 7, 10551288,  3, 1 ]
[  10,  2637822, 7, 10551288,  4, 1 ]
[  16,  1758548, 7, 10551288,  6, 1 ]
[  24,  1318911, 7, 10551288,  8, 1 ]
[  35,   959208, 7, 10551288, 11, 1 ]
[  47,   879274, 7, 10551288, 12, 1 ]
[  64,   620664, 7, 10551288, 17, 1 ]
[  86,   479604, 7, 10551288, 22, 1 ]
[ 110,   439637, 7, 10551288, 24, 1 ]
[ 143,   319736, 7, 10551288, 33, 1 ]
[ 177,   310332, 7, 10551288, 34, 1 ]

Unfortunately, I can't determine whether the values in indices 1 and 4 ever cross paths.

I sense that they do.

Sadly, I can't think critically enough to further inspect the program or the state of registers at any given time to identify the remaining trajectory of outputs

Celebrating my accomplishments

• I solved Part 1!
• I've now solved 3/4 opcode-themed puzzles this year
• I know my device works well enough to attempt Day 21's puzzle

Bummers:

• I didn't solve Part 2
• No GIFs: I spent enough time walking through each example here in the post and describing my working algorithm
• No simulator: Again, there was nothing particularly interesting to see...other than how a few values changed throughout each iteration. I definitely wouldn't have been able to show every iteration in either case, given that Part 1 featured millions, and Part 2 likely featured trillions!

I'm hopeful I can acquire at least one more gold star by completing Part 1 of Day 21.