07-interpreter/machine-code.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     "Three registers, `a`, `b`, and `c`. \n",
  12     "Program counter, `pc`.\n",
  13     "Unlimited memory in numbered addresses, completely separate from program storage.\n",
  14     "\n",
  15     "Each register and memory location can hold 8-byte integers (Java `long`s).\n",
  16     "\n",
  17     "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
  18     "\n",
  19     "`jmp` and `jpz` override this normal change in `pc`.\n",
  20     "\n",
  21     "| Instruction | Description |\n",
  22     "|:------------|:------------|\n",
  23     "| `inc r`     | increment contents of register `r` |\n",
  24     "| `dec r`     | decrement contents of register `r` |\n",
  25     "| `set r i`   | set contents of register `r` to literal value `i` |\n",
  26     "| `cpy r s`   | set contents of register `r` into register `s` | \n",
  27     "| `sto r m`   | store contents of register `r` into memory location `m` |\n",
  28     "| `ld r m`    | load contents of memory location `m` into register `r` |\n",
  29     "| `jmp i`     | jump to instruction `i` places forward |\n",
  30     "| `jpz r i`   | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
  31     "\n",
  32     "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."
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 1,
  38    "metadata": {
  39     "collapsed": true
  40    },
  41    "outputs": [],
  42    "source": [
  43     "def new_machine():\n",
  44     "    return {'pc': 0, \n",
  45     "            'a': 0,\n",
  46     "            'b': 0, \n",
  47     "            'c': 0,\n",
  48     "            'instructions': []}"
  49    ]
  50   },
  51   {
  52    "cell_type": "code",
  53    "execution_count": 2,
  54    "metadata": {
  55     "collapsed": true
  56    },
  57    "outputs": [],
  58    "source": [
  59     "def show_machine(machine):\n",
  60     "    return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
  61     "                     for sk in sorted(str(k) for k in machine)\n",
  62     "                     if sk != 'instructions')"
  63    ]
  64   },
  65   {
  66    "cell_type": "code",
  67    "execution_count": 3,
  68    "metadata": {
  69     "collapsed": true
  70    },
  71    "outputs": [],
  72    "source": [
  73     "def inc(reg, machine):\n",
  74     "    machine[reg] += 1\n",
  75     "    machine['pc'] += 1"
  76    ]
  77   },
  78   {
  79    "cell_type": "code",
  80    "execution_count": 4,
  81    "metadata": {
  82     "collapsed": true
  83    },
  84    "outputs": [],
  85    "source": [
  86     "def dec(reg, machine):\n",
  87     "    machine[reg] -= 1\n",
  88     "    machine['pc'] += 1"
  89    ]
  90   },
  91   {
  92    "cell_type": "code",
  93    "execution_count": 5,
  94    "metadata": {
  95     "collapsed": true
  96    },
  97    "outputs": [],
  98    "source": [
  99     "def jmp(addr, machine):\n",
 100     "    machine['pc'] += addr"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 6,
 106    "metadata": {
 107     "collapsed": true
 108    },
 109    "outputs": [],
 110    "source": [
 111     "def jpz(reg, addr, machine):\n",
 112     "    if machine[reg] == 0:\n",
 113     "        machine['pc'] += addr\n",
 114     "    else:\n",
 115     "        machine['pc'] += 1"
 116    ]
 117   },
 118   {
 119    "cell_type": "code",
 120    "execution_count": 7,
 121    "metadata": {
 122     "collapsed": true
 123    },
 124    "outputs": [],
 125    "source": [
 126     "def set_literal(reg, literal, machine):\n",
 127     "    machine[reg] = literal\n",
 128     "    machine['pc'] += 1"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 8,
 134    "metadata": {
 135     "collapsed": true
 136    },
 137    "outputs": [],
 138    "source": [
 139     "def cpy(from_reg, to_reg, machine):\n",
 140     "    machine[to_reg] = machine[from_reg]\n",
 141     "    machine['pc'] += 1"
 142    ]
 143   },
 144   {
 145    "cell_type": "code",
 146    "execution_count": 9,
 147    "metadata": {
 148     "collapsed": true
 149    },
 150    "outputs": [],
 151    "source": [
 152     "def sto(reg, addr, machine):\n",
 153     "    machine[addr] = machine[reg]\n",
 154     "    machine['pc'] += 1"
 155    ]
 156   },
 157   {
 158    "cell_type": "code",
 159    "execution_count": 10,
 160    "metadata": {
 161     "collapsed": true
 162    },
 163    "outputs": [],
 164    "source": [
 165     "def ld(reg, addr, machine):\n",
 166     "    if addr in machine:\n",
 167     "        machine[reg] = machine[addr]\n",
 168     "    else:\n",
 169     "        machine[reg] = 0\n",
 170     "    machine['pc'] += 1"
 171    ]
 172   },
 173   {
 174    "cell_type": "code",
 175    "execution_count": 11,
 176    "metadata": {
 177     "collapsed": true
 178    },
 179    "outputs": [],
 180    "source": [
 181     "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
 182     "                    'jpz': jpz, 'set': set_literal, 'cpy': cpy,\n",
 183     "                    'sto': sto, 'ld': ld}\n",
 184     "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
 185    ]
 186   },
 187   {
 188    "cell_type": "code",
 189    "execution_count": 12,
 190    "metadata": {
 191     "collapsed": true
 192    },
 193    "outputs": [],
 194    "source": [
 195     "def parse(instruction):\n",
 196     "    words = instruction.split()\n",
 197     "    instr = words[0]\n",
 198     "    args = words[1:]\n",
 199     "    if instr in numeric_args_table:\n",
 200     "        for p in numeric_args_table[instr]:\n",
 201     "            args[p] = int(args[p])\n",
 202     "    return instruction_table[instr], args"
 203    ]
 204   },
 205   {
 206    "cell_type": "code",
 207    "execution_count": 13,
 208    "metadata": {},
 209    "outputs": [
 210     {
 211      "data": {
 212       "text/plain": [
 213        "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
 214       ]
 215      },
 216      "execution_count": 13,
 217      "metadata": {},
 218      "output_type": "execute_result"
 219     }
 220    ],
 221    "source": [
 222     "m = new_machine()\n",
 223     "inc('a', m)\n",
 224     "cargs = ['a', 'b']\n",
 225     "cpy(*cargs, m)\n",
 226     "inc('a', m)\n",
 227     "m"
 228    ]
 229   },
 230   {
 231    "cell_type": "code",
 232    "execution_count": 14,
 233    "metadata": {
 234     "collapsed": true
 235    },
 236    "outputs": [],
 237    "source": [
 238     "def program_from_instructions(prog, machine):\n",
 239     "    machine['instructions'] = [parse(instr) for instr in prog]"
 240    ]
 241   },
 242   {
 243    "cell_type": "code",
 244    "execution_count": 15,
 245    "metadata": {
 246     "collapsed": true
 247    },
 248    "outputs": [],
 249    "source": [
 250     "def program_from_listing(listing, machine):\n",
 251     "    labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
 252     "                             if i.strip() \n",
 253     "                             if not i.strip().startswith('#')]\n",
 254     "    instructions = replace_labels(labelled_instructions)\n",
 255     "    program_from_instructions(instructions, machine)"
 256    ]
 257   },
 258   {
 259    "cell_type": "code",
 260    "execution_count": 16,
 261    "metadata": {
 262     "collapsed": true
 263    },
 264    "outputs": [],
 265    "source": [
 266     "def replace_labels(listing):\n",
 267     "    locations = {}\n",
 268     "    for n, i in enumerate(listing):\n",
 269     "        if ':' in i:\n",
 270     "            locations[i.split(':')[0]] = n\n",
 271     "\n",
 272     "    unlabelled_listing = []\n",
 273     "    for n, i in enumerate(listing):\n",
 274     "        instr = i.split()\n",
 275     "        if ':' in i:\n",
 276     "            instr = i.split(':')[1].split()\n",
 277     "        else:\n",
 278     "            instr = i.split()\n",
 279     "        terms = []\n",
 280     "        for term in instr:\n",
 281     "            if term in locations:\n",
 282     "                terms += [str(locations[term] - n)]\n",
 283     "            else:\n",
 284     "                terms += [term]\n",
 285     "        transformed_instr = ' '.join(terms)\n",
 286     "        unlabelled_listing += [transformed_instr]\n",
 287     "        \n",
 288     "    return unlabelled_listing    "
 289    ]
 290   },
 291   {
 292    "cell_type": "code",
 293    "execution_count": 17,
 294    "metadata": {},
 295    "outputs": [
 296     {
 297      "data": {
 298       "text/plain": [
 299        "['inc', 'a']"
 300       ]
 301      },
 302      "execution_count": 17,
 303      "metadata": {},
 304      "output_type": "execute_result"
 305     }
 306    ],
 307    "source": [
 308     "'fred: inc a'.split(':')[1].split()"
 309    ]
 310   },
 311   {
 312    "cell_type": "code",
 313    "execution_count": 18,
 314    "metadata": {},
 315    "outputs": [
 316     {
 317      "name": "stdout",
 318      "output_type": "stream",
 319      "text": [
 320       "set a 10\n",
 321       "dec a\n",
 322       "inc b\n",
 323       "sto b 1\n",
 324       "jpz a 2\n",
 325       "jmp -4\n"
 326      ]
 327     }
 328    ],
 329    "source": [
 330     "program = \"\"\"\n",
 331     "      set a 10\n",
 332     "      # comment line\n",
 333     "      \n",
 334     "loop: dec a\n",
 335     "      inc b\n",
 336     "      sto b 1\n",
 337     "      jpz a 2\n",
 338     "      jmp loop\n",
 339     "\"\"\"\n",
 340     "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
 341     "instructions = replace_labels(labelled_instructions)\n",
 342     "print('\\n'.join(instructions))"
 343    ]
 344   },
 345   {
 346    "cell_type": "code",
 347    "execution_count": 19,
 348    "metadata": {
 349     "collapsed": true
 350    },
 351    "outputs": [],
 352    "source": [
 353     "def run(machine, initial_state=None, trace=False):\n",
 354     "    if initial_state:\n",
 355     "        machine.update(initial_state)\n",
 356     "    while machine['pc'] < len(machine['instructions']):\n",
 357     "        if trace:\n",
 358     "            print(show_machine(machine))\n",
 359     "        cmd, args = machine['instructions'][machine['pc']]\n",
 360     "        cmd(*args, machine)"
 361    ]
 362   },
 363   {
 364    "cell_type": "code",
 365    "execution_count": 20,
 366    "metadata": {
 367     "collapsed": true
 368    },
 369    "outputs": [],
 370    "source": [
 371     "def execute(listing, initial_state=None, trace=False):\n",
 372     "    m = new_machine()\n",
 373     "    program_from_listing(listing, m)\n",
 374     "    run(m, initial_state=initial_state, trace=trace)\n",
 375     "    return m"
 376    ]
 377   },
 378   {
 379    "cell_type": "code",
 380    "execution_count": 21,
 381    "metadata": {},
 382    "outputs": [
 383     {
 384      "data": {
 385       "text/plain": [
 386        "{'a': 3,\n",
 387        " 'b': 2,\n",
 388        " 'c': 0,\n",
 389        " 'instructions': [(<function __main__.inc>, ['a']),\n",
 390        "  (<function __main__.inc>, ['a']),\n",
 391        "  (<function __main__.cpy>, ['a', 'b']),\n",
 392        "  (<function __main__.inc>, ['a'])],\n",
 393        " 'pc': 4}"
 394       ]
 395      },
 396      "execution_count": 21,
 397      "metadata": {},
 398      "output_type": "execute_result"
 399     }
 400    ],
 401    "source": [
 402     "program = \"\"\"\n",
 403     "inc a\n",
 404     "inc a\n",
 405     "cpy a b\n",
 406     "inc a\n",
 407     "\"\"\"\n",
 408     "execute(program)"
 409    ]
 410   },
 411   {
 412    "cell_type": "code",
 413    "execution_count": 22,
 414    "metadata": {},
 415    "outputs": [
 416     {
 417      "data": {
 418       "text/plain": [
 419        "{1: 10,\n",
 420        " 'a': 0,\n",
 421        " 'c': 20,\n",
 422        " 'pc': 6,\n",
 423        " 'b': 10,\n",
 424        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 425        "  (<function __main__.dec>, ['a']),\n",
 426        "  (<function __main__.inc>, ['b']),\n",
 427        "  (<function __main__.sto>, ['b', 1]),\n",
 428        "  (<function __main__.jpz>, ['a', 2]),\n",
 429        "  (<function __main__.jmp>, [-4])]}"
 430       ]
 431      },
 432      "execution_count": 22,
 433      "metadata": {},
 434      "output_type": "execute_result"
 435     }
 436    ],
 437    "source": [
 438     "program = \"\"\"\n",
 439     "set a 10\n",
 440     "dec a\n",
 441     "inc b\n",
 442     "sto b 1\n",
 443     "jpz a 2\n",
 444     "jmp -4\n",
 445     "\"\"\"\n",
 446     "# m = new_machine()\n",
 447     "# program_from_listing(program, m)\n",
 448     "# run(m)\n",
 449     "execute(program, initial_state={'c': 20})"
 450    ]
 451   },
 452   {
 453    "cell_type": "code",
 454    "execution_count": 23,
 455    "metadata": {},
 456    "outputs": [
 457     {
 458      "data": {
 459       "text/plain": [
 460        "{1: 10,\n",
 461        " 'a': 0,\n",
 462        " 'c': 20,\n",
 463        " 'pc': 6,\n",
 464        " 'b': 10,\n",
 465        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 466        "  (<function __main__.dec>, ['a']),\n",
 467        "  (<function __main__.inc>, ['b']),\n",
 468        "  (<function __main__.sto>, ['b', 1]),\n",
 469        "  (<function __main__.jpz>, ['a', 2]),\n",
 470        "  (<function __main__.jmp>, [-4])]}"
 471       ]
 472      },
 473      "execution_count": 23,
 474      "metadata": {},
 475      "output_type": "execute_result"
 476     }
 477    ],
 478    "source": [
 479     "program = \"\"\"\n",
 480     "      set a 10\n",
 481     "loop: dec a\n",
 482     "      inc b\n",
 483     "      sto b 1\n",
 484     "      jpz a 2\n",
 485     "      jmp loop\n",
 486     "\"\"\"\n",
 487     "execute(program, initial_state={'c': 20})"
 488    ]
 489   },
 490   {
 491    "cell_type": "code",
 492    "execution_count": 24,
 493    "metadata": {},
 494    "outputs": [
 495     {
 496      "data": {
 497       "text/plain": [
 498        "{'a': 0,\n",
 499        " 'b': 1,\n",
 500        " 'c': 5,\n",
 501        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 502        "  (<function __main__.set_literal>, ['b', 0]),\n",
 503        "  (<function __main__.dec>, ['a']),\n",
 504        "  (<function __main__.jpz>, ['b', 3]),\n",
 505        "  (<function __main__.dec>, ['b']),\n",
 506        "  (<function __main__.jmp>, [2]),\n",
 507        "  (<function __main__.inc>, ['b']),\n",
 508        "  (<function __main__.jpz>, ['a', 3]),\n",
 509        "  (<function __main__.jmp>, [-6])],\n",
 510        " 'pc': 10}"
 511       ]
 512      },
 513      "execution_count": 24,
 514      "metadata": {},
 515      "output_type": "execute_result"
 516     }
 517    ],
 518    "source": [
 519     "program = \"\"\"\n",
 520     "cpy c a\n",
 521     "set b 0\n",
 522     "dec a\n",
 523     "jpz b 3\n",
 524     "dec b\n",
 525     "jmp 2\n",
 526     "inc b\n",
 527     "jpz a 3\n",
 528     "jmp -6\n",
 529     "\"\"\"\n",
 530     "# m = new_machine()\n",
 531     "# program_from_listing(program, m)\n",
 532     "# run(m)\n",
 533     "execute(program, initial_state={'c': 5})"
 534    ]
 535   },
 536   {
 537    "cell_type": "code",
 538    "execution_count": 25,
 539    "metadata": {},
 540    "outputs": [
 541     {
 542      "data": {
 543       "text/plain": [
 544        "{'a': 0,\n",
 545        " 'b': 1,\n",
 546        " 'c': 5,\n",
 547        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 548        "  (<function __main__.set_literal>, ['b', 0]),\n",
 549        "  (<function __main__.dec>, ['a']),\n",
 550        "  (<function __main__.jpz>, ['b', 3]),\n",
 551        "  (<function __main__.dec>, ['b']),\n",
 552        "  (<function __main__.jmp>, [2]),\n",
 553        "  (<function __main__.inc>, ['b']),\n",
 554        "  (<function __main__.jpz>, ['a', 2]),\n",
 555        "  (<function __main__.jmp>, [-6])],\n",
 556        " 'pc': 9}"
 557       ]
 558      },
 559      "execution_count": 25,
 560      "metadata": {},
 561      "output_type": "execute_result"
 562     }
 563    ],
 564    "source": [
 565     "# b holds parity of number in c: (c % 2)\n",
 566     "program = \"\"\"\n",
 567     "      cpy c a\n",
 568     "      set b 0\n",
 569     "loop: dec a\n",
 570     "      jpz b odd\n",
 571     "      dec b\n",
 572     "      jmp end\n",
 573     "odd:  inc b\n",
 574     "end:  jpz a 2\n",
 575     "      jmp loop\n",
 576     "\"\"\"\n",
 577     "# m = new_machine()\n",
 578     "# program_from_listing(program, m)\n",
 579     "# run(m)\n",
 580     "execute(program, initial_state={'c': 5})"
 581    ]
 582   },
 583   {
 584    "cell_type": "code",
 585    "execution_count": 26,
 586    "metadata": {},
 587    "outputs": [
 588     {
 589      "data": {
 590       "text/plain": [
 591        "'1: 8, a: 0, b: 1, c: 8, pc: 11'"
 592       ]
 593      },
 594      "execution_count": 26,
 595      "metadata": {},
 596      "output_type": "execute_result"
 597     }
 598    ],
 599    "source": [
 600     "# c holds floor(a/2)\n",
 601     "program = \"\"\"\n",
 602     "      set c 0\n",
 603     "      set b 0\n",
 604     "loop: dec a\n",
 605     "      jpz b odd\n",
 606     "      dec b\n",
 607     "      inc c\n",
 608     "      jmp end\n",
 609     "odd:  inc b\n",
 610     "end:  jpz a 2\n",
 611     "      jmp loop\n",
 612     "      sto c 1\n",
 613     "\"\"\"\n",
 614     "# m = new_machine()\n",
 615     "# program_from_listing(program, m)\n",
 616     "# run(m)\n",
 617     "show_machine(execute(program, initial_state={'a': 17}))"
 618    ]
 619   },
 620   {
 621    "cell_type": "code",
 622    "execution_count": 27,
 623    "metadata": {},
 624    "outputs": [
 625     {
 626      "data": {
 627       "text/plain": [
 628        "'a: 4, b: 0, c: 12, pc: 9'"
 629       ]
 630      },
 631      "execution_count": 27,
 632      "metadata": {},
 633      "output_type": "execute_result"
 634     }
 635    ],
 636    "source": [
 637     "# c holds a * 3\n",
 638     "program = \"\"\"\n",
 639     "      set c 0\n",
 640     "      cpy a b\n",
 641     "      # start of main loop\n",
 642     "loop: jpz b end\n",
 643     "      dec b\n",
 644     "      inc c\n",
 645     "      inc c\n",
 646     "      inc c\n",
 647     "      jmp loop\n",
 648     "      \n",
 649     "      # end of program \n",
 650     "      \n",
 651     "end:  jmp 1\n",
 652     "\"\"\"\n",
 653     "# m = new_machine()\n",
 654     "# program_from_listing(program, m)\n",
 655     "# run(m)\n",
 656     "show_machine(execute(program, initial_state={'a': 4}))"
 657    ]
 658   },
 659   {
 660    "cell_type": "code",
 661    "execution_count": 48,
 662    "metadata": {},
 663    "outputs": [
 664     {
 665      "data": {
 666       "text/plain": [
 667        "'1: 0, a: 0, b: 0, c: 27, pc: 11'"
 668       ]
 669      },
 670      "execution_count": 48,
 671      "metadata": {},
 672      "output_type": "execute_result"
 673     }
 674    ],
 675    "source": [
 676     "# c holds a * b\n",
 677     "program = \"\"\"\n",
 678     "      set c 0\n",
 679     "      sto a 1\n",
 680     "loop: jpz b end      \n",
 681     "      dec b\n",
 682     "      ld a 1\n",
 683     "smul: jpz a emul\n",
 684     "      inc c\n",
 685     "      dec a\n",
 686     "      jmp smul\n",
 687     "emul: jmp loop \n",
 688     "      \n",
 689     "end:  sto a 1\n",
 690     "\"\"\"\n",
 691     "m = new_machine()\n",
 692     "program_from_listing(program, m)\n",
 693     "run(m)\n",
 694     "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
 695    ]
 696   },
 697   {
 698    "cell_type": "code",
 699    "execution_count": 49,
 700    "metadata": {},
 701    "outputs": [
 702     {
 703      "name": "stdout",
 704      "output_type": "stream",
 705      "text": [
 706       "set c 0\n",
 707       "sto a 1\n",
 708       "jpz b 8\n",
 709       "dec b\n",
 710       "ld a 1\n",
 711       "jpz a 4\n",
 712       "inc c\n",
 713       "dec a\n",
 714       "jmp -3\n",
 715       "jmp -7\n",
 716       "sto a 1\n"
 717      ]
 718     }
 719    ],
 720    "source": [
 721     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
 722     "                             if i.strip() \n",
 723     "                             if not i.strip().startswith('#')]\n",
 724     "instructions = replace_labels(labelled_instructions)\n",
 725     "print('\\n'.join(instructions))"
 726    ]
 727   },
 728   {
 729    "cell_type": "code",
 730    "execution_count": 51,
 731    "metadata": {},
 732    "outputs": [
 733     {
 734      "data": {
 735       "text/plain": [
 736        "'1: 0, a: 52, b: 0, c: 0, pc: 48'"
 737       ]
 738      },
 739      "execution_count": 51,
 740      "metadata": {},
 741      "output_type": "execute_result"
 742     }
 743    ],
 744    "source": [
 745     "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
 746     "# Location 2 holds number of steps taken\n",
 747     "# Location 3 holds max value reached\n",
 748     "program = \"\"\"\n",
 749     "      sto a 1\n",
 750     "      \n",
 751     "      set b 0\n",
 752     "      \n",
 753     "      # if a is one, finish, \n",
 754     "main: dec a\n",
 755     "      jpz a end\n",
 756     "      inc a\n",
 757     "      \n",
 758     "      # find parity of a\n",
 759     "      cpy a c\n",
 760     "      set b 0\n",
 761     "prty: dec c\n",
 762     "      jpz b odd\n",
 763     "      dec b\n",
 764     "      jmp prte\n",
 765     "odd:  inc b\n",
 766     "prte: jpz c 2\n",
 767     "      jmp prty\n",
 768     "      \n",
 769     "      # b == 0 means a even; b == 1 means a odd\n",
 770     "      jpz b isev\n",
 771     "\n",
 772     "      # c holds a * 3 + 1\n",
 773     "      cpy a b\n",
 774     "mul:  jpz b emul\n",
 775     "      dec b\n",
 776     "      inc c\n",
 777     "      inc c\n",
 778     "      inc c\n",
 779     "      jmp mul\n",
 780     "emul: inc c\n",
 781     "      cpy c a\n",
 782     "      jmp fin\n",
 783     "      \n",
 784     "      \n",
 785     "isev: set c 0\n",
 786     "      set b 0\n",
 787     "hlvl: dec a\n",
 788     "      jpz b oddh\n",
 789     "      dec b\n",
 790     "      inc c\n",
 791     "      jmp endh\n",
 792     "oddh: inc b\n",
 793     "endh: jpz a 2\n",
 794     "      jmp hlvl\n",
 795     "      cpy c a\n",
 796     "\n",
 797     "fin:  cpy a b\n",
 798     "      ld  c 1\n",
 799     "maxc: jpz c this\n",
 800     "      jpz b othr\n",
 801     "      dec b\n",
 802     "      dec c\n",
 803     "      jmp maxc\n",
 804     "this: sto a 1\n",
 805     "othr: jmp main\n",
 806     "      \n",
 807     "      # end of program \n",
 808     "      \n",
 809     "end:  ld a 1\n",
 810     "      set c 0\n",
 811     "      sto c 1\n",
 812     "\"\"\"\n",
 813     "# m = new_machine()\n",
 814     "# program_from_listing(program, m)\n",
 815     "# run(m)\n",
 816     "show_machine(execute(program, initial_state={'a': 7}))"
 817    ]
 818   },
 819   {
 820    "cell_type": "code",
 821    "execution_count": 30,
 822    "metadata": {},
 823    "outputs": [
 824     {
 825      "data": {
 826       "text/plain": [
 827        "40"
 828       ]
 829      },
 830      "execution_count": 30,
 831      "metadata": {},
 832      "output_type": "execute_result"
 833     }
 834    ],
 835    "source": [
 836     "13*3+1"
 837    ]
 838   },
 839   {
 840    "cell_type": "code",
 841    "execution_count": 31,
 842    "metadata": {
 843     "collapsed": true
 844    },
 845    "outputs": [],
 846    "source": [
 847     "def max_collatz(start):\n",
 848     "    mc = start\n",
 849     "    i = start\n",
 850     "    while i != 1:\n",
 851     "        if i % 2 == 0:\n",
 852     "            i = i // 2\n",
 853     "        else:\n",
 854     "            i = 3 * i + 1\n",
 855     "        if i > mc:\n",
 856     "            mc = i\n",
 857     "    return mc"
 858    ]
 859   },
 860   {
 861    "cell_type": "code",
 862    "execution_count": 32,
 863    "metadata": {},
 864    "outputs": [
 865     {
 866      "data": {
 867       "text/plain": [
 868        "52"
 869       ]
 870      },
 871      "execution_count": 32,
 872      "metadata": {},
 873      "output_type": "execute_result"
 874     }
 875    ],
 876    "source": [
 877     "max_collatz(7)"
 878    ]
 879   },
 880   {
 881    "cell_type": "code",
 882    "execution_count": 33,
 883    "metadata": {},
 884    "outputs": [
 885     {
 886      "data": {
 887       "text/plain": [
 888        "(250504, 937)"
 889       ]
 890      },
 891      "execution_count": 33,
 892      "metadata": {},
 893      "output_type": "execute_result"
 894     }
 895    ],
 896    "source": [
 897     "max([(max_collatz(i), i) for i in range(1, 1000)])"
 898    ]
 899   },
 900   {
 901    "cell_type": "code",
 902    "execution_count": 34,
 903    "metadata": {},
 904    "outputs": [
 905     {
 906      "data": {
 907       "text/plain": [
 908        "[]"
 909       ]
 910      },
 911      "execution_count": 34,
 912      "metadata": {},
 913      "output_type": "execute_result"
 914     }
 915    ],
 916    "source": [
 917     "ans = []\n",
 918     "for i in range(1, 100):\n",
 919     "    m = execute(program, initial_state={'a': i})\n",
 920     "    c = max_collatz(i)\n",
 921     "    if m[1] != c:\n",
 922     "        ans += [(i, m[1], c)]\n",
 923     "ans"
 924    ]
 925   },
 926   {
 927    "cell_type": "code",
 928    "execution_count": 52,
 929    "metadata": {},
 930    "outputs": [
 931     {
 932      "data": {
 933       "text/plain": [
 934        "'1: 0, a: 250504, b: 0, c: 0, pc: 48'"
 935       ]
 936      },
 937      "execution_count": 52,
 938      "metadata": {},
 939      "output_type": "execute_result"
 940     }
 941    ],
 942    "source": [
 943     "show_machine(execute(program, initial_state={'a': 937}))"
 944    ]
 945   },
 946   {
 947    "cell_type": "code",
 948    "execution_count": 53,
 949    "metadata": {},
 950    "outputs": [
 951     {
 952      "name": "stdout",
 953      "output_type": "stream",
 954      "text": [
 955       "sto a 1\n",
 956       "set b 0\n",
 957       "dec a\n",
 958       "jpz a 42\n",
 959       "inc a\n",
 960       "cpy a c\n",
 961       "set b 0\n",
 962       "dec c\n",
 963       "jpz b 3\n",
 964       "dec b\n",
 965       "jmp 2\n",
 966       "inc b\n",
 967       "jpz c 2\n",
 968       "jmp -6\n",
 969       "jpz b 11\n",
 970       "cpy a b\n",
 971       "jpz b 6\n",
 972       "dec b\n",
 973       "inc c\n",
 974       "inc c\n",
 975       "inc c\n",
 976       "jmp -5\n",
 977       "inc c\n",
 978       "cpy c a\n",
 979       "jmp 12\n",
 980       "set c 0\n",
 981       "set b 0\n",
 982       "dec a\n",
 983       "jpz b 4\n",
 984       "dec b\n",
 985       "inc c\n",
 986       "jmp 2\n",
 987       "inc b\n",
 988       "jpz a 2\n",
 989       "jmp -7\n",
 990       "cpy c a\n",
 991       "cpy a b\n",
 992       "ld c 1\n",
 993       "jpz c 5\n",
 994       "jpz b 5\n",
 995       "dec b\n",
 996       "dec c\n",
 997       "jmp -4\n",
 998       "sto a 1\n",
 999       "jmp -42\n",
1000       "ld a 1\n",
1001       "set c 0\n",
1002       "sto c 1\n"
1003      ]
1004     },
1005     {
1006      "data": {
1007       "text/plain": [
1008        "342"
1009       ]
1010      },
1011      "execution_count": 53,
1012      "metadata": {},
1013      "output_type": "execute_result"
1014     }
1015    ],
1016    "source": [
1017     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1018     "                             if i.strip() \n",
1019     "                             if not i.strip().startswith('#')]\n",
1020     "instructions = replace_labels(labelled_instructions)\n",
1021     "print('\\n'.join(instructions))\n",
1022     "open('07-program.txt', 'w').write('\\n'.join(instructions))"
1023    ]
1024   },
1025   {
1026    "cell_type": "code",
1027    "execution_count": null,
1028    "metadata": {
1029     "collapsed": true
1030    },
1031    "outputs": [],
1032    "source": []
1033   }
1034  ],
1035  "metadata": {
1036   "kernelspec": {
1037    "display_name": "Python 3",
1038    "language": "python",
1039    "name": "python3"
1040   },
1041   "language_info": {
1042    "codemirror_mode": {
1043     "name": "ipython",
1044     "version": 3
1045    },
1046    "file_extension": ".py",
1047    "mimetype": "text/x-python",
1048    "name": "python",
1049    "nbconvert_exporter": "python",
1050    "pygments_lexer": "ipython3",
1051    "version": "3.5.2+"
1052   }
1053  },
1054  "nbformat": 4,
1055  "nbformat_minor": 2
1056 }