Chronal Conversion

Advent of Code 2018 Day 21

Task: Solve for X where...

Part 1

X = the lowest non-negative integer value for register 0 that causes the program to halt after executing the fewest instructions

Part 2

X = the lowest non-negative integer value for register 0 that causes the program to halt after executing the most instructions

No example input is given.

Part 1

1. Another open-ended puzzle
2. Attempting to study the behavior of the program using unaltered registers
3. Finding instructions that operate on register 3 and 0
4. Cheater!!!
5. Voila!

Another open-ended puzzle

• With all registers set to 0, the program never halts
• That must be fixed: the program has to halt
• To fix it, I must first study how it works
• Then, I must find some positive number that - when used instead of 0 at register 0 - causes the program to halt
• Then, I must find some positive number that does the same, but with the added caveat that the program performed the fewest possible instructions

Thus, the answer is within the spectrum:

• 0 - near-Infinity

Great.

Time to start studying the program.

Attempting to study the behavior of the program using unaltered registers

I used a for loop that ran 80 times, just to preview things.

What I observed:

• The value at register 0 doesn't change
• The value at register 1 increases by 256 at the same interval
• The value at register 2 increments by 1 from time to time
• The value at register 3 (bound to my instruction pointer) goes up to 25, then repeats going from 18-25
• The values at registers 4 and 5 - except for the first few instructions - seem to remain static

Note to reader: I'll soon be kicking myself for not running this for loop for longer than 80 times.

I looked at my puzzle input, specifically at instruction 25, for a sign. I didn't find one.

Sadly, I was stumped.

Finding instructions that operate on register 3 and 0

My marked-up puzzle input:

#ip 3
S seti 123 0 4      x
B bani 4 456 4      x
E eqri 4 72 4       x
A addr 4 3 3    R   x
S seti 0 0 3    R   x
S seti 0 6 4        x
B bori 4 65536 5    x
S seti 1855046 9 4  x
B bani 5 255 2      x
A addr 4 2 4        x
B bani 4 16777215 4 x
M muli 4 65899 4    x
B bani 4 16777215 4 x
G gtir 256 5 2      x
A addr 2 3 3    R   x
A addi 3 1 3    R   x
S seti 27 0 3   R   x
S seti 0 9 2        x
A addi 2 1 1        x
M muli 1 256 1      x
G gtrr 1 5 1        x
A addr 1 3 3    R   x
A addi 3 1 3    R   x
S seti 25 5 3   R   x
A addi 2 1 2        x
S seti 17 0 3   R   x
S setr 2 7 5        x
S seti 7 9 3    R   x
E eqrr 4 0 2        ???
A addr 2 3 3    R   x
S seti 5 3 3    R   x

• The capital letter marks the category - I was looking for bani,bori,borr,banr
• The capital R marks instructions that update register 3, to which my instruction pointer is bound
• The x marks instructions that DON'T set or use register 0
• The ??? marks the only instruction that DOES use register 0

The only instruction that uses register 0 is instruction 28.

Sadly, I sabotaged myself by thinking I knew how the program worked by seeing only 80 iterations.

So, I was left to believe instruction 28 was never encountered.

Thus, I felt stumped...again.

Cheater!!!

To recap:

• I thought I discovered a clue with instruction 28 being the only one that used register 0
• I foolishly thought I saw all that the program did in the first 80 iterations...and it didn't read instruction 28
• I was still confused by the puzzle's instructions referenced bani,bori,borr,banr
• I was frustrated about not being able to solve this (hopefully?!) last opcode-themed puzzle of 2018

So, I cheated.

• I went to the Advent of Code Sub-Reddit
• Found the Solution Megathread
• Clicked on 2018 - Day 21
• Started scrolling

This redditer's comment was the hint I needed!

SPOILER (a.k.a. hint):

The approach I used for my input was realizing that the only time register 0 was being used was on line 28, in an eqrr 3 0 1. I then just began checking what register 3 was every time the ip was 28. For part 1, I just printed out the first value of register 3.

After reading this, I felt:

• Duped by my own lack of experimentation to run the program long enough for it to encounter instruction 28: The first time it does is after 1100 iterations
• Validated that I was on the cusp of the correct answer by focusing on instruction 28
• Excited to update my code to log registers each time instruction 28 was about to run

Voila!

When register 0 contains the same value as that of register A in the puzzle input's instruction 28: eqrr A B C, register C gets updated with a 1 instead of a 0, which causes the program to halt.

Part 2

1. Having already cheated...
2. When the heck does this value repeat?!

Having already cheated...

SPOILER (a.k.a. hint) continued:

For part 2, I checked when the value in register 3 finally repeats. When it does, the last value must have been the one that causes the most instructions.

That makes perfect sense.

When the heck does this value repeat?!

The answer:

• Not for a while

The journey:

• I started the program
• I walked away
• I came back several times
• Still running
• What seemed like nearly 10 minutes later, it stopped
• What was left was an 8-digit integer
• Which was the correct answer!

I did it!!! (by cheating)

• I wrote an algorithm that generated the correct answer for both parts!
• I've now attained 5/6 gold stars for these opcode-themed puzzles in 2018!

Bummers:

• I didn't solve the puzzles alone
• I feel like I could have, had I not stopped at 80 iterations of a loop
• I didn't make a simulator: to reiterate, these non-ASCII opcode puzzles aren't really worth simulating

Reflecting on all opcode-themed puzzles

Likes

• The ASCII-drawing ones were such a delight to solve and even more delightful to simulate
• I learned how bitwise AND and OR operators worked
• For puzzles that featured example input and/or output, I felt encouraged and satisfyingly confident to attempt solving the puzzle
• Having attempted all and solved most, these puzzles served as a fun continual series that built toward a few very intense and equally rewarding puzzles, especially the droid-controlling, ASCII-drawing ones at the end of 2019

Dislikes

• Many puzzles didn't feature example input or output, which is always helpful as a sort of test to get passing while crafting an algorithm...and therefore made me less confident to attempt solving the puzzle
• For puzzles that required modifying the program so it would halt, it quickly got frustrating to have to reverse-engineer the whole program in order to properly diagnose the issue
• In other words, these puzzles were the least fun to debug and troubleshoot

I hope there are no other opcode-themed puzzles.

If there are, I hope I'm over-prepared to solve them, since I've been working backwards.