2020/Day 08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 8 - Simple instructions\n",
    "\n",
    "- https://adventofcode.com/2020/day/8\n",
    "\n",
    "We regularly are given a CPU opcode task, this year we are dealing with infinite loops! It starts simple, just execute and detect when we have jumped to a memory position we have visited before:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass\n",
    "from enum import Enum, auto\n",
    "from typing import Sequence\n",
    "\n",
    "\n",
    "class OpCode(Enum):\n",
    "    jmp = auto()\n",
    "    nop = auto()\n",
    "    acc = auto()\n",
    "\n",
    "\n",
    "@dataclass(frozen=True)\n",
    "class Instr:\n",
    "    opc: OpCode\n",
    "    arg: int\n",
    "\n",
    "    @classmethod\n",
    "    def from_line(cls, line: str) -> \"Instr\":\n",
    "        opc, arg = line.split(None, 1)\n",
    "        return cls(OpCode[opc], int(arg))\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"{self.opc.name} {self.arg:+d}\"\n",
    "\n",
    "\n",
    "class CPU:\n",
    "    acc: int\n",
    "    pos: int\n",
    "    mem: Sequence[Instr]\n",
    "    seen: set[int]\n",
    "\n",
    "    def __init__(self, mem: Sequence[Instr]) -> None:\n",
    "        self.acc = 0\n",
    "        self.pos = 0\n",
    "        self.mem = mem\n",
    "        self.seen = set()\n",
    "\n",
    "    def execute(self) -> int:\n",
    "        mem, seen = self.mem, self.seen\n",
    "        while self.pos not in seen and self.pos < len(mem):\n",
    "            seen.add(self.pos)\n",
    "            instr = mem[self.pos]\n",
    "            if instr.opc is OpCode.jmp:\n",
    "                self.pos += instr.arg\n",
    "                continue\n",
    "            if instr.opc is OpCode.acc:\n",
    "                self.acc += instr.arg\n",
    "            self.pos += 1\n",
    "        return self.acc\n",
    "\n",
    "\n",
    "def parse_assembly(lines: str) -> Sequence[Instr]:\n",
    "    return [Instr.from_line(line) for line in lines]\n",
    "\n",
    "\n",
    "test = parse_assembly(\n",
    "    \"\"\"\\\n",
    "nop +0\n",
    "acc +1\n",
    "jmp +4\n",
    "acc +3\n",
    "jmp -3\n",
    "acc -99\n",
    "acc +1\n",
    "jmp -4\n",
    "acc +6\n",
    "\"\"\".splitlines()\n",
    ")\n",
    "\n",
    "assert CPU(test).execute() == 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "instructions = parse_assembly(aocd.get_data(day=8, year=2020).splitlines())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 1614\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 1:\", CPU(instructions).execute())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    "Now it gets to be more tricky, but we only have to change a _single_ jump or no-op code. We also don't have to bother with several categories of changes:\n",
    "\n",
    "- `nop` instructions that, if changed to a jump, would put us anywhere we have already been, on _any_ run tested so far.\n",
    "- `nop` instructions that, if changed to a jump, would put us _outside_ of the program (except for the position right after)\n",
    "\n",
    "With only 222 jump instructions and 64 qualifying no-op instructions, I decided to go with a brute-force solution, and try out changing each nop or jmp encountered, in turn, then see if the program will complete.\n",
    "\n",
    "An alternative approach could be to generate a directed graph of all the jumps, and one of the no-ops-converted-to-jumps, and backtrack from the target position. While this too would require some brute-forcing of dropping one edge from the first graph or inserting one edge into the first from the second graph, the number of candidate options for this would be pruned more rapidly perhaps. However, I didn't think it was worth exploring this method.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def repair_program(instructions: Sequence[Instr]) -> int:\n",
    "    seen = set()\n",
    "    for pos, instr in enumerate(instructions):\n",
    "        if instr.opc is OpCode.acc:\n",
    "            continue\n",
    "        elif instr.opc is OpCode.nop:\n",
    "            target = instr.arg + pos\n",
    "            if (\n",
    "                0 <= instr.arg <= 1\n",
    "                or target in seen\n",
    "                or not 0 < target <= len(instructions)\n",
    "            ):\n",
    "                # would not jump, or jump to a position we've already seen or outside of the range\n",
    "                continue\n",
    "            alt = Instr(OpCode.jmp, instr.arg)\n",
    "        else:\n",
    "            alt = Instr(OpCode.nop, 0)\n",
    "        cpu = CPU([*instructions[:pos], alt, *instructions[pos + 1 :]])\n",
    "        result = cpu.execute()\n",
    "        if cpu.pos == len(instructions):\n",
    "            return result\n",
    "        # remember what positions we already visited, to prune\n",
    "        # the search tree a bit\n",
    "        seen |= cpu.seen\n",
    "\n",
    "\n",
    "assert repair_program(test) == 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 1260\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", repair_program(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"
  },
  "orig_nbformat": 2
 },
 "nbformat": 4,
 "nbformat_minor": 2
}