#!/usr/bin/env python # coding: utf-8 # # Day 21 - More machine code analysis # # - [Day 21](https://adventofcode.com/2018/day/21) # # Continuing the theme from days [16](./Day%2016.ipynb) and [19](Day%2019.ipynb), we are explicitly asked to figure out how the new program works. # # Here's my take on the input I was given. The table is annotated with colours, If you are looking at this notebook on Github, you may want to [switch to the Jupyter notebook viewer](https://nbviewer.jupyter.org/github/mjpieters/adventofcode/blob/master/2018/Day%2021.ipynb) instead. # # My input marks register #1 as the IP: # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
labeliopcodeop1op2reginterpretation
0seti1235r5 = 123
ANDTEST1bani54565r5 &= 456
2eqri5725 # 
if r5 != 72:
#     jmp 1 (ANDTEST)
#
3addr511
4seti01
5seti05r5 = 0
OUTER6bori5655364r4 = r5 | 65536 (sets bit 17, 0x10000
7seti134310735r5 = 13431073 (product of 2 primes)
INNER8bani42553r5 += r4 & 255(bottom byte of r4 added to r5)
9addr535
10bani5167772155r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF)
11multi5658995r5 *= 65899 (another prime)
12bani5167772155r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF)
13gtir25643 # 
if r4 < 256:
#     jmp 28 (BREAK)
14addr311
15addr111
16seti271
17seti03r3 = 0
DIV25618addi312r2 = r3 + 1
19muli22562r2 *= 256
20gtrr242 # 
if r2 > r4:
#     jmp 26 (DONEDIV)
21addr211
22addi111
23seti251
24addi313r3 += 1
25seti171jmp 18 (DIV256)
DONEDIV26setr34r4 = r3
27seti71jmp 8 (INNER)
BREAK28eqrr503 # 
if r5 != r0:
#     jmp 6 (OUTER)
29addr311
30seti501
# # The `DIV256` loop effectively divides `r4` by 256, the same thing as shifting the register to the right by 8 bits. # # Converted to Python code, the above becomes: # # ```python # # ANDTEST # while True: # r5 = 123 # r5 &= 456 # if r5 == 72: # break # # r5 = 0 # # OUTER # while True: # r4 = r5 | 0x10000 # sets bit 17 # r5 = 13431073 # a 24-bit value, product of 2 primes, 647 and 20759 # # # INNER # while r4: # r5 += r4 & 0xFF # r5 &= 0xFFFFFF # 24 bit mask # r5 *= 65899 # another prime # r5 &= 0xFFFFFF # 24 bit mask # r4 >>= 8 # the DIV256 as a right-shift operation # # if r5 == r0: # break # ``` # # If we ignore the `ANDTEST` portion (Python is strictly typed, there are no string-as-numbers issues that the test guards against), then to solve Part 1 all we need to do is set register 0 to the outcome of the `OUTER` loop run once. # # In[1]: def loop(input: int = 0, init: int = 13431073, perturb: int = 65899): # init is the product of 2 primes, 647 and 20759 # perturb is another prime bytes = input | 0x10000 # sets bit 33 hash = init while bytes: hash += bytes & 0xFF hash &= 0xFFFFFF hash *= perturb hash &= 0xFFFFFF bytes >>= 8 return hash # In[2]: print("Part 1:", loop()) # ## Part 2 # # Now we need to repeatedly execute the loop until we see the value of r5 repeat, tracking how many operations have been executed for each loop operation. # # We don't need an exact operation count however, we just need to count how many times the variable part, the `DIV256` loop, runs. That loop is run twice, where it counts up to `r4` divided by 256, so `r4 // 256` iterations. # # In[3]: i = 0 count = 0 counts = {} while True: count += (i << 8) + (i << 16) # two >>= 8 loops i = loop(i) if i in counts: break counts[i] = count print("Part 2:", max(counts, key=counts.get))