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": 42,
 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": 39,
 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": 40,
 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        "{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 420        "  (<function __main__.dec>, ['a']),\n",
 421        "  (<function __main__.inc>, ['b']),\n",
 422        "  (<function __main__.sto>, ['b', 1]),\n",
 423        "  (<function __main__.jpz>, ['a', 2]),\n",
 424        "  (<function __main__.jmp>, [-4])],\n",
 425        " 1: 10,\n",
 426        " 'c': 20,\n",
 427        " 'a': 0,\n",
 428        " 'pc': 6,\n",
 429        " 'b': 10}"
 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        "{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 461        "  (<function __main__.dec>, ['a']),\n",
 462        "  (<function __main__.inc>, ['b']),\n",
 463        "  (<function __main__.sto>, ['b', 1]),\n",
 464        "  (<function __main__.jpz>, ['a', 2]),\n",
 465        "  (<function __main__.jmp>, [-4])],\n",
 466        " 1: 10,\n",
 467        " 'c': 20,\n",
 468        " 'a': 0,\n",
 469        " 'pc': 6,\n",
 470        " 'b': 10}"
 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": 85,
 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": 85,
 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": 43,
 623    "metadata": {},
 624    "outputs": [
 625     {
 626      "data": {
 627       "text/plain": [
 628        "'a: 4, b: 0, c: 12, pc: 9'"
 629       ]
 630      },
 631      "execution_count": 43,
 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": null,
 662    "metadata": {
 663     "collapsed": true
 664    },
 665    "outputs": [],
 666    "source": [
 667     "# c holds a!\n",
 668     "program = \"\"\"\n",
 669     "??????????????\n",
 670     "      set c 0\n",
 671     "      cpy a b\n",
 672     "      # start of main loop\n",
 673     "loop: jpz b end\n",
 674     "      dec b\n",
 675     "      inc c\n",
 676     "      inc c\n",
 677     "      inc c\n",
 678     "      jmp loop\n",
 679     "      \n",
 680     "      # end of program \n",
 681     "      \n",
 682     "end:  jmp 1\n",
 683     "\"\"\"\n",
 684     "# m = new_machine()\n",
 685     "# program_from_listing(program, m)\n",
 686     "# run(m)\n",
 687     "show_machine(execute(program, initial_state={'a': 4}))"
 688    ]
 689   },
 690   {
 691    "cell_type": "code",
 692    "execution_count": 82,
 693    "metadata": {},
 694    "outputs": [
 695     {
 696      "data": {
 697       "text/plain": [
 698        "'1: 52, a: 0, b: 0, c: 0, pc: 46'"
 699       ]
 700      },
 701      "execution_count": 82,
 702      "metadata": {},
 703      "output_type": "execute_result"
 704     }
 705    ],
 706    "source": [
 707     "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
 708     "# Location 2 holds number of steps taken\n",
 709     "# Location 3 holds max value reached\n",
 710     "program = \"\"\"\n",
 711     "      sto a 1\n",
 712     "      \n",
 713     "      set b 0\n",
 714     "      \n",
 715     "      # if a is one, finish, \n",
 716     "main: dec a\n",
 717     "      jpz a end\n",
 718     "      inc a\n",
 719     "      \n",
 720     "      # find parity of a\n",
 721     "      cpy a c\n",
 722     "      set b 0\n",
 723     "prty: dec c\n",
 724     "      jpz b odd\n",
 725     "      dec b\n",
 726     "      jmp prte\n",
 727     "odd:  inc b\n",
 728     "prte: jpz c 2\n",
 729     "      jmp prty\n",
 730     "      \n",
 731     "      # b == 0 means a even; b == 1 means a odd\n",
 732     "      jpz b isev\n",
 733     "\n",
 734     "      # c holds a * 3 + 1\n",
 735     "      cpy a b\n",
 736     "mul:  jpz b emul\n",
 737     "      dec b\n",
 738     "      inc c\n",
 739     "      inc c\n",
 740     "      inc c\n",
 741     "      jmp mul\n",
 742     "emul: inc c\n",
 743     "      cpy c a\n",
 744     "      jmp fin\n",
 745     "      \n",
 746     "      \n",
 747     "isev: set c 0\n",
 748     "      set b 0\n",
 749     "hlvl: dec a\n",
 750     "      jpz b oddh\n",
 751     "      dec b\n",
 752     "      inc c\n",
 753     "      jmp endh\n",
 754     "oddh: inc b\n",
 755     "endh: jpz a 2\n",
 756     "      jmp hlvl\n",
 757     "      cpy c a\n",
 758     "\n",
 759     "fin:  cpy a b\n",
 760     "      ld  c 1\n",
 761     "maxc: jpz c this\n",
 762     "      jpz b othr\n",
 763     "      dec b\n",
 764     "      dec c\n",
 765     "      jmp maxc\n",
 766     "this: sto a 1\n",
 767     "othr: jmp main\n",
 768     "      \n",
 769     "      # end of program \n",
 770     "      \n",
 771     "end:  set c 0\n",
 772     "\"\"\"\n",
 773     "# m = new_machine()\n",
 774     "# program_from_listing(program, m)\n",
 775     "# run(m)\n",
 776     "show_machine(execute(program, initial_state={'a': 7}))"
 777    ]
 778   },
 779   {
 780    "cell_type": "code",
 781    "execution_count": 56,
 782    "metadata": {},
 783    "outputs": [
 784     {
 785      "data": {
 786       "text/plain": [
 787        "40"
 788       ]
 789      },
 790      "execution_count": 56,
 791      "metadata": {},
 792      "output_type": "execute_result"
 793     }
 794    ],
 795    "source": [
 796     "13*3+1"
 797    ]
 798   },
 799   {
 800    "cell_type": "code",
 801    "execution_count": 63,
 802    "metadata": {
 803     "collapsed": true
 804    },
 805    "outputs": [],
 806    "source": [
 807     "def max_collatz(start):\n",
 808     "    mc = start\n",
 809     "    i = start\n",
 810     "    while i != 1:\n",
 811     "        if i % 2 == 0:\n",
 812     "            i = i // 2\n",
 813     "        else:\n",
 814     "            i = 3 * i + 1\n",
 815     "        if i > mc:\n",
 816     "            mc = i\n",
 817     "    return mc"
 818    ]
 819   },
 820   {
 821    "cell_type": "code",
 822    "execution_count": 64,
 823    "metadata": {},
 824    "outputs": [
 825     {
 826      "data": {
 827       "text/plain": [
 828        "52"
 829       ]
 830      },
 831      "execution_count": 64,
 832      "metadata": {},
 833      "output_type": "execute_result"
 834     }
 835    ],
 836    "source": [
 837     "max_collatz(7)"
 838    ]
 839   },
 840   {
 841    "cell_type": "code",
 842    "execution_count": 80,
 843    "metadata": {},
 844    "outputs": [
 845     {
 846      "data": {
 847       "text/plain": [
 848        "(250504, 937)"
 849       ]
 850      },
 851      "execution_count": 80,
 852      "metadata": {},
 853      "output_type": "execute_result"
 854     }
 855    ],
 856    "source": [
 857     "max([(max_collatz(i), i) for i in range(1, 1000)])"
 858    ]
 859   },
 860   {
 861    "cell_type": "code",
 862    "execution_count": 73,
 863    "metadata": {},
 864    "outputs": [
 865     {
 866      "data": {
 867       "text/plain": [
 868        "[]"
 869       ]
 870      },
 871      "execution_count": 73,
 872      "metadata": {},
 873      "output_type": "execute_result"
 874     }
 875    ],
 876    "source": [
 877     "ans = []\n",
 878     "for i in range(1, 100):\n",
 879     "    m = execute(program, initial_state={'a': i})\n",
 880     "    c = max_collatz(i)\n",
 881     "    if m[1] != c:\n",
 882     "        ans += [(i, m[1], c)]\n",
 883     "ans"
 884    ]
 885   },
 886   {
 887    "cell_type": "code",
 888    "execution_count": 83,
 889    "metadata": {},
 890    "outputs": [
 891     {
 892      "data": {
 893       "text/plain": [
 894        "'1: 250504, a: 0, b: 0, c: 0, pc: 46'"
 895       ]
 896      },
 897      "execution_count": 83,
 898      "metadata": {},
 899      "output_type": "execute_result"
 900     }
 901    ],
 902    "source": [
 903     "show_machine(execute(program, initial_state={'a': 937}))"
 904    ]
 905   },
 906   {
 907    "cell_type": "code",
 908    "execution_count": null,
 909    "metadata": {
 910     "collapsed": true
 911    },
 912    "outputs": [],
 913    "source": []
 914   }
 915  ],
 916  "metadata": {
 917   "kernelspec": {
 918    "display_name": "Python 3",
 919    "language": "python",
 920    "name": "python3"
 921   },
 922   "language_info": {
 923    "codemirror_mode": {
 924     "name": "ipython",
 925     "version": 3
 926    },
 927    "file_extension": ".py",
 928    "mimetype": "text/x-python",
 929    "name": "python",
 930    "nbconvert_exporter": "python",
 931    "pygments_lexer": "ipython3",
 932    "version": "3.5.2+"
 933   }
 934  },
 935  "nbformat": 4,
 936  "nbformat_minor": 2
 937 }