Clock Signal

Advent of Code 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 0s for even starting numbers and 1s 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

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!