day19.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "day1.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "metadata": {
        "id": "TZ5O20obUjg0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "##  🍫 [Day 19](https://adventofcode.com/2018/day/19)"
      ]
    },
    {
      "metadata": {
        "id": "Mk1gkvnlUhYu",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from functools import partial\n",
        "\n",
        "\"\"\"Defines all instructions (Reusing Day 16 code)\"\"\"\n",
        "def apply_add(a, b, c, before, register=0):\n",
        "  before[c] = before[a] + (before[b] if register else b)\n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_mul(a, b, c, before, register=0):\n",
        "  before[c] = before[a] * (before[b] if register else b)\n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_ban(a, b, c, before, register=0):\n",
        "  before[c] = before[a] & (before[b] if register else b)\n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_bor(a, b, c, before, register=0):\n",
        "  before[c] = before[a] | (before[b] if register else b)\n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_set(a, b, c, before, register=0):\n",
        "  before[c] = before[a] if register else a\n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_gt(a, b, c, before, register=0):\n",
        "  if register == 0:\n",
        "    before[c] = a > before[b]\n",
        "  elif register == 1:\n",
        "    before[c] = before[a] > b\n",
        "  else:\n",
        "    before[c] = before[a] > before[b]    \n",
        "  return before\n",
        "\n",
        "\n",
        "def apply_eq(a, b, c, before, register=0):\n",
        "  if register == 0:\n",
        "    before[c] = a == before[b]\n",
        "  elif register == 1:\n",
        "    before[c] = before[a] == b\n",
        "  else:\n",
        "    before[c] = before[a] == before[b]    \n",
        "  return before\n",
        "\n",
        "\n",
        "\"\"\"Gather all instructions\"\"\"\n",
        "operations = {'addr': partial(apply_add, register=1),\n",
        "              'addi': partial(apply_add, register=0),\n",
        "              'mulr': partial(apply_mul, register=1), \n",
        "              'muli': partial(apply_mul, register=0),\n",
        "              'banr': partial(apply_ban, register=1), \n",
        "              'bani': partial(apply_ban, register=0),\n",
        "              'borr': partial(apply_bor, register=1), \n",
        "              'bori': partial(apply_bor, register=0),\n",
        "              'setr': partial(apply_set, register=1), \n",
        "              'seti': partial(apply_set, register=0),\n",
        "              'gtir': partial(apply_gt, register=0), \n",
        "              'gtri': partial(apply_gt, register=1),\n",
        "              'gtrr': partial(apply_gt, register=2),\n",
        "              'eqir': partial(apply_eq, register=0), \n",
        "              'eqri': partial(apply_eq, register=1),\n",
        "              'eqrr': partial(apply_eq, register=2)}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "axCn6FNaUql6",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def run_programm(inputs, init_registers=None, verbose=False):\n",
        "  \"\"\"Run the background program\"\"\"\n",
        "  registers = [0] * 6\n",
        "  if init_registers is not None:\n",
        "    registers = init_registers\n",
        "  inst_register = inputs[0][1]\n",
        "  instructions = inputs[1:]\n",
        "  step = 0\n",
        "  while 1:\n",
        "    op, a, b, c = instructions[registers[inst_register]]\n",
        "    operations[op](a, b, c, registers)\n",
        "    if registers[inst_register] >= len(instructions) - 1:\n",
        "      break\n",
        "    registers[inst_register] += 1\n",
        "    if verbose:\n",
        "      print('Step %d' % (step + 1), op, a, b, c, '-->', registers)\n",
        "      step += 1\n",
        "  return registers"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "LqXBEfRttpFF",
        "colab_type": "code",
        "outputId": "70281d03-e7a7-4a86-b3a8-76c83722015a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        }
      },
      "cell_type": "code",
      "source": [
        "%%time\n",
        "with open(\"day19.txt\", 'r') as f:  \n",
        "  inputs = f.read().splitlines()\n",
        "  for i, line in enumerate(inputs):\n",
        "    if line.startswith('#'):\n",
        "      inputs[i] = ('inst', int(line[-1]), 0, 0)\n",
        "    else:\n",
        "      aux = line.split()\n",
        "      inputs[i] = (aux[0], int(aux[1]), int(aux[2]), int(aux[3]))\n",
        "      \n",
        "print('Final value of register 0:', run_programm(inputs)[0])"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Final value of register 0: 1140\n",
            "CPU times: user 5.72 s, sys: 9.15 ms, total: 5.73 s\n",
            "Wall time: 7.12 s\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "-lGMTqBI1kgZ",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "For Part II, running the program for a few instructions show that there is a cyclic structure in the program... In my input, the register state at `step 28` is `[0, 1, 10, 0, 2, 10551331]`,  and it is where the program starts to loop through instructions 13, 5, 6, 7, 8, 10, 11, 12. \n",
        "```"
      ]
    },
    {
      "metadata": {
        "id": "GtmmZ-xe1hHs",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 714
        },
        "outputId": "70313ebf-3ba6-4a4d-fa42-6fd139aec531"
      },
      "cell_type": "code",
      "source": [
        "_ = run_programm(inputs, init_registers=[1, 0, 0, 0, 0, 0], verbose=True)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Step 1 addi 2 16 2 --> [1, 0, 17, 0, 0, 0]\n",
            "Step 2 addi 5 2 5 --> [1, 0, 18, 0, 0, 2]\n",
            "Step 3 mulr 5 5 5 --> [1, 0, 19, 0, 0, 4]\n",
            "Step 4 mulr 2 5 5 --> [1, 0, 20, 0, 0, 76]\n",
            "Step 5 muli 5 11 5 --> [1, 0, 21, 0, 0, 836]\n",
            "Step 6 addi 3 4 3 --> [1, 0, 22, 4, 0, 836]\n",
            "Step 7 mulr 3 2 3 --> [1, 0, 23, 88, 0, 836]\n",
            "Step 8 addi 3 7 3 --> [1, 0, 24, 95, 0, 836]\n",
            "Step 9 addr 5 3 5 --> [1, 0, 25, 95, 0, 931]\n",
            "Step 10 addr 2 0 2 --> [1, 0, 27, 95, 0, 931]\n",
            "Step 11 setr 2 1 3 --> [1, 0, 28, 27, 0, 931]\n",
            "Step 12 mulr 3 2 3 --> [1, 0, 29, 756, 0, 931]\n",
            "Step 13 addr 2 3 3 --> [1, 0, 30, 785, 0, 931]\n",
            "Step 14 mulr 2 3 3 --> [1, 0, 31, 23550, 0, 931]\n",
            "Step 15 muli 3 14 3 --> [1, 0, 32, 329700, 0, 931]\n",
            "Step 16 mulr 3 2 3 --> [1, 0, 33, 10550400, 0, 931]\n",
            "Step 17 addr 5 3 5 --> [1, 0, 34, 10550400, 0, 10551331]\n",
            "Step 18 seti 0 9 0 --> [0, 0, 35, 10550400, 0, 10551331]\n",
            "Step 19 seti 0 8 2 --> [0, 0, 1, 10550400, 0, 10551331]\n",
            "Step 20 seti 1 4 1 --> [0, 1, 2, 10550400, 0, 10551331]\n",
            "Step 21 seti 1 2 4 --> [0, 1, 3, 10550400, 1, 10551331]\n",
            "Step 22 mulr 1 4 3 --> [0, 1, 4, 1, 1, 10551331]\n",
            "Step 23 eqrr 3 5 3 --> [0, 1, 5, False, 1, 10551331]\n",
            "Step 24 addr 3 2 2 --> [0, 1, 6, False, 1, 10551331]\n",
            "Step 25 addi 2 1 2 --> [0, 1, 8, False, 1, 10551331]\n",
            "Step 26 addi 4 1 4 --> [0, 1, 9, False, 2, 10551331]\n",
            "Step 27 gtrr 4 5 3 --> [0, 1, 10, False, 2, 10551331]\n",
            "Step 28 addr 2 3 2 --> [0, 1, 11, False, 2, 10551331]\n",
            "Step 29 seti 2 7 2 --> [0, 1, 3, False, 2, 10551331]\n",
            "Step 30 mulr 1 4 3 --> [0, 1, 4, 2, 2, 10551331]\n",
            "Step 31 eqrr 3 5 3 --> [0, 1, 5, False, 2, 10551331]\n",
            "Step 32 addr 3 2 2 --> [0, 1, 6, False, 2, 10551331]\n",
            "Step 33 addi 2 1 2 --> [0, 1, 8, False, 2, 10551331]\n",
            "Step 34 addi 4 1 4 --> [0, 1, 9, False, 3, 10551331]\n",
            "Step 35 gtrr 4 5 3 --> [0, 1, 10, False, 3, 10551331]\n",
            "Step 36 addr 2 3 2 --> [0, 1, 11, False, 3, 10551331]\n",
            "Step 37 seti 2 7 2 --> [0, 1, 3, False, 3, 10551331]\n",
            "Step 38 mulr 1 4 3 --> [0, 1, 4, 3, 3, 10551331]\n",
            "Step 39 eqrr 3 5 3 --> [0, 1, 5, False, 3, 10551331]\n",
            "Step 40 addr 3 2 2 --> [0, 1, 6, False, 3, 10551331]\n",
            "Step 41 addi 2 1 2 --> [0, 1, 8, False, 3, 10551331]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "id": "qrn3TDcn1006",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "In other words, the loop is:\n",
        "\n",
        "```\n",
        "seti 2 7 2 --> Set R2 to 2\n",
        "mulr 1 4 3 --> R3 = R1 * R4 = R4\n",
        "eqrr 3 5 3 --> Set R3 to bool(R5 == R3)\n",
        "addr 3 2 2 --> R2 += R3\n",
        "  (addi 2 1 2 --> R2 += 1) if R3 = 0\n",
        "  (addr 1 0 0 --> R0 += R1) if R3 = 1\n",
        "addi 4 1 4 --> R4 += 1\n",
        "gtrr 4 5 3 --> Set R3 to bool(R4 > R5)\n",
        "addr 2 3 2 --> R2 += R3 (escape the loop when R3 is True)\n",
        "```\n",
        "\n",
        "which translates as:"
      ]
    },
    {
      "metadata": {
        "id": "eG4_EGuT1yGd",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def inner_loop(registers):\n",
        "  # when R3 == R5 is possible, R0 gets updated once (when R4 = R5 // R1)\n",
        "  # Oterwise the loop only increment R4 until it reaches R5\n",
        "  if registers[5] % registers[1] == 0:\n",
        "    registers[0] += registers[1] \n",
        "  registers[4] = registers[5] + 1\n",
        "  registers[2] = 12"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "JYIrM8CF1_N5",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Replacing the instructions loop with this shortcut everytime I encouter instruction `seti 2 7 2`, I again run the program and detect another loop :[ , which is as follows:\n",
        "\n",
        "```\n",
        "addi 1 1 1 --> R1 += 1\n",
        "gtrr 1 5 3 --> Set R3 to bool(R1 > R5)\n",
        "addr 3 2 2 --> R2 += R3 (escape the loop if R3 is True)\n",
        "seti 1 0 2 --> R2 = 1\n",
        "seti 1 2 4 --> R4 = 1\n",
        "  [... back to the first loop .... ]\n",
        "```"
      ]
    },
    {
      "metadata": {
        "id": "lOCSdm_012rt",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        " def main_loop(registers):\n",
        "  \"\"\"Outer loop shortcut\"\"\"\n",
        "  while registers[1] <= registers[5]:\n",
        "    registers[4] = 1\n",
        "    inner_loop(registers)\n",
        "    registers[1] += 1\n",
        "  registers[2] = 16\n",
        "  \n",
        "def run_programm_with_loop(inputs, init_registers=None):\n",
        "  \"\"\"Run the background program ut shortcut the inner loop\"\"\"\n",
        "  registers = [0] * 6\n",
        "  if init_registers is not None:\n",
        "    registers = init_registers\n",
        "  inst_register = inputs[0][1]\n",
        "  instructions = inputs[1:]\n",
        "  while 1:\n",
        "    # First inner loop\n",
        "    if registers[inst_register] == 11:\n",
        "      inner_loop(registers)\n",
        "    # Outer loop\n",
        "    if registers[inst_register] == 13:\n",
        "      main_loop(registers)\n",
        "    else:\n",
        "      op, a, b, c = instructions[registers[inst_register]]\n",
        "      operations[op](a, b, c, registers)\n",
        "      if registers[inst_register] >= len(instructions) - 1:\n",
        "        break\n",
        "      registers[inst_register] += 1\n",
        "  return registers"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "sK7A_uI82CqH",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        },
        "outputId": "828d5812-4cdc-4952-b20e-3db448354abf"
      },
      "cell_type": "code",
      "source": [
        "%%time\n",
        "print('Final value of register 0:', run_programm_with_loop(inputs, init_registers=[1, 0, 0, 0, 0, 0])[0])"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Final value of register 0: 12474720\n",
            "CPU times: user 5.45 s, sys: 2.77 ms, total: 5.45 s\n",
            "Wall time: 5.45 s\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}