{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Day 19 - Back to that CPU\n", "\n", "- [Day 19](https://adventofcode.com/2018/day/19)\n", "\n", "We return to the CPU from [day 16](./Day%2016.ipynb); I remarked then (in my part 2 notes) that executing instructions was _certainly going to be straightforward, as there are no jumps (so no loops) in this instruction set._ Now we have jumps!\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import operator\n", "from dataclasses import dataclass\n", "from functools import partial\n", "from typing import Callable, Iterable, List, Mapping, Sequence, Tuple, Type, Union\n", "\n", "Instruction = Tuple[str, int, int, int]\n", "OpcodeFunction = Union[Callable[[int, int], int], Callable[[int], int]]\n", "\n", "\n", "@dataclass\n", "class Opcode:\n", " # An opcode function takes one or two integers as input\n", " f: OpcodeFunction\n", " operands: str # 1 or 2 characters, i and r\n", " opcode: str = \"\"\n", "\n", " def __set_name__(self, owner: Type[\"CPU\"], name: str) -> None:\n", " self.opcode = name[3:]\n", " owner.opcodes[self.opcode] = self\n", "\n", " def __repr__(self) -> str:\n", " return f\"\"\n", "\n", " def __get__(\n", " self, instance: \"CPU\", owner: Type[\"CPU\"]\n", " ) -> Callable[[int, int, int], None]:\n", " return partial(self.__call__, instance)\n", "\n", " def __call__(self, cpu: \"CPU\", *ops: int) -> None:\n", " # operand C receives the output\n", " *ops, op_c = ops\n", " # map the oter operands to values\n", " value = {\"r\": cpu.registers.__getitem__, \"i\": operator.pos}\n", " ops = (value[t](op) for t, op in zip(self.operands, ops))\n", " # execute the operand, store the integer result in the register\n", " # designated by C. Int is used to convert bool results to 0 or 1\n", " cpu.registers[op_c] = int(self.f(*ops))\n", "\n", "\n", "def opcode(operands: str) -> Callable[[OpcodeFunction], Opcode]:\n", " \"\"\"Operator operates on 1 or 2 operands\n", "\n", " Specify the operands as 'r' or 'i' for registers and immediate values.\n", " \"\"\"\n", "\n", " def decorator(f: OpcodeFunction) -> Opcode:\n", " return Opcode(f, operands)\n", "\n", " return decorator\n", "\n", "\n", "class CPU:\n", " registers: List[int] # limited to 6\n", " opcodes: Mapping[str, Opcode] = {}\n", "\n", " def __init__(self) -> None:\n", " self.registers = [0, 0, 0, 0, 0, 0]\n", " self.bound: Mapping[str, Callable[[int, int, int], None]] = {\n", " name: opcode.__get__(self, None) for name, opcode in CPU.opcodes.items()\n", " }\n", "\n", " # Addition\n", " # addr (add register) stores into register C the result of adding register\n", " # A and register B.\n", " op_addr = opcode(\"rr\")(operator.add)\n", " # addi (add immediate) stores into register C the result of adding\n", " # register A and value B.\n", " op_addi = opcode(\"ri\")(operator.add)\n", "\n", " # Multiplication:\n", " # mulr (multiply register) stores into register C the result of\n", " # multiplying register A and register B.\n", " op_mulr = opcode(\"rr\")(operator.mul)\n", " # muli (multiply immediate) stores into register C the result of\n", " # multiplying register A and value B.\n", " op_muli = opcode(\"ri\")(operator.mul)\n", "\n", " # Bitwise AND:\n", " # banr (bitwise AND register) stores into register C the result of the\n", " # bitwise AND of register A and register B.\n", " op_banr = opcode(\"rr\")(operator.and_)\n", " # bani (bitwise AND immediate) stores into register C the result of the\n", " # bitwise AND of register A and value B.\n", " op_bani = opcode(\"ri\")(operator.and_)\n", "\n", " # Bitwise OR:\n", " # borr (bitwise OR register) stores into register C the result of the\n", " # bitwise OR of register A and register B.\n", " op_borr = opcode(\"rr\")(operator.or_)\n", " # bori (bitwise OR immediate) stores into register C the result of the\n", " # bitwise OR of register A and value B.\n", " op_bori = opcode(\"ri\")(operator.or_)\n", "\n", " # Assignment:\n", " # setr (set register) copies the contents of register A into register C.\n", " # (Input B is ignored.)\n", " op_setr = opcode(\"r\")(operator.pos) # pos is the identity function for int\n", " # seti (set immediate) stores value A into register C. (Input B is\n", " # ignored.)\n", " op_seti = opcode(\"i\")(operator.pos) # pos is the identity function for int\n", "\n", " # Greater-than testing:\n", " # gtir (greater-than immediate/register) sets register C to 1 if value A\n", " # is greater than register B. Otherwise, register C is set to 0.\n", " op_gtir = opcode(\"ir\")(operator.gt)\n", " # gtri (greater-than register/immediate) sets register C to 1 if register\n", " # A is greater than value B. Otherwise, register C is set to 0.\n", " op_gtri = opcode(\"ri\")(operator.gt)\n", " # gtrr (greater-than register/register) sets register C to 1 if register A\n", " # is greater than register B. Otherwise, register C is set to 0.\n", " op_gtrr = opcode(\"rr\")(operator.gt)\n", "\n", " # Equality testing:\n", " # eqir (equal immediate/register) sets register C to 1 if value A is equal\n", " # to register B. Otherwise, register C is set to 0.\n", " op_eqir = opcode(\"ir\")(operator.eq)\n", " # eqri (equal register/immediate) sets register C to 1 if register A is\n", " # equal to value B. Otherwise, register C is set to 0.\n", " op_eqri = opcode(\"ri\")(operator.eq)\n", " # eqrr (equal register/register) sets register C to 1 if register A is\n", " # equal to register B. Otherwise, register C is set to 0.\n", " op_eqrr = opcode(\"rr\")(operator.eq)\n", "\n", " def execute(self, ipregister: int, instructions: Sequence[Instruction]) -> int:\n", " opcodes = self.bound\n", " r = self.registers\n", " while 0 <= r[ipregister] < len(instructions):\n", " op, *operands = instructions[r[ipregister]]\n", " opcodes[op](*operands)\n", " r[ipregister] += 1\n", " return self.registers[0]\n", "\n", "\n", "def parse_instructions(lines: Iterable[str]) -> Tuple[int, Sequence[Instruction]]:\n", " it = iter(lines)\n", " ipregister = int(next(it).rpartition(\" \")[-1])\n", " instructions = []\n", " for line in it:\n", " opcode, *operands = line.split()\n", " instructions.append((opcode, *map(int, operands)))\n", " return ipregister, instructions" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "testprogram = parse_instructions(\n", " \"\"\"\\\n", "#ip 0\n", "seti 5 0 1\n", "seti 6 0 2\n", "addi 0 1 0\n", "addr 1 2 3\n", "setr 1 0 0\n", "seti 8 0 4\n", "seti 9 0 5\"\"\".splitlines()\n", ")\n", "assert CPU().execute(*testprogram) == 7" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "import aocd\n", "\n", "data = aocd.get_data(day=19, year=2018)\n", "ipregister, instructions = parse_instructions(data.splitlines())" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 1: 912\n" ] } ], "source": [ "print(\"Part 1:\", CPU().execute(ipregister, instructions))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 2, analysis\n", "\n", "The puzzle is specifically crafted to take a very, very long time once you set register 0 to 1. We need to find a shortcut. The machine code given isn't very long, we need to analyse it a little to see what it does and were we can cut a corner.\n", "\n", "Looking over my puzzle input, I annotated the instructions with my interpretation; my IP is register #4. 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%2019.ipynb) instead to see my colour annotations and have label links work:\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \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
0addi4164jmp 17 (SETUP)
MAIN1seti12r2 = 1
LOOP12seti15r5 = 1
LOOP23mulr253\n", " 
if (r2 * r5) == r1:\n",
    "    r0 += r2
\n", "
4eqrr313
5addr344
6addi414
7addr200
8addi515r5 += 1
9gtrr513\n", " 
if r5 <= r1:\n",
    "    jmp 3 (LOOP2)
\n", "
10addr434
11seti24
12addi212r2 += 1
13gtrr213\n", " 
if r2 <= r1:\n",
    "    jmp 2 (LOOP1)
14addr344
15seti14
16mulr444HALT
SETUP17addi121\n", " r1 = 911\n", "

\n", " simplified from
\n", " 

r1 = 2 ** 2 * 19 * 11 = 836\n",
    "r3 = 3 * 22 + 9 = 75\n",
    "r1 += r3
\n", " \n", "

\n", "
18mulr111
19mulr411
20muli1111
21addi333
22mulr343
23addi393
24addr131
25addr404\n", " 
if r0 == 0:\n",
    "    jmp 1 (MAIN)
26seti04
PART227setr43\n", " r1 = 10551311\n", "

\n", " simplified from\n", " 

r3 = (27 * 28 + 29) * 30 * 14 * 32 = 10550400\n",
    "r1 += r3
\n", " \n", "

\n", "
28mulr343
29addr433
30mulr433
31muli3143
32mulr343
33addr131
34seti00r0 = 0
35seti04jmp 36 (MAIN)
\n", "\n", "The above can be condensed into the following Python code:\n", "\n", "```python\n", "v = 911 if part1 else 10551311\n", "result = 0\n", "for i in range(1, v + 1):\n", " for j in range(1, v + 1):\n", " if i * j == v:\n", " result += i\n", "```\n", "\n", "So we are basically finding the sum of the divisors of the given number. For 911, a prime number, that's just 911 itself and 1, and so the answer is 912.\n", "\n", "For part 2 the number becomes a lot, lot larger, so lets not bother with our CPU at all and just calculate the number using Python. Not with the above code, of course; we don't need a double loop here!\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "from itertools import chain\n", "\n", "\n", "def sum_factors(n):\n", " return sum(\n", " set(\n", " chain.from_iterable(\n", " (i, n // i) for i in range(1, int(n**0.5) + 1) if not n % i\n", " )\n", " )\n", " )\n", "\n", "\n", "assert sum_factors(911) == 912" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 2: 10576224\n" ] } ], "source": [ "print(\"Part 2:\", sum_factors(10551311))" ] } ], "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 }