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
- Trying to understand how the
instruction pointer
works - Using the example walkthrough to solidify understanding
- 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 a6
-element array, where each value starts as 0:0,0,0,0,0,0
- 16
opcode
s 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
- It can't be that easy...can it?
- 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.
Top comments (0)