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
- Brute-force process of elimination, here I come!
- Two observations
- Doing more analysis of the program
- Feeling exhausted
- 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
- The output is seemingly always
0
s for even starting numbers and1
s for odd starting numbers - 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 myout
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!
Top comments (0)