Advent of Code - Day 19

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.

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.

I got stuck but after reading your replies I tried to also optimize the loop and I arrived to the same conclusion as @sasajuric: part 2 is basically computing the sum of all divisors for a given number, with some busy wait thrown in for good measure, haha.

However, I have optimized it slightly differently. If I trace the results I get this:

{{1, 0, 0, 0, 0, 0}, :addi, 1, 16, 1, {1, 16, 0, 0, 0, 0}}
{{1, 17, 0, 0, 0, 0}, :addi, 3, 2, 3, {1, 17, 0, 2, 0, 0}}
{{1, 18, 0, 2, 0, 0}, :mulr, 3, 3, 3, {1, 18, 0, 4, 0, 0}}
{{1, 19, 0, 4, 0, 0}, :mulr, 1, 3, 3, {1, 19, 0, 76, 0, 0}}
{{1, 20, 0, 76, 0, 0}, :muli, 3, 11, 3, {1, 20, 0, 836, 0, 0}}
{{1, 21, 0, 836, 0, 0}, :addi, 4, 3, 4, {1, 21, 0, 836, 3, 0}}
{{1, 22, 0, 836, 3, 0}, :mulr, 4, 1, 4, {1, 22, 0, 836, 66, 0}}
{{1, 23, 0, 836, 66, 0}, :addi, 4, 18, 4, {1, 23, 0, 836, 84, 0}}
{{1, 24, 0, 836, 84, 0}, :addr, 3, 4, 3, {1, 24, 0, 920, 84, 0}}
{{1, 25, 0, 920, 84, 0}, :addr, 1, 0, 1, {1, 26, 0, 920, 84, 0}}
{{1, 27, 0, 920, 84, 0}, :setr, 1, 4, 4, {1, 27, 0, 920, 27, 0}}
{{1, 28, 0, 920, 27, 0}, :mulr, 4, 1, 4, {1, 28, 0, 920, 756, 0}}
{{1, 29, 0, 920, 756, 0}, :addr, 1, 4, 4, {1, 29, 0, 920, 785, 0}}
{{1, 30, 0, 920, 785, 0}, :mulr, 1, 4, 4, {1, 30, 0, 920, 23550, 0}}
{{1, 31, 0, 920, 23550, 0}, :muli, 4, 14, 4, {1, 31, 0, 920, 329700, 0}}
{{1, 32, 0, 920, 329700, 0}, :mulr, 4, 1, 4, {1, 32, 0, 920, 10550400, 0}}
{{1, 33, 0, 920, 10550400, 0}, :addr, 3, 4, 3, {1, 33, 0, 10551320, 10550400, 0}}
{{1, 34, 0, 10551320, 10550400, 0}, :seti, 0, 0, 0, {0, 34, 0, 10551320, 10550400, 0}}
{{0, 35, 0, 10551320, 10550400, 0}, :seti, 0, 1, 1, {0, 0, 0, 10551320, 10550400, 0}}
{{0, 1, 0, 10551320, 10550400, 0}, :seti, 1, 4, 5, {0, 1, 0, 10551320, 10550400, 1}}
{{0, 2, 0, 10551320, 10550400, 1}, :seti, 1, 4, 2, {0, 2, 1, 10551320, 10550400, 1}}
{{0, 3, 1, 10551320, 10550400, 1}, :mulr, 5, 2, 4, {0, 3, 1, 10551320, 1, 1}}

My instruction point is in the 2nd register and I noticed that when it has value 1, it is when the loop starts, so I just need to get the number at position 4th in the registry and compute the sum of its divisors. So I added this instruction:

  # Specialized instruction for part 2.
  # The problem is basically computing the sum of all numbers in register 3.
  defp compute(_ip, _instructions, {_, 1, 0, number, _, _}) do
    Enum.sum(for i <- 1..number, rem(number, i) == 0, do: i)
  end

Both parts finish in 0.6 seconds. This is by far the puzzle that took me the longest.

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

45986×1450 109 KB