Note: This topic is to talk about Day 21 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
I’ve spent some embarassing amount of time before I figured out how to solve today’s puzzle. In the end the solution is fairly simple.
Similar to day 19, here we have to reverse engineer the code first. In my particular input, if at instruction 28 r0 == r1, the program halts. The r0 register is not used anywhere else. Therefore, the solution for part 1 is to simply loop through all the states until reach the instruction 28. The value of r1 at this point is the result of the first part.
The key insight for the second part is the fact that the program loops forever. This is mentioned in the text (it appears to run forever without halting), which means there is a cycle.
My approach was then to find the finite amount of the states at instruction 28. Basically, the first time I see the duplicate occurence of the register values at the state 28, I conclude that it’s a cycle. So at this point, I know all the possible inputs which will cause the program to halt. I compute the result by deduping the inputs and taking the last value. Deduping is needed to properly resolve the situation of [input_1, input_2, input_1], where the input_2 is the solution, but input_1 is the last encountered value before the cycle.
Since my emulator is not super fast, I also inlined the inner loop of my input program (i.e. implemented it in Elixir).
I also extracted the device code into a separate module and refactored the solution for the day 19 to use it too. My solution for today is then reasonably short, and it computes the result in about 1 sec.
3 Likes
@sasajuric My experience is similar to yours and I ended up with a similar solution.
I first spent some time improving the pretty-printer of the input program to make it easier to understand what it does. Here is pretty-printed program, with some extra blank lines inserted by me.
With a nice program listing and some output from tracing, I then figured out that the answer could be found in register 5 at address 28. I could read out the answer for part one directly from the trace output.
After some thinking about part 2, I installed a breakpoint handler at adress 28 that kept track of the last result and all previously seen results. When a value was seen again, the breakpoint handler halted the program by setting IP to a high value.
As expected, the program executed far too slowly, so I then installed a breakpoint at adress 17 to optimize the inner loop.
Now it finished in well under a second. Here is my solution.
3 Likes
I solved it in a very similar fashion as 19. I detected whenever the loop started and then I jumped to the end of the loop:
defp compute(1, instructions, {0, 18, _, 0, r4, r5}) do
r2 = div(r5, 256)
r3 = r2 + 1
compute(1, instructions, {0, 19, r2, r3, r4, r5})
end
Then every time we reached instruction 28, I stored the value we were supposed to compare against, and continued as usual. Once the value to be compared on instruction 28 repeats, the previous value is the solution.
This is the first time I actually did not enjoy the puzzle. There was basically no coding and mostly debugging. 
3 Likes
Yeah, I didn’t really like this one myself. I found some solace by refactoring the common stuff from both parts, and then also extracting the device code into a separate module and reusing the code for day 19.
Same here. I did some coding so that my decompiler from Day 19 would recognize if-then-else statements so I ended up with this:
0: B = 123 seti 123 0 1
1: B = B & 456 bani 1 456 1
2: IF (B == 72) [B] eqri 1 72 1
3: THEN GOTO 5 ELSE GOTO 4 addr 1 3 3
4: GOTO 1 seti 0 0 3
5: B = 0 seti 0 7 1
6: E = B | 65536 bori 1 65536 4
7: B = 3798839 seti 3798839 3 1
8: F = E & 255 bani 4 255 5
9: B = B + F addr 1 5 1
10: B = B & 16777215 bani 1 16777215 1
11: B = B * 65899 muli 1 65899 1
12: B = B & 16777215 bani 1 16777215 1
13: IF (256 > E) [F] gtir 256 4 5
14: THEN GOTO 16 ELSE GOTO 15 addr 5 3 3
15: GOTO 17 addi 3 1 3
16: GOTO 28 seti 27 6 3
17: F = 0 seti 0 2 5
18: C = F + 1 addi 5 1 2
19: C = C * 256 muli 2 256 2
20: IF (C > E) [C] gtrr 2 4 2
21: THEN GOTO 23 ELSE GOTO 22 addr 2 3 3
22: GOTO 24 addi 3 1 3
23: GOTO 26 seti 25 3 3
24: F = F + 1 addi 5 1 5
25: GOTO 18 seti 17 1 3
26: E = F setr 5 6 4
27: GOTO 8 seti 7 8 3
28: IF (B == A) [F] eqrr 1 0 5
29: THEN GOTO 31 ELSE GOTO 30 addr 5 3 3
30: GOTO 6 seti 5 6 3
It looked promising when I figured out that code starting from line 17 calculates div(e, 256). That made me think that the intention is really e >>> 8 and there’s something about bitwise operations. I’ve decompiled the program manually into:
CHECK_BINARY_OPS()
B = 0
E = B | 1_0000_0000_0000_0000_b
B = 0011_1001_1111_0111_0011_0111_b
WHILE TRUE:
B = CALC_B(B, E & 255)
IF (E <= 1111_1111_b) AND (B == A):
RETURN
IF (E <= 1111_1111_b):
E = B | 1_0000_0000_0000_0000_b
B = 0011_1001_1111_0111_0011_0111_b
ELSE:
E = E >> 8
CALC_B(B, X):
B = B + X
B = B & 1111_1111_1111_1111_1111_1111_b
B = B * 65899
B = B & 1111_1111_1111_1111_1111_1111_b
RETURN B
CHECK_BINARY_OPS():
B = 123
WHILE TRUE:
B = B & 456
IF B == 72:
BREAK
But it seems like there’s no actual meaning to the program. So I rewrote this to Elixir and went the same path as @sasajuric to find a cycle. Streams were perfect here:
import Bitwise
def mystery_function({b, e, _}) do
b = calc_b(b, band(e, 255))
if e < 256 do
{3798839, bor(b, 65536), b}
else
{b, e >>> 8, :cont}
end
end
defp calc_b(b, x) do
b = b + x
b = band(b, 16777215)
b = b * 65899
b = band(b, 16777215)
b
end
def part2() do
# Run the program and keep all values that are checked in the halting
# condition. The value that we're looking for is the last one before
# they start repeating.
{3798839, 65536, :cont}
|> Stream.unfold(fn state -> {state, mystery_function(state)} end)
|> Stream.filter(fn {_, _, value} -> value != :cont end)
|> Stream.map(fn {_, _, value} -> value end)
|> Enum.reduce_while([], fn x, seen ->
if x in seen do
{:halt, hd(seen)}
else
{:cont, [x | seen]}
end
end)
end
1 Like
