Chronal Conversion
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-06-09 13:51:55

## [Advent of Code 2018 Day 21](https://adventofcode.com/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](https://www.reddit.com/r/adventofcode/comments/a86jgt/comment/ec8fnq8/?utm_source=share&utm_medium=web2x&context=3) 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.