Continuing the theme from days 16 and 19, 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 instead.
My input marks register #1 as the IP:
label | i | opcode | op1 | op2 | reg | interpretation |
---|---|---|---|---|---|---|
0 | seti | 123 | 5 | r5 = 123 |
||
ANDTEST | 1 | bani | 5 | 456 | 5 | r5 &= 456 |
2 | eqri | 5 | 72 | 5 |
|
|
3 | addr | 5 | 1 | 1 | ||
4 | seti | 0 | 1 | |||
5 | seti | 0 | 5 | r5 = 0 |
||
OUTER | 6 | bori | 5 | 65536 | 4 | r4 = r5 | 65536 (sets bit 17, 0x10000 |
7 | seti | 13431073 | 5 | r5 = 13431073 (product of 2 primes) |
||
INNER | 8 | bani | 4 | 255 | 3 | r5 += r4 & 255 (bottom byte of r4 added to r5) |
9 | addr | 5 | 3 | 5 | ||
10 | bani | 5 | 16777215 | 5 | r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF ) |
|
11 | multi | 5 | 65899 | 5 | r5 *= 65899 (another prime) |
|
12 | bani | 5 | 16777215 | 5 | r5 &= 16777215 (masking r5 to 24 bits, 0xFFFFFF ) |
|
13 | gtir | 256 | 4 | 3 |
|
|
14 | addr | 3 | 1 | 1 | ||
15 | addr | 1 | 1 | 1 | ||
16 | seti | 27 | 1 | |||
17 | seti | 0 | 3 | r3 = 0 |
||
DIV256 | 18 | addi | 3 | 1 | 2 | r2 = r3 + 1 |
19 | muli | 2 | 256 | 2 | r2 *= 256 |
|
20 | gtrr | 2 | 4 | 2 |
|
|
21 | addr | 2 | 1 | 1 | ||
22 | addi | 1 | 1 | 1 | ||
23 | seti | 25 | 1 | |||
24 | addi | 3 | 1 | 3 | r3 += 1 |
|
25 | seti | 17 | 1 | jmp 18 (DIV256) |
||
DONEDIV | 26 | setr | 3 | 4 | r4 = r3 |
|
27 | seti | 7 | 1 | jmp 8 (INNER) |
||
BREAK | 28 | eqrr | 5 | 0 | 3 |
|
29 | addr | 3 | 1 | 1 | ||
30 | seti | 5 | 0 | 1 |
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:
# 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.
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
print("Part 1:", loop())
Part 1: 3115806
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.
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))
Part 2: 13959373