X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=07-interpreter%2Fmachine-code.ipynb;h=48da543feccf20468c7c036c640544966007074b;hb=84f849f83970f3a6295d09da5c1bef1fe9cec4cb;hp=7d3d6a603af069bb4cb67849bc32c7a136736979;hpb=6b6255ad38d913560571c8d2aaea0fb55c9a030a;p=ou-summer-of-code-2017.git

diff --git a/07-interpreter/machine-code.ipynb b/07-interpreter/machine-code.ipynb
index 7d3d6a6..48da543 100644
--- a/07-interpreter/machine-code.ipynb
+++ b/07-interpreter/machine-code.ipynb
@@ -34,7 +34,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
+   "execution_count": 1,
    "metadata": {
     "collapsed": true
    },
@@ -50,7 +50,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
+   "execution_count": 2,
    "metadata": {
     "collapsed": true
    },
@@ -64,7 +64,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 3,
    "metadata": {
     "collapsed": true
    },
@@ -77,7 +77,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
+   "execution_count": 4,
    "metadata": {
     "collapsed": true
    },
@@ -90,7 +90,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 26,
+   "execution_count": 5,
    "metadata": {
     "collapsed": true
    },
@@ -102,7 +102,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 27,
+   "execution_count": 6,
    "metadata": {
     "collapsed": true
    },
@@ -117,7 +117,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 28,
+   "execution_count": 7,
    "metadata": {
     "collapsed": true
    },
@@ -130,7 +130,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 29,
+   "execution_count": 8,
    "metadata": {
     "collapsed": true
    },
@@ -143,7 +143,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 30,
+   "execution_count": 9,
    "metadata": {
     "collapsed": true
    },
@@ -156,7 +156,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 31,
+   "execution_count": 10,
    "metadata": {
     "collapsed": true
    },
@@ -172,7 +172,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 32,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -186,7 +186,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 33,
+   "execution_count": 12,
    "metadata": {
     "collapsed": true
    },
@@ -204,7 +204,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 34,
+   "execution_count": 13,
    "metadata": {},
    "outputs": [
     {
@@ -213,7 +213,7 @@
        "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
       ]
      },
-     "execution_count": 34,
+     "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -229,7 +229,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 35,
+   "execution_count": 14,
    "metadata": {
     "collapsed": true
    },
@@ -241,21 +241,23 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 36,
+   "execution_count": 42,
    "metadata": {
     "collapsed": true
    },
    "outputs": [],
    "source": [
     "def program_from_listing(listing, machine):\n",
-    "    labelled_instructions = [i for i in listing.split('\\n') if i]\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": 37,
+   "execution_count": 39,
    "metadata": {
     "collapsed": true
    },
@@ -288,7 +290,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 38,
+   "execution_count": 17,
    "metadata": {},
    "outputs": [
     {
@@ -297,7 +299,7 @@
        "['inc', 'a']"
       ]
      },
-     "execution_count": 38,
+     "execution_count": 17,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -308,37 +310,41 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 39,
+   "execution_count": 40,
    "metadata": {},
    "outputs": [
     {
-     "data": {
-      "text/plain": [
-       "['set a 10', 'dec a', 'inc b', 'sto b 1', 'jpz a 2', 'jmp -4']"
-      ]
-     },
-     "execution_count": 39,
-     "metadata": {},
-     "output_type": "execute_result"
+     "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 for i in program.split('\\n') if i]\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",
-    "instructions"
+    "print('\\n'.join(instructions))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 40,
+   "execution_count": 19,
    "metadata": {
     "collapsed": true
    },
@@ -356,7 +362,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 41,
+   "execution_count": 20,
    "metadata": {
     "collapsed": true
    },
@@ -371,7 +377,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
+   "execution_count": 21,
    "metadata": {},
    "outputs": [
     {
@@ -387,7 +393,7 @@
        " 'pc': 4}"
       ]
      },
-     "execution_count": 42,
+     "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -404,26 +410,26 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 43,
+   "execution_count": 22,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "{'b': 10,\n",
-       " 1: 10,\n",
-       " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
+       "{'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",
-       " 'pc': 6,\n",
+       " 1: 10,\n",
+       " 'c': 20,\n",
        " 'a': 0,\n",
-       " 'c': 20}"
+       " 'pc': 6,\n",
+       " 'b': 10}"
       ]
      },
-     "execution_count": 43,
+     "execution_count": 22,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -445,26 +451,26 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 44,
+   "execution_count": 23,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "{'b': 10,\n",
-       " 1: 10,\n",
-       " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
+       "{'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",
-       " 'pc': 6,\n",
+       " 1: 10,\n",
+       " 'c': 20,\n",
        " 'a': 0,\n",
-       " 'c': 20}"
+       " 'pc': 6,\n",
+       " 'b': 10}"
       ]
      },
-     "execution_count": 44,
+     "execution_count": 23,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -483,7 +489,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
@@ -504,7 +510,7 @@
        " 'pc': 10}"
       ]
      },
-     "execution_count": 45,
+     "execution_count": 24,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -529,7 +535,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 49,
+   "execution_count": 25,
    "metadata": {},
    "outputs": [
     {
@@ -550,7 +556,7 @@
        " 'pc': 9}"
       ]
      },
-     "execution_count": 49,
+     "execution_count": 25,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -576,16 +582,16 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 52,
+   "execution_count": 85,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "'10: 7, a: 0, b: 1, c: 3, pc: 11'"
+       "'1: 8, a: 0, b: 1, c: 8, pc: 11'"
       ]
      },
-     "execution_count": 52,
+     "execution_count": 85,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -593,7 +599,6 @@
    "source": [
     "# c holds floor(a/2)\n",
     "program = \"\"\"\n",
-    "      sto a 10\n",
     "      set c 0\n",
     "      set b 0\n",
     "loop: dec a\n",
@@ -604,6 +609,166 @@
     "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",
@@ -611,6 +776,133 @@
     "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,