07-interpreter/machine-code-4-reg.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Machine interpreter\n",
   8     "\n",
   9     "## Instructions\n",
  10     "\n",
  11     "Four registers, `a`, `b`, `c`, and `d`.\n",
  12     "Program counter, `pc`.\n",
  13     "\n",
  14     "Each register can hold 8-byte integers (Java `long`s).\n",
  15     "\n",
  16     "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
  17     "\n",
  18     "`jmp` and `jpz` override this normal change in `pc`.\n",
  19     "\n",
  20     "| Instruction | Description |\n",
  21     "|:------------|:------------|\n",
  22     "| `inc r`     | increment contents of register `r` |\n",
  23     "| `dec r`     | decrement contents of register `r` |\n",
  24     "| `set r i`   | set contents of register `r` to literal value `i` |\n",
  25     "| `cpy r s`   | copy contents of register `r` into register `s` | \n",
  26     "| `jmp i`     | jump to instruction `i` places forward |\n",
  27     "| `jpz r i`   | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
  28     "\n",
  29     "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."
  30    ]
  31   },
  32   {
  33    "cell_type": "code",
  34    "execution_count": 1,
  35    "metadata": {
  36     "collapsed": true
  37    },
  38    "outputs": [],
  39    "source": [
  40     "def new_machine():\n",
  41     "    return {'pc': 0, \n",
  42     "            'a': 0,\n",
  43     "            'b': 0, \n",
  44     "            'c': 0,\n",
  45     "            'd': 0,\n",
  46     "            'instructions': []}"
  47    ]
  48   },
  49   {
  50    "cell_type": "code",
  51    "execution_count": 2,
  52    "metadata": {
  53     "collapsed": true
  54    },
  55    "outputs": [],
  56    "source": [
  57     "def show_machine(machine):\n",
  58     "    return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
  59     "                     for sk in sorted(str(k) for k in machine)\n",
  60     "                     if sk != 'instructions')"
  61    ]
  62   },
  63   {
  64    "cell_type": "code",
  65    "execution_count": 3,
  66    "metadata": {
  67     "collapsed": true
  68    },
  69    "outputs": [],
  70    "source": [
  71     "def inc(reg, machine):\n",
  72     "    machine[reg] += 1\n",
  73     "    machine['pc'] += 1"
  74    ]
  75   },
  76   {
  77    "cell_type": "code",
  78    "execution_count": 4,
  79    "metadata": {
  80     "collapsed": true
  81    },
  82    "outputs": [],
  83    "source": [
  84     "def dec(reg, machine):\n",
  85     "    machine[reg] -= 1\n",
  86     "    machine['pc'] += 1"
  87    ]
  88   },
  89   {
  90    "cell_type": "code",
  91    "execution_count": 5,
  92    "metadata": {
  93     "collapsed": true
  94    },
  95    "outputs": [],
  96    "source": [
  97     "def jmp(addr, machine):\n",
  98     "    machine['pc'] += addr"
  99    ]
 100   },
 101   {
 102    "cell_type": "code",
 103    "execution_count": 6,
 104    "metadata": {
 105     "collapsed": true
 106    },
 107    "outputs": [],
 108    "source": [
 109     "def jpz(reg, addr, machine):\n",
 110     "    if machine[reg] == 0:\n",
 111     "        machine['pc'] += addr\n",
 112     "    else:\n",
 113     "        machine['pc'] += 1"
 114    ]
 115   },
 116   {
 117    "cell_type": "code",
 118    "execution_count": 7,
 119    "metadata": {
 120     "collapsed": true
 121    },
 122    "outputs": [],
 123    "source": [
 124     "def set_literal(reg, literal, machine):\n",
 125     "    machine[reg] = literal\n",
 126     "    machine['pc'] += 1"
 127    ]
 128   },
 129   {
 130    "cell_type": "code",
 131    "execution_count": 8,
 132    "metadata": {
 133     "collapsed": true
 134    },
 135    "outputs": [],
 136    "source": [
 137     "def cpy(from_reg, to_reg, machine):\n",
 138     "    machine[to_reg] = machine[from_reg]\n",
 139     "    machine['pc'] += 1"
 140    ]
 141   },
 142   {
 143    "cell_type": "code",
 144    "execution_count": 9,
 145    "metadata": {
 146     "collapsed": true
 147    },
 148    "outputs": [],
 149    "source": [
 150     "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
 151     "                    'jpz': jpz, 'set': set_literal, 'cpy': cpy}\n",
 152     "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
 153    ]
 154   },
 155   {
 156    "cell_type": "code",
 157    "execution_count": 10,
 158    "metadata": {
 159     "collapsed": true
 160    },
 161    "outputs": [],
 162    "source": [
 163     "def parse(instruction):\n",
 164     "    words = instruction.split()\n",
 165     "    instr = words[0]\n",
 166     "    args = words[1:]\n",
 167     "    if instr in numeric_args_table:\n",
 168     "        for p in numeric_args_table[instr]:\n",
 169     "            args[p] = int(args[p])\n",
 170     "    return instruction_table[instr], args"
 171    ]
 172   },
 173   {
 174    "cell_type": "code",
 175    "execution_count": 11,
 176    "metadata": {},
 177    "outputs": [
 178     {
 179      "data": {
 180       "text/plain": [
 181        "{'a': 2, 'b': 1, 'c': 0, 'd': 0, 'instructions': [], 'pc': 3}"
 182       ]
 183      },
 184      "execution_count": 11,
 185      "metadata": {},
 186      "output_type": "execute_result"
 187     }
 188    ],
 189    "source": [
 190     "m = new_machine()\n",
 191     "inc('a', m)\n",
 192     "cargs = ['a', 'b']\n",
 193     "cpy(*cargs, m)\n",
 194     "inc('a', m)\n",
 195     "m"
 196    ]
 197   },
 198   {
 199    "cell_type": "code",
 200    "execution_count": 12,
 201    "metadata": {
 202     "collapsed": true
 203    },
 204    "outputs": [],
 205    "source": [
 206     "def program_from_instructions(prog, machine):\n",
 207     "    machine['instructions'] = [parse(instr) for instr in prog]"
 208    ]
 209   },
 210   {
 211    "cell_type": "code",
 212    "execution_count": 45,
 213    "metadata": {
 214     "collapsed": true
 215    },
 216    "outputs": [],
 217    "source": [
 218     "def unlabel_listing(listing):\n",
 219     "    labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
 220     "                             if i.strip() \n",
 221     "                             if not i.strip().startswith('#')]\n",
 222     "    return replace_labels(labelled_instructions)    "
 223    ]
 224   },
 225   {
 226    "cell_type": "code",
 227    "execution_count": 13,
 228    "metadata": {
 229     "collapsed": true
 230    },
 231    "outputs": [],
 232    "source": [
 233     "# def program_from_listing(listing, machine):\n",
 234     "#     labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
 235     "#                              if i.strip() \n",
 236     "#                              if not i.strip().startswith('#')]\n",
 237     "#     instructions = replace_labels(labelled_instructions)\n",
 238     "#     program_from_instructions(instructions, machine)"
 239    ]
 240   },
 241   {
 242    "cell_type": "code",
 243    "execution_count": 53,
 244    "metadata": {
 245     "collapsed": true
 246    },
 247    "outputs": [],
 248    "source": [
 249     "def program_from_listing(listing, machine):\n",
 250     "    instructions = unlabel_listing(listing)\n",
 251     "    program_from_instructions(instructions, machine)"
 252    ]
 253   },
 254   {
 255    "cell_type": "code",
 256    "execution_count": 14,
 257    "metadata": {
 258     "collapsed": true
 259    },
 260    "outputs": [],
 261    "source": [
 262     "def replace_labels(listing):\n",
 263     "    locations = {}\n",
 264     "    for n, i in enumerate(listing):\n",
 265     "        if ':' in i:\n",
 266     "            locations[i.split(':')[0]] = n\n",
 267     "\n",
 268     "    unlabelled_listing = []\n",
 269     "    for n, i in enumerate(listing):\n",
 270     "        instr = i.split()\n",
 271     "        if ':' in i:\n",
 272     "            instr = i.split(':')[1].split()\n",
 273     "        else:\n",
 274     "            instr = i.split()\n",
 275     "        terms = []\n",
 276     "        for term in instr:\n",
 277     "            if term in locations:\n",
 278     "                terms += [str(locations[term] - n)]\n",
 279     "            else:\n",
 280     "                terms += [term]\n",
 281     "        transformed_instr = ' '.join(terms)\n",
 282     "        unlabelled_listing += [transformed_instr]\n",
 283     "        \n",
 284     "    return unlabelled_listing    "
 285    ]
 286   },
 287   {
 288    "cell_type": "code",
 289    "execution_count": 15,
 290    "metadata": {},
 291    "outputs": [
 292     {
 293      "data": {
 294       "text/plain": [
 295        "['inc', 'a']"
 296       ]
 297      },
 298      "execution_count": 15,
 299      "metadata": {},
 300      "output_type": "execute_result"
 301     }
 302    ],
 303    "source": [
 304     "'fred: inc a'.split(':')[1].split()"
 305    ]
 306   },
 307   {
 308    "cell_type": "code",
 309    "execution_count": 47,
 310    "metadata": {},
 311    "outputs": [
 312     {
 313      "name": "stdout",
 314      "output_type": "stream",
 315      "text": [
 316       "set a 10\n",
 317       "dec a\n",
 318       "inc b\n",
 319       "jpz a 2\n",
 320       "jmp -3\n"
 321      ]
 322     }
 323    ],
 324    "source": [
 325     "program = \"\"\"\n",
 326     "      set a 10\n",
 327     "      # comment line\n",
 328     "      \n",
 329     "loop: dec a\n",
 330     "      inc b\n",
 331     "      jpz a 2\n",
 332     "      jmp loop\n",
 333     "\"\"\"\n",
 334     "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
 335     "instructions = replace_labels(labelled_instructions)\n",
 336     "print('\\n'.join(instructions))"
 337    ]
 338   },
 339   {
 340    "cell_type": "code",
 341    "execution_count": 49,
 342    "metadata": {},
 343    "outputs": [
 344     {
 345      "name": "stdout",
 346      "output_type": "stream",
 347      "text": [
 348       "set a 10\n",
 349       "dec a\n",
 350       "inc b\n",
 351       "jpz a 2\n",
 352       "jmp -3\n"
 353      ]
 354     }
 355    ],
 356    "source": [
 357     "print('\\n'.join(unlabel_listing(program)))"
 358    ]
 359   },
 360   {
 361    "cell_type": "code",
 362    "execution_count": 17,
 363    "metadata": {
 364     "collapsed": true
 365    },
 366    "outputs": [],
 367    "source": [
 368     "def run(machine, initial_state=None, trace=False):\n",
 369     "    if initial_state:\n",
 370     "        machine.update(initial_state)\n",
 371     "    while machine['pc'] < len(machine['instructions']):\n",
 372     "        if trace:\n",
 373     "            print(show_machine(machine))\n",
 374     "        cmd, args = machine['instructions'][machine['pc']]\n",
 375     "        cmd(*args, machine)"
 376    ]
 377   },
 378   {
 379    "cell_type": "code",
 380    "execution_count": 18,
 381    "metadata": {
 382     "collapsed": true
 383    },
 384    "outputs": [],
 385    "source": [
 386     "def execute(listing, initial_state=None, trace=False):\n",
 387     "    m = new_machine()\n",
 388     "    program_from_listing(listing, m)\n",
 389     "    run(m, initial_state=initial_state, trace=trace)\n",
 390     "    return m"
 391    ]
 392   },
 393   {
 394    "cell_type": "code",
 395    "execution_count": 19,
 396    "metadata": {},
 397    "outputs": [
 398     {
 399      "data": {
 400       "text/plain": [
 401        "{'a': 3,\n",
 402        " 'b': 2,\n",
 403        " 'c': 0,\n",
 404        " 'd': 0,\n",
 405        " 'instructions': [(<function __main__.inc>, ['a']),\n",
 406        "  (<function __main__.inc>, ['a']),\n",
 407        "  (<function __main__.cpy>, ['a', 'b']),\n",
 408        "  (<function __main__.inc>, ['a'])],\n",
 409        " 'pc': 4}"
 410       ]
 411      },
 412      "execution_count": 19,
 413      "metadata": {},
 414      "output_type": "execute_result"
 415     }
 416    ],
 417    "source": [
 418     "program = \"\"\"\n",
 419     "inc a\n",
 420     "inc a\n",
 421     "cpy a b\n",
 422     "inc a\n",
 423     "\"\"\"\n",
 424     "execute(program)"
 425    ]
 426   },
 427   {
 428    "cell_type": "code",
 429    "execution_count": 20,
 430    "metadata": {},
 431    "outputs": [
 432     {
 433      "data": {
 434       "text/plain": [
 435        "{'a': 0,\n",
 436        " 'b': 10,\n",
 437        " 'c': 20,\n",
 438        " 'd': 0,\n",
 439        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 440        "  (<function __main__.dec>, ['a']),\n",
 441        "  (<function __main__.inc>, ['b']),\n",
 442        "  (<function __main__.jpz>, ['a', 2]),\n",
 443        "  (<function __main__.jmp>, [-3])],\n",
 444        " 'pc': 5}"
 445       ]
 446      },
 447      "execution_count": 20,
 448      "metadata": {},
 449      "output_type": "execute_result"
 450     }
 451    ],
 452    "source": [
 453     "program = \"\"\"\n",
 454     "set a 10\n",
 455     "dec a\n",
 456     "inc b\n",
 457     "jpz a 2\n",
 458     "jmp -3\n",
 459     "\"\"\"\n",
 460     "# m = new_machine()\n",
 461     "# program_from_listing(program, m)\n",
 462     "# run(m)\n",
 463     "execute(program, initial_state={'c': 20})"
 464    ]
 465   },
 466   {
 467    "cell_type": "code",
 468    "execution_count": 21,
 469    "metadata": {},
 470    "outputs": [
 471     {
 472      "data": {
 473       "text/plain": [
 474        "{'a': 0,\n",
 475        " 'b': 10,\n",
 476        " 'c': 20,\n",
 477        " 'd': 0,\n",
 478        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 479        "  (<function __main__.dec>, ['a']),\n",
 480        "  (<function __main__.inc>, ['b']),\n",
 481        "  (<function __main__.jpz>, ['a', 2]),\n",
 482        "  (<function __main__.jmp>, [-3])],\n",
 483        " 'pc': 5}"
 484       ]
 485      },
 486      "execution_count": 21,
 487      "metadata": {},
 488      "output_type": "execute_result"
 489     }
 490    ],
 491    "source": [
 492     "program = \"\"\"\n",
 493     "      set a 10\n",
 494     "loop: dec a\n",
 495     "      inc b\n",
 496     "      jpz a 2\n",
 497     "      jmp loop\n",
 498     "\"\"\"\n",
 499     "execute(program, initial_state={'c': 20})"
 500    ]
 501   },
 502   {
 503    "cell_type": "code",
 504    "execution_count": 22,
 505    "metadata": {},
 506    "outputs": [
 507     {
 508      "data": {
 509       "text/plain": [
 510        "{'a': 0,\n",
 511        " 'b': 1,\n",
 512        " 'c': 5,\n",
 513        " 'd': 0,\n",
 514        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 515        "  (<function __main__.set_literal>, ['b', 0]),\n",
 516        "  (<function __main__.dec>, ['a']),\n",
 517        "  (<function __main__.jpz>, ['b', 3]),\n",
 518        "  (<function __main__.dec>, ['b']),\n",
 519        "  (<function __main__.jmp>, [2]),\n",
 520        "  (<function __main__.inc>, ['b']),\n",
 521        "  (<function __main__.jpz>, ['a', 3]),\n",
 522        "  (<function __main__.jmp>, [-6])],\n",
 523        " 'pc': 10}"
 524       ]
 525      },
 526      "execution_count": 22,
 527      "metadata": {},
 528      "output_type": "execute_result"
 529     }
 530    ],
 531    "source": [
 532     "program = \"\"\"\n",
 533     "cpy c a\n",
 534     "set b 0\n",
 535     "dec a\n",
 536     "jpz b 3\n",
 537     "dec b\n",
 538     "jmp 2\n",
 539     "inc b\n",
 540     "jpz a 3\n",
 541     "jmp -6\n",
 542     "\"\"\"\n",
 543     "# m = new_machine()\n",
 544     "# program_from_listing(program, m)\n",
 545     "# run(m)\n",
 546     "execute(program, initial_state={'c': 5})"
 547    ]
 548   },
 549   {
 550    "cell_type": "code",
 551    "execution_count": 71,
 552    "metadata": {},
 553    "outputs": [
 554     {
 555      "data": {
 556       "text/plain": [
 557        "{'a': 0,\n",
 558        " 'b': 1,\n",
 559        " 'c': 5,\n",
 560        " 'd': 0,\n",
 561        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 562        "  (<function __main__.set_literal>, ['b', 0]),\n",
 563        "  (<function __main__.dec>, ['a']),\n",
 564        "  (<function __main__.jpz>, ['b', 3]),\n",
 565        "  (<function __main__.dec>, ['b']),\n",
 566        "  (<function __main__.jmp>, [2]),\n",
 567        "  (<function __main__.inc>, ['b']),\n",
 568        "  (<function __main__.jpz>, ['a', 2]),\n",
 569        "  (<function __main__.jmp>, [-6])],\n",
 570        " 'pc': 9}"
 571       ]
 572      },
 573      "execution_count": 71,
 574      "metadata": {},
 575      "output_type": "execute_result"
 576     }
 577    ],
 578    "source": [
 579     "# b holds parity of number in c: (c % 2)\n",
 580     "program = \"\"\"\n",
 581     "      cpy c a\n",
 582     "      set b 0\n",
 583     "loop: dec a\n",
 584     "      jpz b odd\n",
 585     "      dec b\n",
 586     "      jmp end\n",
 587     "odd:  inc b\n",
 588     "end:  jpz a 2\n",
 589     "      jmp loop\n",
 590     "\"\"\"\n",
 591     "# m = new_machine()\n",
 592     "# program_from_listing(program, m)\n",
 593     "# run(m)\n",
 594     "execute(program, initial_state={'c': 5})"
 595    ]
 596   },
 597   {
 598    "cell_type": "code",
 599    "execution_count": 64,
 600    "metadata": {},
 601    "outputs": [
 602     {
 603      "name": "stdout",
 604      "output_type": "stream",
 605      "text": [
 606       "cpy c a\n",
 607       "set b 0\n",
 608       "dec a\n",
 609       "jpz b 3\n",
 610       "dec b\n",
 611       "jmp 2\n",
 612       "inc b\n",
 613       "jpz a 2\n",
 614       "jmp -6\n"
 615      ]
 616     }
 617    ],
 618    "source": [
 619     "print('\\n'.join(unlabel_listing(program)))"
 620    ]
 621   },
 622   {
 623    "cell_type": "code",
 624    "execution_count": 65,
 625    "metadata": {},
 626    "outputs": [
 627     {
 628      "data": {
 629       "text/plain": [
 630        "'a: 0, b: 1, c: 8, d: 0, pc: 10'"
 631       ]
 632      },
 633      "execution_count": 65,
 634      "metadata": {},
 635      "output_type": "execute_result"
 636     }
 637    ],
 638    "source": [
 639     "# c holds floor(a/2)\n",
 640     "program = \"\"\"\n",
 641     "      set c 0\n",
 642     "      set b 0\n",
 643     "loop: dec a\n",
 644     "      jpz b odd\n",
 645     "      dec b\n",
 646     "      inc c\n",
 647     "      jmp end\n",
 648     "odd:  inc b\n",
 649     "end:  jpz a 2\n",
 650     "      jmp loop\n",
 651     "\"\"\"\n",
 652     "# m = new_machine()\n",
 653     "# program_from_listing(program, m)\n",
 654     "# run(m)\n",
 655     "show_machine(execute(program, initial_state={'a': 17}))"
 656    ]
 657   },
 658   {
 659    "cell_type": "code",
 660    "execution_count": 66,
 661    "metadata": {},
 662    "outputs": [
 663     {
 664      "name": "stdout",
 665      "output_type": "stream",
 666      "text": [
 667       "set c 0\n",
 668       "set b 0\n",
 669       "dec a\n",
 670       "jpz b 4\n",
 671       "dec b\n",
 672       "inc c\n",
 673       "jmp 2\n",
 674       "inc b\n",
 675       "jpz a 2\n",
 676       "jmp -7\n"
 677      ]
 678     }
 679    ],
 680    "source": [
 681     "print('\\n'.join(unlabel_listing(program)))"
 682    ]
 683   },
 684   {
 685    "cell_type": "code",
 686    "execution_count": 25,
 687    "metadata": {},
 688    "outputs": [
 689     {
 690      "data": {
 691       "text/plain": [
 692        "'a: 4, b: 0, c: 12, d: 0, pc: 9'"
 693       ]
 694      },
 695      "execution_count": 25,
 696      "metadata": {},
 697      "output_type": "execute_result"
 698     }
 699    ],
 700    "source": [
 701     "# c holds a * 3\n",
 702     "program = \"\"\"\n",
 703     "      set c 0\n",
 704     "      cpy a b\n",
 705     "      # start of main loop\n",
 706     "loop: jpz b end\n",
 707     "      dec b\n",
 708     "      inc c\n",
 709     "      inc c\n",
 710     "      inc c\n",
 711     "      jmp loop\n",
 712     "      \n",
 713     "      # end of program \n",
 714     "      \n",
 715     "end:  jmp 1\n",
 716     "\"\"\"\n",
 717     "# m = new_machine()\n",
 718     "# program_from_listing(program, m)\n",
 719     "# run(m)\n",
 720     "show_machine(execute(program, initial_state={'a': 4}))"
 721    ]
 722   },
 723   {
 724    "cell_type": "code",
 725    "execution_count": 67,
 726    "metadata": {},
 727    "outputs": [
 728     {
 729      "data": {
 730       "text/plain": [
 731        "'a: 0, b: 0, c: 27, d: 0, pc: 11'"
 732       ]
 733      },
 734      "execution_count": 67,
 735      "metadata": {},
 736      "output_type": "execute_result"
 737     }
 738    ],
 739    "source": [
 740     "# c holds a * b\n",
 741     "program = \"\"\"\n",
 742     "      set c 0\n",
 743     "      cpy a d\n",
 744     "loop: jpz b end      \n",
 745     "      dec b\n",
 746     "      cpy d a\n",
 747     "smul: jpz a emul\n",
 748     "      inc c\n",
 749     "      dec a\n",
 750     "      jmp smul\n",
 751     "emul: jmp loop \n",
 752     "      \n",
 753     "end:  set d 0\n",
 754     "\"\"\"\n",
 755     "m = new_machine()\n",
 756     "program_from_listing(program, m)\n",
 757     "run(m)\n",
 758     "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
 759    ]
 760   },
 761   {
 762    "cell_type": "code",
 763    "execution_count": 68,
 764    "metadata": {},
 765    "outputs": [
 766     {
 767      "name": "stdout",
 768      "output_type": "stream",
 769      "text": [
 770       "set c 0\n",
 771       "cpy a d\n",
 772       "jpz b 8\n",
 773       "dec b\n",
 774       "cpy d a\n",
 775       "jpz a 4\n",
 776       "inc c\n",
 777       "dec a\n",
 778       "jmp -3\n",
 779       "jmp -7\n",
 780       "set d 0\n"
 781      ]
 782     }
 783    ],
 784    "source": [
 785     "print('\\n'.join(unlabel_listing(program)))"
 786    ]
 787   },
 788   {
 789    "cell_type": "code",
 790    "execution_count": 27,
 791    "metadata": {},
 792    "outputs": [
 793     {
 794      "name": "stdout",
 795      "output_type": "stream",
 796      "text": [
 797       "set c 0\n",
 798       "cpy a d\n",
 799       "jpz b 8\n",
 800       "dec b\n",
 801       "cpy d a\n",
 802       "jpz a 4\n",
 803       "inc c\n",
 804       "dec a\n",
 805       "jmp -3\n",
 806       "jmp -7\n",
 807       "set d 0\n"
 808      ]
 809     }
 810    ],
 811    "source": [
 812     "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
 813     "instructions = replace_labels(labelled_instructions)\n",
 814     "print('\\n'.join(instructions))"
 815    ]
 816   },
 817   {
 818    "cell_type": "code",
 819    "execution_count": 28,
 820    "metadata": {},
 821    "outputs": [
 822     {
 823      "data": {
 824       "text/plain": [
 825        "'a: 2, b: 0, c: 10, d: 2, pc: 13'"
 826       ]
 827      },
 828      "execution_count": 28,
 829      "metadata": {},
 830      "output_type": "execute_result"
 831     }
 832    ],
 833    "source": [
 834     "# c holds a * b\n",
 835     "program = \"\"\"\n",
 836     "      set a 2\n",
 837     "      set b 5\n",
 838     "      set c 0\n",
 839     "      cpy a d\n",
 840     "loop: jpz b end      \n",
 841     "      dec b\n",
 842     "      cpy d a\n",
 843     "smul: jpz a emul\n",
 844     "      inc c\n",
 845     "      dec a\n",
 846     "      jmp smul\n",
 847     "emul: jmp loop \n",
 848     "      \n",
 849     "end:  cpy d a\n",
 850     "\"\"\"\n",
 851     "m = new_machine()\n",
 852     "program_from_listing(program, m)\n",
 853     "run(m)\n",
 854     "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
 855    ]
 856   },
 857   {
 858    "cell_type": "code",
 859    "execution_count": 29,
 860    "metadata": {},
 861    "outputs": [
 862     {
 863      "name": "stdout",
 864      "output_type": "stream",
 865      "text": [
 866       "set a 2\n",
 867       "set b 5\n",
 868       "set c 0\n",
 869       "cpy a d\n",
 870       "jpz b 8\n",
 871       "dec b\n",
 872       "cpy d a\n",
 873       "jpz a 4\n",
 874       "inc c\n",
 875       "dec a\n",
 876       "jmp -3\n",
 877       "jmp -7\n",
 878       "cpy d a\n"
 879      ]
 880     }
 881    ],
 882    "source": [
 883     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
 884     "                             if i.strip() \n",
 885     "                             if not i.strip().startswith('#')]\n",
 886     "instructions = replace_labels(labelled_instructions)\n",
 887     "print('\\n'.join(instructions))"
 888    ]
 889   },
 890   {
 891    "cell_type": "code",
 892    "execution_count": 30,
 893    "metadata": {},
 894    "outputs": [
 895     {
 896      "data": {
 897       "text/plain": [
 898        "'a: 52, b: 0, c: 0, d: 0, pc: 48'"
 899       ]
 900      },
 901      "execution_count": 30,
 902      "metadata": {},
 903      "output_type": "execute_result"
 904     }
 905    ],
 906    "source": [
 907     "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
 908     "# Location 2 holds number of steps taken\n",
 909     "# Location 3 holds max value reached\n",
 910     "program = \"\"\"\n",
 911     "      cpy a d\n",
 912     "      \n",
 913     "      set b 0\n",
 914     "      \n",
 915     "      # if a is one, finish, \n",
 916     "main: dec a\n",
 917     "      jpz a end\n",
 918     "      inc a\n",
 919     "      \n",
 920     "      # find parity of a\n",
 921     "      cpy a c\n",
 922     "      set b 0\n",
 923     "prty: dec c\n",
 924     "      jpz b odd\n",
 925     "      dec b\n",
 926     "      jmp prte\n",
 927     "odd:  inc b\n",
 928     "prte: jpz c 2\n",
 929     "      jmp prty\n",
 930     "      \n",
 931     "      # b == 0 means a even; b == 1 means a odd\n",
 932     "      jpz b isev\n",
 933     "\n",
 934     "      # c holds a * 3 + 1\n",
 935     "      cpy a b\n",
 936     "mul:  jpz b emul\n",
 937     "      dec b\n",
 938     "      inc c\n",
 939     "      inc c\n",
 940     "      inc c\n",
 941     "      jmp mul\n",
 942     "emul: inc c\n",
 943     "      cpy c a\n",
 944     "      jmp fin\n",
 945     "      \n",
 946     "      \n",
 947     "isev: set c 0\n",
 948     "      set b 0\n",
 949     "hlvl: dec a\n",
 950     "      jpz b oddh\n",
 951     "      dec b\n",
 952     "      inc c\n",
 953     "      jmp endh\n",
 954     "oddh: inc b\n",
 955     "endh: jpz a 2\n",
 956     "      jmp hlvl\n",
 957     "      cpy c a\n",
 958     "\n",
 959     "fin:  cpy a b\n",
 960     "      cpy d c\n",
 961     "maxc: jpz c this\n",
 962     "      jpz b othr\n",
 963     "      dec b\n",
 964     "      dec c\n",
 965     "      jmp maxc\n",
 966     "this: cpy a d\n",
 967     "othr: jmp main\n",
 968     "      \n",
 969     "      # end of program \n",
 970     "      \n",
 971     "end:  cpy d a\n",
 972     "      set c 0\n",
 973     "      set d 0\n",
 974     "\"\"\"\n",
 975     "# m = new_machine()\n",
 976     "# program_from_listing(program, m)\n",
 977     "# run(m)\n",
 978     "show_machine(execute(program, initial_state={'a': 7}))"
 979    ]
 980   },
 981   {
 982    "cell_type": "code",
 983    "execution_count": 31,
 984    "metadata": {},
 985    "outputs": [
 986     {
 987      "data": {
 988       "text/plain": [
 989        "40"
 990       ]
 991      },
 992      "execution_count": 31,
 993      "metadata": {},
 994      "output_type": "execute_result"
 995     }
 996    ],
 997    "source": [
 998     "13*3+1"
 999    ]
1000   },
1001   {
1002    "cell_type": "code",
1003    "execution_count": 32,
1004    "metadata": {
1005     "collapsed": true
1006    },
1007    "outputs": [],
1008    "source": [
1009     "def max_collatz(start):\n",
1010     "    mc = start\n",
1011     "    i = start\n",
1012     "    while i != 1:\n",
1013     "        if i % 2 == 0:\n",
1014     "            i = i // 2\n",
1015     "        else:\n",
1016     "            i = 3 * i + 1\n",
1017     "        if i > mc:\n",
1018     "            mc = i\n",
1019     "    return mc"
1020    ]
1021   },
1022   {
1023    "cell_type": "code",
1024    "execution_count": 33,
1025    "metadata": {},
1026    "outputs": [
1027     {
1028      "data": {
1029       "text/plain": [
1030        "52"
1031       ]
1032      },
1033      "execution_count": 33,
1034      "metadata": {},
1035      "output_type": "execute_result"
1036     }
1037    ],
1038    "source": [
1039     "max_collatz(7)"
1040    ]
1041   },
1042   {
1043    "cell_type": "code",
1044    "execution_count": 34,
1045    "metadata": {},
1046    "outputs": [
1047     {
1048      "data": {
1049       "text/plain": [
1050        "(250504, 937)"
1051       ]
1052      },
1053      "execution_count": 34,
1054      "metadata": {},
1055      "output_type": "execute_result"
1056     }
1057    ],
1058    "source": [
1059     "max([(max_collatz(i), i) for i in range(1, 1000)])"
1060    ]
1061   },
1062   {
1063    "cell_type": "code",
1064    "execution_count": 36,
1065    "metadata": {
1066     "scrolled": true
1067    },
1068    "outputs": [
1069     {
1070      "data": {
1071       "text/plain": [
1072        "[]"
1073       ]
1074      },
1075      "execution_count": 36,
1076      "metadata": {},
1077      "output_type": "execute_result"
1078     }
1079    ],
1080    "source": [
1081     "ans = []\n",
1082     "for i in range(1, 100):\n",
1083     "    m = execute(program, initial_state={'a': i})\n",
1084     "    c = max_collatz(i)\n",
1085     "    if m['a'] != c:\n",
1086     "        ans += [(i, m['a'], c)]\n",
1087     "ans"
1088    ]
1089   },
1090   {
1091    "cell_type": "code",
1092    "execution_count": 37,
1093    "metadata": {},
1094    "outputs": [
1095     {
1096      "ename": "KeyboardInterrupt",
1097      "evalue": "",
1098      "output_type": "error",
1099      "traceback": [
1100       "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
1101       "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
1102       "\u001b[0;32m<ipython-input-37-a9f4d977edea>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mexecute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprogram\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m'a'\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m937\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
1103       "\u001b[0;32m<ipython-input-18-d22f089366e4>\u001b[0m in \u001b[0;36mexecute\u001b[0;34m(listing, initial_state, trace)\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0mm\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m     \u001b[0mprogram_from_listing\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlisting\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mtrace\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
1104       "\u001b[0;32m<ipython-input-17-5478d48920ba>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(machine, initial_state, trace)\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      3\u001b[0m         \u001b[0mmachine\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupdate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m     \u001b[0;32mwhile\u001b[0m \u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'pc'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'instructions'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      5\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m             \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
1105       "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
1106      ]
1107     }
1108    ],
1109    "source": [
1110     "show_machine(execute(program, initial_state={'a': 937}))"
1111    ]
1112   },
1113   {
1114    "cell_type": "code",
1115    "execution_count": null,
1116    "metadata": {},
1117    "outputs": [],
1118    "source": [
1119     "# labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1120     "#                              if i.strip() \n",
1121     "#                              if not i.strip().startswith('#')]\n",
1122     "# instructions = replace_labels(labelled_instructions)\n",
1123     "# print('\\n'.join(instructions))\n",
1124     "# open('07-program.txt', 'w').write('\\n'.join(instructions))"
1125    ]
1126   },
1127   {
1128    "cell_type": "code",
1129    "execution_count": 58,
1130    "metadata": {},
1131    "outputs": [
1132     {
1133      "data": {
1134       "text/plain": [
1135        "{'a': 0,\n",
1136        " 'b': 3,\n",
1137        " 'c': 0,\n",
1138        " 'd': 0,\n",
1139        " 'instructions': [(<function __main__.dec>, ['a']),\n",
1140        "  (<function __main__.inc>, ['b']),\n",
1141        "  (<function __main__.jpz>, ['a', 2]),\n",
1142        "  (<function __main__.jmp>, [-3])],\n",
1143        " 'pc': 4}"
1144       ]
1145      },
1146      "execution_count": 58,
1147      "metadata": {},
1148      "output_type": "execute_result"
1149     }
1150    ],
1151    "source": [
1152     "# Adds a to b\n",
1153     "program = \"\"\"\n",
1154     "loop: dec a\n",
1155     "      inc b\n",
1156     "      jpz a 2\n",
1157     "      jmp loop\n",
1158     "\"\"\"\n",
1159     "execute(program, initial_state={'a': 3})"
1160    ]
1161   },
1162   {
1163    "cell_type": "code",
1164    "execution_count": 59,
1165    "metadata": {},
1166    "outputs": [
1167     {
1168      "name": "stdout",
1169      "output_type": "stream",
1170      "text": [
1171       "dec a\n",
1172       "inc b\n",
1173       "jpz a 2\n",
1174       "jmp -3\n"
1175      ]
1176     }
1177    ],
1178    "source": [
1179     "print('\\n'.join(unlabel_listing(program)))"
1180    ]
1181   },
1182   {
1183    "cell_type": "code",
1184    "execution_count": 55,
1185    "metadata": {},
1186    "outputs": [
1187     {
1188      "data": {
1189       "text/plain": [
1190        "{'a': 0,\n",
1191        " 'b': 7,\n",
1192        " 'c': 0,\n",
1193        " 'd': 0,\n",
1194        " 'instructions': [(<function __main__.dec>, ['a']),\n",
1195        "  (<function __main__.inc>, ['b']),\n",
1196        "  (<function __main__.jpz>, ['a', 2]),\n",
1197        "  (<function __main__.jmp>, [-3])],\n",
1198        " 'pc': 4}"
1199       ]
1200      },
1201      "execution_count": 55,
1202      "metadata": {},
1203      "output_type": "execute_result"
1204     }
1205    ],
1206    "source": [
1207     "# Adds a to b\n",
1208     "program = \"\"\"\n",
1209     "loop: dec a\n",
1210     "      inc b\n",
1211     "      jpz a 2\n",
1212     "      jmp loop\n",
1213     "\"\"\"\n",
1214     "execute(program, initial_state={'a': 3, 'b': 4})"
1215    ]
1216   },
1217   {
1218    "cell_type": "code",
1219    "execution_count": 61,
1220    "metadata": {},
1221    "outputs": [
1222     {
1223      "data": {
1224       "text/plain": [
1225        "{'a': 4,\n",
1226        " 'b': 8,\n",
1227        " 'c': 0,\n",
1228        " 'd': 0,\n",
1229        " 'instructions': [(<function __main__.set_literal>, ['b', 0]),\n",
1230        "  (<function __main__.set_literal>, ['c', 0]),\n",
1231        "  (<function __main__.jpz>, ['a', 11]),\n",
1232        "  (<function __main__.dec>, ['a']),\n",
1233        "  (<function __main__.inc>, ['b']),\n",
1234        "  (<function __main__.inc>, ['b']),\n",
1235        "  (<function __main__.inc>, ['c']),\n",
1236        "  (<function __main__.jpz>, ['a', 2]),\n",
1237        "  (<function __main__.jmp>, [-5]),\n",
1238        "  (<function __main__.dec>, ['c']),\n",
1239        "  (<function __main__.inc>, ['a']),\n",
1240        "  (<function __main__.jpz>, ['c', 2]),\n",
1241        "  (<function __main__.jmp>, [-3]),\n",
1242        "  (<function __main__.set_literal>, ['c', 0])],\n",
1243        " 'pc': 14}"
1244       ]
1245      },
1246      "execution_count": 61,
1247      "metadata": {},
1248      "output_type": "execute_result"
1249     }
1250    ],
1251    "source": [
1252     "# Puts double a in b, leaves a unchanged\n",
1253     "program = \"\"\"\n",
1254     "      set b 0\n",
1255     "      set c 0\n",
1256     "      jpz a end\n",
1257     "loop: dec a\n",
1258     "      inc b\n",
1259     "      inc b\n",
1260     "      inc c\n",
1261     "      jpz a 2\n",
1262     "      jmp loop\n",
1263     "lp2:  dec c\n",
1264     "      inc a\n",
1265     "      jpz c 2\n",
1266     "      jmp lp2\n",
1267     "end:  set c 0      \n",
1268     "\"\"\"\n",
1269     "execute(program, initial_state={'a': 4})"
1270    ]
1271   },
1272   {
1273    "cell_type": "code",
1274    "execution_count": 62,
1275    "metadata": {},
1276    "outputs": [
1277     {
1278      "name": "stdout",
1279      "output_type": "stream",
1280      "text": [
1281       "set b 0\n",
1282       "set c 0\n",
1283       "jpz a 11\n",
1284       "dec a\n",
1285       "inc b\n",
1286       "inc b\n",
1287       "inc c\n",
1288       "jpz a 2\n",
1289       "jmp -5\n",
1290       "dec c\n",
1291       "inc a\n",
1292       "jpz c 2\n",
1293       "jmp -3\n",
1294       "set c 0\n"
1295      ]
1296     }
1297    ],
1298    "source": [
1299     "print('\\n'.join(unlabel_listing(program)))"
1300    ]
1301   },
1302   {
1303    "cell_type": "code",
1304    "execution_count": null,
1305    "metadata": {
1306     "collapsed": true
1307    },
1308    "outputs": [],
1309    "source": []
1310   }
1311  ],
1312  "metadata": {
1313   "kernelspec": {
1314    "display_name": "Python 3",
1315    "language": "python",
1316    "name": "python3"
1317   },
1318   "language_info": {
1319    "codemirror_mode": {
1320     "name": "ipython",
1321     "version": 3
1322    },
1323    "file_extension": ".py",
1324    "mimetype": "text/x-python",
1325    "name": "python",
1326    "nbconvert_exporter": "python",
1327    "pygments_lexer": "ipython3",
1328    "version": "3.5.2+"
1329   }
1330  },
1331  "nbformat": 4,
1332  "nbformat_minor": 2
1333 }