Robert Mion

Posted on

# Chronal Conversion

## 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.

### 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
• 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.

• 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

2. When the heck does this value repeat?!

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?!

• 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.