{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 16 - Processor simulation\n",
    "\n",
    "- [Day 16](https://adventofcode.com/2018/day/16)\n",
    "\n",
    "The author of Advent of Code certainly likes their [machine code](https://en.wikipedia.org/wiki/Machine_code) challenges! Not only have we seen similar problems in previous years (last year had three!; days [8](../2017/Day%2008.ipynb), [18](../2017/Day%2018.ipynb) & [23](../2017/Day%2023.ipynb)), the author previously created the [Synacor challenge](https://challenge.synacor.com/), which requires you to write your own virtual CPU for the supplied machine code, first.\n",
    "\n",
    "But they do find novel puzzles each time! Here, we are only given the [assembly language](https://en.wikipedia.org/wiki/Assembly_language) description, and are asked to count the number of possible opcode instructions. The solution is simple; run the opcode through all possible instructions, see which ones produce the expected output.\n",
    "\n",
    "All operands can be implemented using the Python [`operator` module](https://docs.python.org/3/library/operator.html).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import operator\n",
    "import re\n",
    "from dataclasses import dataclass\n",
    "from typing import (\n",
    "    Callable,\n",
    "    Iterable,\n",
    "    Iterator,\n",
    "    List,\n",
    "    Mapping,\n",
    "    Sequence,\n",
    "    Tuple,\n",
    "    Type,\n",
    "    Union,\n",
    ")\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Opcode:\n",
    "    # An opcode function takes one or two integers as input\n",
    "    f: Union[Callable[[int, int], int], Callable[[int], int]]\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\"<opcode {self.opcode} {self.operands!r}>\"\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):\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):\n",
    "        return Opcode(f, operands)\n",
    "\n",
    "    return decorator\n",
    "\n",
    "\n",
    "class CPU:\n",
    "    registers: List[int]  # limited to 4\n",
    "    opcodes: Mapping[str, Opcode] = {}\n",
    "\n",
    "    def __init__(self):\n",
    "        self.registers = [0, 0, 0, 0]\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 test_instruction(\n",
    "        self, registers: List[int], instruction: Sequence[int], expected: List[int]\n",
    "    ) -> Iterator[Opcode]:\n",
    "        for opcode in self.opcodes.values():\n",
    "            self.registers[:] = registers\n",
    "            opcode(self, *instruction[1:])\n",
    "            if self.registers == expected:\n",
    "                yield opcode\n",
    "\n",
    "    def execute(self, instructions: Iterable[Sequence[int]]):\n",
    "        opcodes = self.opcodes\n",
    "        for op, operands in instructions:\n",
    "            opcodes[op](self, *operands)\n",
    "        return self.registers[0]\n",
    "\n",
    "\n",
    "def test_opcodes(samples: Iterable[Tuple[List[int], List[int], List[int]]]) -> int:\n",
    "    cpu = CPU()\n",
    "    return sum(1 for test in samples if sum(1 for _ in cpu.test_instruction(*test)) > 2)\n",
    "\n",
    "\n",
    "def parse_data(\n",
    "    data: str,\n",
    ") -> Tuple[Sequence[Tuple[List[int], List[int], List[int]]], Sequence[List[int]]]:\n",
    "    sample_lines, instruction_lines = map(str.splitlines, data.split(\"\\n\\n\\n\\n\"))\n",
    "    it = iter(sample_lines)\n",
    "    samples = []\n",
    "    for line in it:\n",
    "        if \"Before:\" in line:\n",
    "            registers = [int(r) for r in re.findall(r\"\\d+\", line)]\n",
    "            instruction = [int(i) for i in next(it).split()]\n",
    "            expected = [int(r) for r in re.findall(r\"\\d+\", next(it))]\n",
    "            samples.append((registers, instruction, expected))\n",
    "    return samples, [[int(i) for i in line.split()] for line in instruction_lines]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "test_samples = parse_data(\n",
    "    \"\"\"\\\n",
    "Before: [3, 2, 1, 1]\n",
    "9 2 1 2\n",
    "After:  [3, 2, 2, 1]\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"\n",
    ")[0]\n",
    "assert test_opcodes(test_samples) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "data = aocd.get_data(day=16, year=2018)\n",
    "samples, instructions = parse_data(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 605\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", test_opcodes(samples))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2, recover the instruction set\n",
    "\n",
    "Now we have to map machine code to the operator names, based on the samples. If you map the first value of each instruction to the opcode names that produce the correct output, we can see that one of those mappings has just one possible operator name. There is also a set with two names, one of which is the one named in the set with a single name.\n",
    "\n",
    "This gave me a hunch that we can simply eliminate mapped names from the possibities of as-yet-unresolved mappings, and by this process of elimination reconstruct the full instruction set.\n",
    "\n",
    "Executing the program is then super simple; just execute the machine code using or new-found mapping. That part is certainly going to be straightforward, as there are no jumps (so no loops) in this instruction set.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Set\n",
    "\n",
    "\n",
    "def determine_opcodes(\n",
    "    samples: Sequence[Tuple[List[int], List[int], List[int]]],\n",
    ") -> Mapping[int, opcode]:\n",
    "    cpu = CPU()\n",
    "    # we'll reduce this down per sample\n",
    "    possible_opcodes: Mapping[int, Set[str]] = {i: set() for i in range(16)}\n",
    "    for registers, instruction, expected in samples:\n",
    "        for opcode in cpu.test_instruction(registers, instruction, expected):\n",
    "            possible_opcodes[instruction[0]].add(opcode.opcode)\n",
    "\n",
    "    # iteratively determine what opcode goes where\n",
    "    opcode_map: Mapping[int, Opcode] = {}\n",
    "    assigned: Set[str] = set()\n",
    "    while len(opcode_map) < 16:\n",
    "        for op, opcodes in possible_opcodes.items():\n",
    "            opcodes.difference_update(assigned)\n",
    "            if len(opcodes) == 1:\n",
    "                opcode = opcode_map[op] = opcodes.pop()\n",
    "                assigned.add(opcode)\n",
    "\n",
    "    return opcode_map\n",
    "\n",
    "\n",
    "def execute_instructions(\n",
    "    samples: Sequence[Tuple[List[int], List[int], List[int]]],\n",
    "    instructions: Sequence[List[int]],\n",
    ") -> int:\n",
    "    opcode_map = determine_opcodes(samples)\n",
    "    cpu = CPU()\n",
    "    return cpu.execute((opcode_map[op], operands) for op, *operands in instructions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 653\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", execute_instructions(samples, instructions))"
   ]
  }
 ],
 "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
}