Here is my solution for Day 19.

I did not even attempt to make a solution that would solve part 2 for any input (in a reasonable time).

Instead, I looked at the trace of the execution of my input and found the inner loop. I then wrote an optimized version of the inner loop.

To run the optimized version, I implemented a general mechanism for installing a breakpoint handler and installed my optimized inner loop as a breakpoint handler. The breakpoint handler will only be installed for code similar to my input program (it must be the same instructions, but it registers could be different).

My solution runs in less than 20 seconds.

I actually wrote a decompiler/debugger in Elixir to poke with the program. It was sooo much fun!

45986×1450 109 KB

This idea with installing the optimized loop is very interesting.

I just reverse engineered the entire program. I started by inspecting the first 100 states to quickly figure out where’s the inner loop, what is its input, and what is the effect of a single pass through it on the registers. Then I annotated my program and spent some time understanding what it does. After awhile, it became clear to me that the program first computes the input number, stores it to r4, and then iteratively finds all the divisors of that number, adding them into r0 (which is set to 0 before entering the loop). So finally, I wrote the equivalent program in Elixir

The complete solution is here, and it takes about 6 sec combined for both parts.