Clock Signal
Tags: adventofcode, algorithms, programming, javascript
Published: 2022-08-12 21:30:13

## [Advent of Code 2016 Day 25](https://adventofcode.com/2016/day/25)

## My journey thus far
- Started Day 25...only to realize...
- Solving it depends on having written algorithms as part of a few days prior, namely: 11, 12, 23
- Skipped to Day 11
- Completing that puzzle wasn't necessary, thankfully - as I was unable
- Successful in solving both parts of Day 12 - enabling me to attempt Day 23
- Solved Part 1 of Day 23, and, after giving up, found a shortcut to solving Part 2
- Arrived back at Day 25 only to discover that Day 12 was the only prerequisite: there's no `tgl` opcode in my puzzle input

## Part 1
1. Brute-force process of elimination, here I come!
2. Two observations
3. Doing more analysis of the program
4. Feeling exhausted
5. Reddit, for the reveal!

### Brute-force process of elimination, here I come!
I need to find:
> the lowest positive integer that can be used to initialize register a and cause the code to output a clock signal of 0, 1, 0, 1... repeating forever

I guess I'll start with `0`.

```
Set output as an empty array
Set value as 0

Do until output contains the numbers - in order - 0,1,0,1
  Create a copy of the program
  Set register a to value

  Do as long as output's length is less than four
    Run the next instruction in the program
      If the instruction uses the out opcode, add the appropriate integer to output

  Check whether output contains the numbers - in order - 0,1,0,1

  If it is, escape the loop
  Else, increment value by 1 and reset output to an empty array

Return value
```

I anticipate the answer is somewhere in the millions or billions.

Therefore, I'll need to include some logging statements to see how high `value` gets, so I can restart the algorithm from that checkpoint, or attempt to skip several numbers.

Let's build it and see if this has any merit!

### Two observations
1. The output is seemingly always `0`s for even starting numbers and `1`s for odd starting numbers
2. The program runs slower the larger the starting number is

I wonder what's causing all this?

### Doing more analysis of the program
I want to know how many instructions are processed before `output` has two numbers in it.
- I add a counter
- I increment the counter in my `while` loop
- I display the counter when the `while` loop exits

I see this:
```
0 [ 0, 0 ] 21623
1 [ 1, 1 ] 21623
2 [ 0, 0 ] 21634
3 [ 1, 1 ] 21634
4 [ 0, 0 ] 21645
5 [ 1, 1 ] 21645
```

Hmm:
- Each even-odd pair performs the same amount of steps
- Each subsequent pair performs 11 more steps

Also, that's a ton of operations!

Now, I wonder:
- How often is register `b` changing?

Because my puzzle input features a single `out` instruction, with `b` as the argument.

The answer?
- A lot!
- It regularly gets reset to 282
- Then counts down to 0
- Sometimes it gets up above 2000

### Feeling exhausted
- I really hate these `opcode` puzzles
- They're just too frustrating for me to analyze
- It hurts my brain walking them line-by-line
- And every time I try, I fail to be rewarded with a useful answer

So, I give up.

### Reddit, for the reveal!
Oh my! Tons of rabbit - nay, bunny! - holes to expore!
- There were several descriptions by various solvers as to what the instructions were doing and how to `shortcut` the program
- The one I found most insightful and concise was [this solver's explanation](https://www.reddit.com/r/adventofcode/comments/5k6yfu/comment/dbltx5f/?utm_source=share&utm_medium=web2x&context=3)

Much like with Day 23, the start of the answer resided in two key statements: a pair of `cpy` that set registers `c` and `b`.

For my puzzle input, these statements are:
```
cpy 9 c
cpy 282 b
```

Multiplying those together gets me:
```
9 * 282 = 2538
```

I then need an algorithm that identifies the closest number that's larger than `2538` among a list of integer apparently known as the "Lichtenberg sequence":
```
1, 2, 5, 10, 21, 42, 85, 170, 341, 682, 1365, 2730, 5461...
```

The algorithm that the solver offered looks like this:
```
Set target as the product of both numbers
Set n to 1
Do as long as n is less than target
  If n is even
    Set n to itself doubled, plus 1
  Else
    Set n to itself doubled
Return n - target
```

What a simple, eloquent algorithm for generating the number list shown above!

When run using my number, I get:
```
2730 - 2538 = 192
```

Therefore, the correct answer using my puzzle input should be `192`.
- I plug in `192` as the first value for my algorithm
- I run it
- I see an output of `[0,0,0,0]`
- What's happening?

#### Oh my goodness, again!?
- I forgot to increment `pointer` by 1 in my `out` method!
- You've got to be kidding me!

With that fixed, I decide to run the program from `0`, expecting it to end at `192`:
- It ends at `0`
- What's happening now?

Well, `0` is the lowest non-negative integer that works.

But the puzzle asks for the lowest `positive` integer that works.

So, I need to start from `1`, not `0`.
- Now it ends at `34`
- What's happening now?

Well, I end the loop as soon as `output` contains four numbers: `0`,`1`,`0`,`1`

I need to expand that quite a bit, because it's highly likely that the next number is a `1` instead of a `0`.

I expand it to `8` numbers.

Now it ends at `62`.

I expand it to `24` numbers.

Finally, it ends at `192`!

## Reflecting on today's puzzle
I just couldn't crack the code!

Thankfully, Reddit helped me identify all sorts of missteps in my algorithm and analysis:
- I omitted the pointer increment step in my new method!
- I started my search at `0`, a non-positive integer!
- I didn't collect enough numbers of output!

In hindsight, I really wish I had done all three correctly.

Because my algorithm would have returned `192` almost instantly.

Then again, if it had, I never would have spent this much time understanding the subtle secrets of this program.

Anyway, on to what I hope is a non-assembly, non-pathfinding, challenging but accessible puzzle in Day 24!