{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Day 21 - More machine code analysis\n", "\n", "- [Day 21](https://adventofcode.com/2018/day/21)\n", "\n", "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.\n", "\n", "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.\n", "\n", "My input marks register #1 as the IP:\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
labeliopcodeop1op2reginterpretation
0seti1235r5 = 123
ANDTEST1bani54565r5 &= 456
2eqri5725\n", " 
if r5 != 72:\n",
    "    jmp 1 (ANDTEST)
\n", "
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\n", " 
if r4 < 256:\n",
    "    jmp 28 (BREAK)
14addr311
15addr111
16seti271
17seti03r3 = 0
DIV25618addi312r2 = r3 + 1
19muli22562r2 *= 256
20gtrr242\n", " 
if r2 > r4:\n",
    "    jmp 26 (DONEDIV)
21addr211
22addi111
23seti251
24addi313r3 += 1
25seti171jmp 18 (DIV256)
DONEDIV26setr34r4 = r3
27seti71jmp 8 (INNER)
BREAK28eqrr503\n", " 
if r5 != r0:\n",
    "    jmp 6 (OUTER)
29addr311
30seti501
\n", "\n", "The `DIV256` loop effectively divides `r4` by 256, the same thing as shifting the register to the right by 8 bits.\n", "\n", "Converted to Python code, the above becomes:\n", "\n", "```python\n", "# ANDTEST\n", "while True:\n", " r5 = 123\n", " r5 &= 456\n", " if r5 == 72:\n", " break\n", "\n", "r5 = 0\n", "# OUTER\n", "while True:\n", " r4 = r5 | 0x10000 # sets bit 17\n", " r5 = 13431073 # a 24-bit value, product of 2 primes, 647 and 20759\n", "\n", " # INNER\n", " while r4:\n", " r5 += r4 & 0xFF\n", " r5 &= 0xFFFFFF # 24 bit mask\n", " r5 *= 65899 # another prime\n", " r5 &= 0xFFFFFF # 24 bit mask\n", " r4 >>= 8 # the DIV256 as a right-shift operation\n", "\n", " if r5 == r0:\n", " break\n", "```\n", "\n", "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.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "def loop(input: int = 0, init: int = 13431073, perturb: int = 65899):\n", " # init is the product of 2 primes, 647 and 20759\n", " # perturb is another prime\n", " bytes = input | 0x10000 # sets bit 33\n", " hash = init\n", " while bytes:\n", " hash += bytes & 0xFF\n", " hash &= 0xFFFFFF\n", " hash *= perturb\n", " hash &= 0xFFFFFF\n", " bytes >>= 8\n", " return hash" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 1: 3115806\n" ] } ], "source": [ "print(\"Part 1:\", loop())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 2\n", "\n", "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.\n", "\n", "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.\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 2: 13959373\n" ] } ], "source": [ "i = 0\n", "count = 0\n", "counts = {}\n", "while True:\n", " count += (i << 8) + (i << 16) # two >>= 8 loops\n", " i = loop(i)\n", " if i in counts:\n", " break\n", " counts[i] = count\n", "\n", "print(\"Part 2:\", max(counts, key=counts.get))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.0" } }, "nbformat": 4, "nbformat_minor": 2 }