Note: This topic is to talk about Day 19 of the Advent of Code.
For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.
1 Like
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.
4 Likes
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.
2 Likes
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.
2 Likes
I actually wrote a decompiler/debugger in Elixir to poke with the program. It was sooo much fun!
With the tool at hand, after a few initial steps in which the program initializes the register 5 with a big number, I could run “seti 10 0 5” while the program was running. After that it was quite easy to trace what the program is computing.
4 Likes
