Another CPU type problem. I took the react app I wrote for Day 23, 2016, retooled it for this “Device,” and went to analyzing the program for part two.
Part one is straight forward, it runs quickly.
Part two, however, would require some tricks to see what the program was actually doing.
Looking at the input, and drawing lines between the jumps, our program looks like this:
0. set b 67
1. set c b
2. jnz a 2 ->----+
3. jnz 1 5 -->---P---->-+
4. mul b 100 <---+ |
5. sub b -100000 Q
6. set c b |
7. sub c -17000 |
8. set f 1 <---------+-+
9. set d 2 ^
10. set e 2 <-------+ |
11. set g d <-----+ | |
12. mul g e | | |
13. sub g b | | |
14. jnz g 2 ->-+ | | |
15. set f 0 A X | |
16. sub e -1 <-+ | | |
17. set g e | Y |
18. sub g b | | |
19. jnz g -8 ->----+ | Z
20. sub d -1 | |
21. set g d | |
22. sub g b | |
23. jnz g -13 ->-----+ |
24. jnz f 2 ->-+ |
25. sub h -1 B |
26. set g b <-+ |
27. sub g c |
28. jnz g 2 ->---+ |
29. jnz 1 3 C |
30. sub b -17 <--+ |
31. jnz 1 -23 ->-------+
P and Q are the paths that happen when you flip a to 1 in part two. They are relatively straight-forward:
b and c get set to 67, and we go to instruction 8, the start of the main Z loop.b gets set to 106700, and c gets set to 106700 + 17000 = 123700 and also start on instruction 8.As it moves toward the X inner loop (this one gets hit a lot), it sets f to 1, and initializes d and e to 2.
Next, starting on instruction 11, this X loop essentially:
d * e is equal to the value in b. If so, it doesn’t skip the A jump, and importantly changes f from 1 to 0.e by one until it reaches the value in b.Once we break out of the X loop onto instruction 20, we then
d by one.d is equal to b. If so continue on. Otherwise, loop back up through Y.Y is the same as the start as X, except it resets e back to 2.This keeps happening until we multiply every number between 2 and b, ending with d and e being equal to b. That then breaks us out of the Y loop.
Once there, we
f is equal to 0. If so, add 1 to register h. Otherwise, its jumps through B to skip this.Now we are on instruction 26.
b is equal to c. If so, exit the program.b and loop back through Z to start the whole thing over again!So, what this program does is…
Looks for prime numbers!
Specifically, starting at 106700, in increments of 17, check how many numbers are not prime for 1000 iterations, inclusively.
In JS that might look like:
// Simple prime number checker.
function isPrime(num) {
if (num === 2) {
return true;
}
let s = Math.sqrt(num);
for (let i = 2; i <= s; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
function run() {
let count = 0;
let start = 106700;
let increment = 17;
// Importantly, our loop is _inclusive_, so use `<=` comparison.
for (let n = start; n <= start + 1000 * increment; n += increment) {
if (!isPrime(n)) {
count++;
}
}
return count;
}
run();
Running the above, gives us our answer: 905!
For the application, it works the same way. I’ll copy in the instructions I originally wrote:
To run this yourself, the application works as follows:
When the app starts, you’ll need to initialize it with your program. Paste in your program’s input and submit to start the program. It defaults to the input I received.
Press the play button (▶) to run the program until the break point. If no point is set, it’ll run until the program finishes. The steps under the play button step forward 1, 10, and 100 ticks, respectively.
The break point can be any expression that’ll be
eval‘d. Usea,b,c, …hvariables for the registers, andifor the instruction. For instance, to run until the program is at instruction 22, just enteri === 22into the breakpoint. To run until it is at instruction 16 and registergis greater than to 10, then you’d havei === 16 && g > 10.At the top, you can change any register to any value, change what instruction the program is at by typing in
i, and can even change arbitrary lines by typing inl. Once you type in the action, press set to save the change.For instance, for part two, I had to change register
ato1.As always, code is untranspiled: modern browsers only.
You decide to head directly to the CPU and fix the printer from there. As you get close, you find an experimental coprocessor doing so much work that the local programs are afraid it will halt and catch fire. This would cause serious issues for the rest of the computer, so you head in and see what you can do.
The code it's running seems to be a variant of the kind you saw recently on that tablet. The general functionality seems very similar, but some of the instructions are different:
set X Y sets register X to the value of Y.sub X Y decreases register X by the value of Y.mul X Y sets register X to the result of multiplying the value contained in register X by the value of Y.jnz X Y jumps with an offset of the value of Y, but only if the value of X is not zero. (An offset of 2 skips the next instruction, an offset of -1 jumps to the previous instruction, and so on.)Only the instructions listed above are used. The eight registers here, named a through h, all start at 0.
The coprocessor is currently set to some kind of debug mode, which allows for testing, but prevents it from doing any meaningful work.
If you run the program (your puzzle input), how many times is the mul instruction invoked?
4225
Now, it's time to fix the problem.
The debug mode switch is wired directly to register a. You flip the switch, which makes register a now start at 1 when the program is executed.
Immediately, the coprocessor begins to overheat. Whoever wrote this program obviously didn't choose a very efficient implementation. You'll need to optimize the program if it has any hope of completing before Santa needs that printer working.
The coprocessor's ultimate goal is to determine the final value left in register h once the program completes. Technically, if it had that... it wouldn't even need to run the program.
After setting register a to 1, if the program were to run to completion, what value would be left in register h?
905