Advent of Code - Day 21

advent-of-code
#1

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

#2

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

#3

@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

#4

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. :frowning:

3 Likes

#5

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.

0 Likes

#6

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