{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class Jump(Exception):\n", " def __init__(self, offset):\n", " self.offset = offset\n", " super().__init__(offset)\n", "\n", "\n", "def opcode(operands):\n", " def decorator(f):\n", " class Opcode:\n", " def __set_name__(self, owner, name):\n", " self.opcode = name[3:]\n", " owner.opcodes[self.opcode] = self\n", "\n", " def __repr__(self):\n", " return f\"\"\n", "\n", " def value(self, operand, type_):\n", " if type_ == \"r\":\n", " return operand\n", " try:\n", " return int(operand)\n", " except ValueError:\n", " return self.registers[operand]\n", "\n", " def __call__(self, cpu, *ops):\n", " self.registers = cpu.registers\n", " try:\n", " f(cpu, *map(self.value, ops, operands))\n", " cpu.pos += 1\n", " except Jump as j:\n", " cpu.pos += j.offset\n", " return self.opcode\n", "\n", " return Opcode()\n", "\n", " return decorator\n", "\n", "\n", "class Proc:\n", " opcodes = {}\n", "\n", " def __init__(self, debug=True):\n", " self.reset(debug)\n", "\n", " def reset(self, debug=True):\n", " self.registers = dict.fromkeys(\"abcdefgh\", 0)\n", " self.debug = debug\n", " if not debug:\n", " self.registers[\"a\"] = 1\n", " self.pos = 0\n", "\n", " def run(self, instructions):\n", " if not self.debug:\n", " instructions = self.optimise(instructions)\n", " while 0 <= self.pos < len(instructions):\n", " opcode, *ops = instructions[self.pos]\n", " yield self.opcodes[opcode](self, *ops)\n", "\n", " @opcode(\"\")\n", " def op_nop(self):\n", " pass\n", "\n", " @opcode(\"rv\")\n", " def op_set(self, x, y):\n", " self.registers[x] = y\n", "\n", " @opcode(\"rv\")\n", " def op_sub(self, x, y):\n", " self.registers[x] -= y\n", "\n", " @opcode(\"rv\")\n", " def op_mul(self, x, y):\n", " self.registers[x] *= y\n", "\n", " @opcode(\"rv\")\n", " def op_mod(self, x, y):\n", " self.registers[x] %= y\n", "\n", " @opcode(\"vv\")\n", " def op_jnz(self, x, y):\n", " if x:\n", " raise Jump(y)\n", "\n", " def optimise(self, instructions):\n", " # modulus operation over two registers, setting a third flag register\n", " # using two working registers. If the flag register\n", " # is set, jump out of the outer loop\n", " operand1, operand2 = instructions[13][2], instructions[11][2]\n", " workreg = instructions[11][1]\n", " flagreg = instructions[15][1]\n", " return (\n", " instructions[:10]\n", " + [\n", " (\"set\", workreg, operand1),\n", " (\"mod\", workreg, operand2),\n", " (\"jnz\", workreg, \"8\"),\n", " (\"set\", flagreg, \"0\"),\n", " (\"jnz\", \"1\", \"11\"),\n", " (\"jnz\", \"1\", \"5\"),\n", " ]\n", " + [(\"nop\",)] * 4\n", " + instructions[20:]\n", " )" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import aocd\n", "\n", "data = aocd.get_data(day=23, year=2017)\n", "instructions = [line.split() for line in data.splitlines()]" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 1: 9409\n" ] } ], "source": [ "proc = Proc()\n", "print(\"Part 1:\", sum(1 for opcode in proc.run(instructions) if opcode == \"mul\"))" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Part 2: 913\n" ] } ], "source": [ "from collections import deque\n", "\n", "proc = Proc(debug=False)\n", "deque(proc.run(instructions), 0)\n", "print(\"Part 2:\", proc.registers[\"h\"])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Optimisations\n", "\n", "The following set of instructions is basically setting `f` to `0` (true) if `b % d == 0` is true, using `g` as the stack for operands, using multiplication with e, incrementing in single steps:\n", "\n", " 0. set e 2 > for e in range(2, b):\n", " 1. set g d v\n", " 2. mul g e v\n", " 3. sub g b v\n", " 4. jnz g 2 > if d * e == b:\n", " 5. set f 0 > f = 0\n", " 6. sub e -1 0\n", " 7. set g e 0\n", " 8. sub g b 0\n", " 9. jnz g -8 0\n", "\n", "We can replace those 10 with a simple `mod` operand instead, filling out the rest with `nop` codes:\n", "\n", " 0. set g b v\n", " 1. mod g d v\n", " 2. jnz g 8 > if b % d == 0:\n", " 3. set f 0 > f = 0\n", " 4. jnz 1 6 > skip the remaining nops\n", " 5-9 nop\n", "\n", "Next, the outer loop is inefficient; it keeps on looping while only the first `f == 0` setting is important:\n", "\n", " -2. set f 1 > f = 1\n", " -1. set d 2 > for d in range(2, b):\n", " ... the inner loop above, so repeated b - 1 times\n", " 10. sub d -1 1\n", " 11. set g d 1\n", " 12. sub g b 1\n", " 13. jnz g -13 1\n", " 14. jnz f 2 > if not f:\n", " 15. sub h -1 > h += 1\n", "\n", "That outer loop can be jumped out of when we set f = 0, so in the inner loop, after `set f 0`, we can add a jump to the `h += 1` instruction, stepping out of the outer loop:\n", "\n", " 0. set g b v\n", " 1. mod g d v\n", " 2. jnz g 8 > if b % d == 0:\n", " 3. set f 0 > f = 0\n", " 4. jnz 1 11 > break (and skip the if not f test)\n", " 5. jnz 1 5 > skip the remaining nops\n", " 6-9 nop\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "913\n" ] } ], "source": [ "# Cheating option, just run Python code\n", "lower = (99 * 100) + 100000\n", "upper = lower + 17000\n", "h = 0\n", "for b in range(lower, upper + 1, 17):\n", " f = 1\n", " for d in range(2, b):\n", " if b % d == 0:\n", " f = 0\n", " break\n", " if not f:\n", " h += 1\n", "print(h)" ] } ], "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 }