{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine interpreter\n",
    "\n",
    "## Instructions\n",
    "\n",
    "Three registers, `a`, `b`, and `c`. \n",
    "Program counter, `pc`.\n",
    "Unlimited memory in numbered addresses, completely separate from program storage.\n",
    "\n",
    "Each register and memory location can hold 8-byte integers (Java `long`s).\n",
    "\n",
    "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
    "\n",
    "`jmp` and `jpz` override this normal change in `pc`.\n",
    "\n",
    "| Instruction | Description |\n",
    "|:------------|:------------|\n",
    "| `inc r`     | increment contents of register `r` |\n",
    "| `dec r`     | decrement contents of register `r` |\n",
    "| `set r i`   | set contents of register `r` to literal value `i` |\n",
    "| `cpy r s`   | set contents of register `r` into register `s` | \n",
    "| `sto r m`   | store contents of register `r` into memory location `m` |\n",
    "| `ld r m`    | load contents of memory location `m` into register `r` |\n",
    "| `jmp i`     | jump to instruction `i` places forward |\n",
    "| `jpz r i`   | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
    "\n",
    "For `jmp` and `jpz`, `i` is relative to the current instruction. `i` can be negative to jump to earlier places in the program. `i`=1 is a no-op, `i`=0 causes an infinite loop."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def new_machine():\n",
    "    return {'pc': 0, \n",
    "            'a': 0,\n",
    "            'b': 0, \n",
    "            'c': 0,\n",
    "            'instructions': []}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def show_machine(machine):\n",
    "    return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
    "                     for sk in sorted(str(k) for k in machine)\n",
    "                     if sk != 'instructions')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def inc(reg, machine):\n",
    "    machine[reg] += 1\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dec(reg, machine):\n",
    "    machine[reg] -= 1\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def jmp(addr, machine):\n",
    "    machine['pc'] += addr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def jpz(reg, addr, machine):\n",
    "    if machine[reg] == 0:\n",
    "        machine['pc'] += addr\n",
    "    else:\n",
    "        machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def set_literal(reg, literal, machine):\n",
    "    machine[reg] = literal\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cpy(from_reg, to_reg, machine):\n",
    "    machine[to_reg] = machine[from_reg]\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sto(reg, addr, machine):\n",
    "    machine[addr] = machine[reg]\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ld(reg, addr, machine):\n",
    "    if addr in machine:\n",
    "        machine[reg] = machine[addr]\n",
    "    else:\n",
    "        machine[reg] = 0\n",
    "    machine['pc'] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
    "                    'jpz': jpz, 'set': set_literal, 'cpy': cpy,\n",
    "                    'sto': sto, 'ld': ld}\n",
    "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def parse(instruction):\n",
    "    words = instruction.split()\n",
    "    instr = words[0]\n",
    "    args = words[1:]\n",
    "    if instr in numeric_args_table:\n",
    "        for p in numeric_args_table[instr]:\n",
    "            args[p] = int(args[p])\n",
    "    return instruction_table[instr], args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = new_machine()\n",
    "inc('a', m)\n",
    "cargs = ['a', 'b']\n",
    "cpy(*cargs, m)\n",
    "inc('a', m)\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def program_from_instructions(prog, machine):\n",
    "    machine['instructions'] = [parse(instr) for instr in prog]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def program_from_listing(listing, machine):\n",
    "    labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
    "                             if i.strip() \n",
    "                             if not i.strip().startswith('#')]\n",
    "    instructions = replace_labels(labelled_instructions)\n",
    "    program_from_instructions(instructions, machine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def replace_labels(listing):\n",
    "    locations = {}\n",
    "    for n, i in enumerate(listing):\n",
    "        if ':' in i:\n",
    "            locations[i.split(':')[0]] = n\n",
    "\n",
    "    unlabelled_listing = []\n",
    "    for n, i in enumerate(listing):\n",
    "        instr = i.split()\n",
    "        if ':' in i:\n",
    "            instr = i.split(':')[1].split()\n",
    "        else:\n",
    "            instr = i.split()\n",
    "        terms = []\n",
    "        for term in instr:\n",
    "            if term in locations:\n",
    "                terms += [str(locations[term] - n)]\n",
    "            else:\n",
    "                terms += [term]\n",
    "        transformed_instr = ' '.join(terms)\n",
    "        unlabelled_listing += [transformed_instr]\n",
    "        \n",
    "    return unlabelled_listing    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['inc', 'a']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'fred: inc a'.split(':')[1].split()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set a 10\n",
      "dec a\n",
      "inc b\n",
      "sto b 1\n",
      "jpz a 2\n",
      "jmp -4\n"
     ]
    }
   ],
   "source": [
    "program = \"\"\"\n",
    "      set a 10\n",
    "      # comment line\n",
    "      \n",
    "loop: dec a\n",
    "      inc b\n",
    "      sto b 1\n",
    "      jpz a 2\n",
    "      jmp loop\n",
    "\"\"\"\n",
    "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
    "instructions = replace_labels(labelled_instructions)\n",
    "print('\\n'.join(instructions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def run(machine, initial_state=None, trace=False):\n",
    "    if initial_state:\n",
    "        machine.update(initial_state)\n",
    "    while machine['pc'] < len(machine['instructions']):\n",
    "        if trace:\n",
    "            print(show_machine(machine))\n",
    "        cmd, args = machine['instructions'][machine['pc']]\n",
    "        cmd(*args, machine)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def execute(listing, initial_state=None, trace=False):\n",
    "    m = new_machine()\n",
    "    program_from_listing(listing, m)\n",
    "    run(m, initial_state=initial_state, trace=trace)\n",
    "    return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 3,\n",
       " 'b': 2,\n",
       " 'c': 0,\n",
       " 'instructions': [(<function __main__.inc>, ['a']),\n",
       "  (<function __main__.inc>, ['a']),\n",
       "  (<function __main__.cpy>, ['a', 'b']),\n",
       "  (<function __main__.inc>, ['a'])],\n",
       " 'pc': 4}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program = \"\"\"\n",
    "inc a\n",
    "inc a\n",
    "cpy a b\n",
    "inc a\n",
    "\"\"\"\n",
    "execute(program)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
       "  (<function __main__.dec>, ['a']),\n",
       "  (<function __main__.inc>, ['b']),\n",
       "  (<function __main__.sto>, ['b', 1]),\n",
       "  (<function __main__.jpz>, ['a', 2]),\n",
       "  (<function __main__.jmp>, [-4])],\n",
       " 1: 10,\n",
       " 'c': 20,\n",
       " 'a': 0,\n",
       " 'pc': 6,\n",
       " 'b': 10}"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program = \"\"\"\n",
    "set a 10\n",
    "dec a\n",
    "inc b\n",
    "sto b 1\n",
    "jpz a 2\n",
    "jmp -4\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "execute(program, initial_state={'c': 20})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
       "  (<function __main__.dec>, ['a']),\n",
       "  (<function __main__.inc>, ['b']),\n",
       "  (<function __main__.sto>, ['b', 1]),\n",
       "  (<function __main__.jpz>, ['a', 2]),\n",
       "  (<function __main__.jmp>, [-4])],\n",
       " 1: 10,\n",
       " 'c': 20,\n",
       " 'a': 0,\n",
       " 'pc': 6,\n",
       " 'b': 10}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program = \"\"\"\n",
    "      set a 10\n",
    "loop: dec a\n",
    "      inc b\n",
    "      sto b 1\n",
    "      jpz a 2\n",
    "      jmp loop\n",
    "\"\"\"\n",
    "execute(program, initial_state={'c': 20})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 0,\n",
       " 'b': 1,\n",
       " 'c': 5,\n",
       " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
       "  (<function __main__.set_literal>, ['b', 0]),\n",
       "  (<function __main__.dec>, ['a']),\n",
       "  (<function __main__.jpz>, ['b', 3]),\n",
       "  (<function __main__.dec>, ['b']),\n",
       "  (<function __main__.jmp>, [2]),\n",
       "  (<function __main__.inc>, ['b']),\n",
       "  (<function __main__.jpz>, ['a', 3]),\n",
       "  (<function __main__.jmp>, [-6])],\n",
       " 'pc': 10}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "program = \"\"\"\n",
    "cpy c a\n",
    "set b 0\n",
    "dec a\n",
    "jpz b 3\n",
    "dec b\n",
    "jmp 2\n",
    "inc b\n",
    "jpz a 3\n",
    "jmp -6\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "execute(program, initial_state={'c': 5})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 0,\n",
       " 'b': 1,\n",
       " 'c': 5,\n",
       " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
       "  (<function __main__.set_literal>, ['b', 0]),\n",
       "  (<function __main__.dec>, ['a']),\n",
       "  (<function __main__.jpz>, ['b', 3]),\n",
       "  (<function __main__.dec>, ['b']),\n",
       "  (<function __main__.jmp>, [2]),\n",
       "  (<function __main__.inc>, ['b']),\n",
       "  (<function __main__.jpz>, ['a', 2]),\n",
       "  (<function __main__.jmp>, [-6])],\n",
       " 'pc': 9}"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# b holds parity of number in c: (c % 2)\n",
    "program = \"\"\"\n",
    "      cpy c a\n",
    "      set b 0\n",
    "loop: dec a\n",
    "      jpz b odd\n",
    "      dec b\n",
    "      jmp end\n",
    "odd:  inc b\n",
    "end:  jpz a 2\n",
    "      jmp loop\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "execute(program, initial_state={'c': 5})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1: 8, a: 0, b: 1, c: 8, pc: 11'"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# c holds floor(a/2)\n",
    "program = \"\"\"\n",
    "      set c 0\n",
    "      set b 0\n",
    "loop: dec a\n",
    "      jpz b odd\n",
    "      dec b\n",
    "      inc c\n",
    "      jmp end\n",
    "odd:  inc b\n",
    "end:  jpz a 2\n",
    "      jmp loop\n",
    "      sto c 1\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "show_machine(execute(program, initial_state={'a': 17}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a: 4, b: 0, c: 12, pc: 9'"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# c holds a * 3\n",
    "program = \"\"\"\n",
    "      set c 0\n",
    "      cpy a b\n",
    "      # start of main loop\n",
    "loop: jpz b end\n",
    "      dec b\n",
    "      inc c\n",
    "      inc c\n",
    "      inc c\n",
    "      jmp loop\n",
    "      \n",
    "      # end of program \n",
    "      \n",
    "end:  jmp 1\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "show_machine(execute(program, initial_state={'a': 4}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# c holds a!\n",
    "program = \"\"\"\n",
    "??????????????\n",
    "      set c 0\n",
    "      cpy a b\n",
    "      # start of main loop\n",
    "loop: jpz b end\n",
    "      dec b\n",
    "      inc c\n",
    "      inc c\n",
    "      inc c\n",
    "      jmp loop\n",
    "      \n",
    "      # end of program \n",
    "      \n",
    "end:  jmp 1\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "show_machine(execute(program, initial_state={'a': 4}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1: 52, a: 0, b: 0, c: 0, pc: 46'"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
    "# Location 2 holds number of steps taken\n",
    "# Location 3 holds max value reached\n",
    "program = \"\"\"\n",
    "      sto a 1\n",
    "      \n",
    "      set b 0\n",
    "      \n",
    "      # if a is one, finish, \n",
    "main: dec a\n",
    "      jpz a end\n",
    "      inc a\n",
    "      \n",
    "      # find parity of a\n",
    "      cpy a c\n",
    "      set b 0\n",
    "prty: dec c\n",
    "      jpz b odd\n",
    "      dec b\n",
    "      jmp prte\n",
    "odd:  inc b\n",
    "prte: jpz c 2\n",
    "      jmp prty\n",
    "      \n",
    "      # b == 0 means a even; b == 1 means a odd\n",
    "      jpz b isev\n",
    "\n",
    "      # c holds a * 3 + 1\n",
    "      cpy a b\n",
    "mul:  jpz b emul\n",
    "      dec b\n",
    "      inc c\n",
    "      inc c\n",
    "      inc c\n",
    "      jmp mul\n",
    "emul: inc c\n",
    "      cpy c a\n",
    "      jmp fin\n",
    "      \n",
    "      \n",
    "isev: set c 0\n",
    "      set b 0\n",
    "hlvl: dec a\n",
    "      jpz b oddh\n",
    "      dec b\n",
    "      inc c\n",
    "      jmp endh\n",
    "oddh: inc b\n",
    "endh: jpz a 2\n",
    "      jmp hlvl\n",
    "      cpy c a\n",
    "\n",
    "fin:  cpy a b\n",
    "      ld  c 1\n",
    "maxc: jpz c this\n",
    "      jpz b othr\n",
    "      dec b\n",
    "      dec c\n",
    "      jmp maxc\n",
    "this: sto a 1\n",
    "othr: jmp main\n",
    "      \n",
    "      # end of program \n",
    "      \n",
    "end:  set c 0\n",
    "\"\"\"\n",
    "# m = new_machine()\n",
    "# program_from_listing(program, m)\n",
    "# run(m)\n",
    "show_machine(execute(program, initial_state={'a': 7}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "13*3+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def max_collatz(start):\n",
    "    mc = start\n",
    "    i = start\n",
    "    while i != 1:\n",
    "        if i % 2 == 0:\n",
    "            i = i // 2\n",
    "        else:\n",
    "            i = 3 * i + 1\n",
    "        if i > mc:\n",
    "            mc = i\n",
    "    return mc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "52"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_collatz(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(250504, 937)"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max([(max_collatz(i), i) for i in range(1, 1000)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ans = []\n",
    "for i in range(1, 100):\n",
    "    m = execute(program, initial_state={'a': i})\n",
    "    c = max_collatz(i)\n",
    "    if m[1] != c:\n",
    "        ans += [(i, m[1], c)]\n",
    "ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1: 250504, a: 0, b: 0, c: 0, pc: 46'"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show_machine(execute(program, initial_state={'a': 937}))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}