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`   | copy 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        " 'b': 10,\n",
 422        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 423        "  (<function __main__.dec>, ['a']),\n",
 424        "  (<function __main__.inc>, ['b']),\n",
 425        "  (<function __main__.sto>, ['b', 1]),\n",
 426        "  (<function __main__.jpz>, ['a', 2]),\n",
 427        "  (<function __main__.jmp>, [-4])],\n",
 428        " 'c': 20,\n",
 429        " 'pc': 6}"
 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        " 'b': 10,\n",
 463        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 464        "  (<function __main__.dec>, ['a']),\n",
 465        "  (<function __main__.inc>, ['b']),\n",
 466        "  (<function __main__.sto>, ['b', 1]),\n",
 467        "  (<function __main__.jpz>, ['a', 2]),\n",
 468        "  (<function __main__.jmp>, [-4])],\n",
 469        " 'c': 20,\n",
 470        " 'pc': 6}"
 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": 28,
 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": 28,
 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": 29,
 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') if i.strip() if not i.strip().startswith('#')]\n",
 722     "instructions = replace_labels(labelled_instructions)\n",
 723     "print('\\n'.join(instructions))"
 724    ]
 725   },
 726   {
 727    "cell_type": "code",
 728    "execution_count": 30,
 729    "metadata": {},
 730    "outputs": [
 731     {
 732      "data": {
 733       "text/plain": [
 734        "'1: 0, a: 0, b: 0, c: 10, pc: 13'"
 735       ]
 736      },
 737      "execution_count": 30,
 738      "metadata": {},
 739      "output_type": "execute_result"
 740     }
 741    ],
 742    "source": [
 743     "# c holds a * b\n",
 744     "program = \"\"\"\n",
 745     "      set a 2\n",
 746     "      set b 5\n",
 747     "      set c 0\n",
 748     "      sto a 1\n",
 749     "loop: jpz b end      \n",
 750     "      dec b\n",
 751     "      ld a 1\n",
 752     "smul: jpz a emul\n",
 753     "      inc c\n",
 754     "      dec a\n",
 755     "      jmp smul\n",
 756     "emul: jmp loop \n",
 757     "      \n",
 758     "end:  sto a 1\n",
 759     "\"\"\"\n",
 760     "m = new_machine()\n",
 761     "program_from_listing(program, m)\n",
 762     "run(m)\n",
 763     "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
 764    ]
 765   },
 766   {
 767    "cell_type": "code",
 768    "execution_count": 31,
 769    "metadata": {},
 770    "outputs": [
 771     {
 772      "name": "stdout",
 773      "output_type": "stream",
 774      "text": [
 775       "set a 2\n",
 776       "set b 5\n",
 777       "set c 0\n",
 778       "sto a 1\n",
 779       "jpz b 8\n",
 780       "dec b\n",
 781       "ld a 1\n",
 782       "jpz a 4\n",
 783       "inc c\n",
 784       "dec a\n",
 785       "jmp -3\n",
 786       "jmp -7\n",
 787       "sto a 1\n"
 788      ]
 789     }
 790    ],
 791    "source": [
 792     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
 793     "                             if i.strip() \n",
 794     "                             if not i.strip().startswith('#')]\n",
 795     "instructions = replace_labels(labelled_instructions)\n",
 796     "print('\\n'.join(instructions))"
 797    ]
 798   },
 799   {
 800    "cell_type": "code",
 801    "execution_count": 32,
 802    "metadata": {},
 803    "outputs": [
 804     {
 805      "data": {
 806       "text/plain": [
 807        "'1: 0, a: 52, b: 0, c: 0, pc: 48'"
 808       ]
 809      },
 810      "execution_count": 32,
 811      "metadata": {},
 812      "output_type": "execute_result"
 813     }
 814    ],
 815    "source": [
 816     "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
 817     "# Location 2 holds number of steps taken\n",
 818     "# Location 3 holds max value reached\n",
 819     "program = \"\"\"\n",
 820     "      sto a 1\n",
 821     "      \n",
 822     "      set b 0\n",
 823     "      \n",
 824     "      # if a is one, finish, \n",
 825     "main: dec a\n",
 826     "      jpz a end\n",
 827     "      inc a\n",
 828     "      \n",
 829     "      # find parity of a\n",
 830     "      cpy a c\n",
 831     "      set b 0\n",
 832     "prty: dec c\n",
 833     "      jpz b odd\n",
 834     "      dec b\n",
 835     "      jmp prte\n",
 836     "odd:  inc b\n",
 837     "prte: jpz c 2\n",
 838     "      jmp prty\n",
 839     "      \n",
 840     "      # b == 0 means a even; b == 1 means a odd\n",
 841     "      jpz b isev\n",
 842     "\n",
 843     "      # c holds a * 3 + 1\n",
 844     "      cpy a b\n",
 845     "mul:  jpz b emul\n",
 846     "      dec b\n",
 847     "      inc c\n",
 848     "      inc c\n",
 849     "      inc c\n",
 850     "      jmp mul\n",
 851     "emul: inc c\n",
 852     "      cpy c a\n",
 853     "      jmp fin\n",
 854     "      \n",
 855     "      \n",
 856     "isev: set c 0\n",
 857     "      set b 0\n",
 858     "hlvl: dec a\n",
 859     "      jpz b oddh\n",
 860     "      dec b\n",
 861     "      inc c\n",
 862     "      jmp endh\n",
 863     "oddh: inc b\n",
 864     "endh: jpz a 2\n",
 865     "      jmp hlvl\n",
 866     "      cpy c a\n",
 867     "\n",
 868     "fin:  cpy a b\n",
 869     "      ld  c 1\n",
 870     "maxc: jpz c this\n",
 871     "      jpz b othr\n",
 872     "      dec b\n",
 873     "      dec c\n",
 874     "      jmp maxc\n",
 875     "this: sto a 1\n",
 876     "othr: jmp main\n",
 877     "      \n",
 878     "      # end of program \n",
 879     "      \n",
 880     "end:  ld a 1\n",
 881     "      set c 0\n",
 882     "      sto c 1\n",
 883     "\"\"\"\n",
 884     "# m = new_machine()\n",
 885     "# program_from_listing(program, m)\n",
 886     "# run(m)\n",
 887     "show_machine(execute(program, initial_state={'a': 7}))"
 888    ]
 889   },
 890   {
 891    "cell_type": "code",
 892    "execution_count": 33,
 893    "metadata": {},
 894    "outputs": [
 895     {
 896      "data": {
 897       "text/plain": [
 898        "40"
 899       ]
 900      },
 901      "execution_count": 33,
 902      "metadata": {},
 903      "output_type": "execute_result"
 904     }
 905    ],
 906    "source": [
 907     "13*3+1"
 908    ]
 909   },
 910   {
 911    "cell_type": "code",
 912    "execution_count": 34,
 913    "metadata": {
 914     "collapsed": true
 915    },
 916    "outputs": [],
 917    "source": [
 918     "def max_collatz(start):\n",
 919     "    mc = start\n",
 920     "    i = start\n",
 921     "    while i != 1:\n",
 922     "        if i % 2 == 0:\n",
 923     "            i = i // 2\n",
 924     "        else:\n",
 925     "            i = 3 * i + 1\n",
 926     "        if i > mc:\n",
 927     "            mc = i\n",
 928     "    return mc"
 929    ]
 930   },
 931   {
 932    "cell_type": "code",
 933    "execution_count": 35,
 934    "metadata": {},
 935    "outputs": [
 936     {
 937      "data": {
 938       "text/plain": [
 939        "52"
 940       ]
 941      },
 942      "execution_count": 35,
 943      "metadata": {},
 944      "output_type": "execute_result"
 945     }
 946    ],
 947    "source": [
 948     "max_collatz(7)"
 949    ]
 950   },
 951   {
 952    "cell_type": "code",
 953    "execution_count": 36,
 954    "metadata": {},
 955    "outputs": [
 956     {
 957      "data": {
 958       "text/plain": [
 959        "(250504, 937)"
 960       ]
 961      },
 962      "execution_count": 36,
 963      "metadata": {},
 964      "output_type": "execute_result"
 965     }
 966    ],
 967    "source": [
 968     "max([(max_collatz(i), i) for i in range(1, 1000)])"
 969    ]
 970   },
 971   {
 972    "cell_type": "code",
 973    "execution_count": 41,
 974    "metadata": {},
 975    "outputs": [
 976     {
 977      "data": {
 978       "text/plain": [
 979        "(52, 9)"
 980       ]
 981      },
 982      "execution_count": 41,
 983      "metadata": {},
 984      "output_type": "execute_result"
 985     }
 986    ],
 987    "source": [
 988     "max([(max_collatz(i), i) for i in range(1, 10)])"
 989    ]
 990   },
 991   {
 992    "cell_type": "code",
 993    "execution_count": 37,
 994    "metadata": {
 995     "scrolled": true
 996    },
 997    "outputs": [
 998     {
 999      "data": {
1000       "text/plain": [
1001        "[(1, 0, 1),\n",
1002        " (2, 0, 2),\n",
1003        " (3, 0, 16),\n",
1004        " (4, 0, 4),\n",
1005        " (5, 0, 16),\n",
1006        " (6, 0, 16),\n",
1007        " (7, 0, 52),\n",
1008        " (8, 0, 8),\n",
1009        " (9, 0, 52),\n",
1010        " (10, 0, 16),\n",
1011        " (11, 0, 52),\n",
1012        " (12, 0, 16),\n",
1013        " (13, 0, 40),\n",
1014        " (14, 0, 52),\n",
1015        " (15, 0, 160),\n",
1016        " (16, 0, 16),\n",
1017        " (17, 0, 52),\n",
1018        " (18, 0, 52),\n",
1019        " (19, 0, 88),\n",
1020        " (20, 0, 20),\n",
1021        " (21, 0, 64),\n",
1022        " (22, 0, 52),\n",
1023        " (23, 0, 160),\n",
1024        " (24, 0, 24),\n",
1025        " (25, 0, 88),\n",
1026        " (26, 0, 40),\n",
1027        " (27, 0, 9232),\n",
1028        " (28, 0, 52),\n",
1029        " (29, 0, 88),\n",
1030        " (30, 0, 160),\n",
1031        " (31, 0, 9232),\n",
1032        " (32, 0, 32),\n",
1033        " (33, 0, 100),\n",
1034        " (34, 0, 52),\n",
1035        " (35, 0, 160),\n",
1036        " (36, 0, 52),\n",
1037        " (37, 0, 112),\n",
1038        " (38, 0, 88),\n",
1039        " (39, 0, 304),\n",
1040        " (40, 0, 40),\n",
1041        " (41, 0, 9232),\n",
1042        " (42, 0, 64),\n",
1043        " (43, 0, 196),\n",
1044        " (44, 0, 52),\n",
1045        " (45, 0, 136),\n",
1046        " (46, 0, 160),\n",
1047        " (47, 0, 9232),\n",
1048        " (48, 0, 48),\n",
1049        " (49, 0, 148),\n",
1050        " (50, 0, 88),\n",
1051        " (51, 0, 232),\n",
1052        " (52, 0, 52),\n",
1053        " (53, 0, 160),\n",
1054        " (54, 0, 9232),\n",
1055        " (55, 0, 9232),\n",
1056        " (56, 0, 56),\n",
1057        " (57, 0, 196),\n",
1058        " (58, 0, 88),\n",
1059        " (59, 0, 304),\n",
1060        " (60, 0, 160),\n",
1061        " (61, 0, 184),\n",
1062        " (62, 0, 9232),\n",
1063        " (63, 0, 9232),\n",
1064        " (64, 0, 64),\n",
1065        " (65, 0, 196),\n",
1066        " (66, 0, 100),\n",
1067        " (67, 0, 304),\n",
1068        " (68, 0, 68),\n",
1069        " (69, 0, 208),\n",
1070        " (70, 0, 160),\n",
1071        " (71, 0, 9232),\n",
1072        " (72, 0, 72),\n",
1073        " (73, 0, 9232),\n",
1074        " (74, 0, 112),\n",
1075        " (75, 0, 340),\n",
1076        " (76, 0, 88),\n",
1077        " (77, 0, 232),\n",
1078        " (78, 0, 304),\n",
1079        " (79, 0, 808),\n",
1080        " (80, 0, 80),\n",
1081        " (81, 0, 244),\n",
1082        " (82, 0, 9232),\n",
1083        " (83, 0, 9232),\n",
1084        " (84, 0, 84),\n",
1085        " (85, 0, 256),\n",
1086        " (86, 0, 196),\n",
1087        " (87, 0, 592),\n",
1088        " (88, 0, 88),\n",
1089        " (89, 0, 304),\n",
1090        " (90, 0, 136),\n",
1091        " (91, 0, 9232),\n",
1092        " (92, 0, 160),\n",
1093        " (93, 0, 280),\n",
1094        " (94, 0, 9232),\n",
1095        " (95, 0, 9232),\n",
1096        " (96, 0, 96),\n",
1097        " (97, 0, 9232),\n",
1098        " (98, 0, 148),\n",
1099        " (99, 0, 448)]"
1100       ]
1101      },
1102      "execution_count": 37,
1103      "metadata": {},
1104      "output_type": "execute_result"
1105     }
1106    ],
1107    "source": [
1108     "ans = []\n",
1109     "for i in range(1, 100):\n",
1110     "    m = execute(program, initial_state={'a': i})\n",
1111     "    c = max_collatz(i)\n",
1112     "    if m[1] != c:\n",
1113     "        ans += [(i, m[1], c)]\n",
1114     "ans"
1115    ]
1116   },
1117   {
1118    "cell_type": "code",
1119    "execution_count": 38,
1120    "metadata": {},
1121    "outputs": [
1122     {
1123      "data": {
1124       "text/plain": [
1125        "'1: 0, a: 250504, b: 0, c: 0, pc: 48'"
1126       ]
1127      },
1128      "execution_count": 38,
1129      "metadata": {},
1130      "output_type": "execute_result"
1131     }
1132    ],
1133    "source": [
1134     "show_machine(execute(program, initial_state={'a': 937}))"
1135    ]
1136   },
1137   {
1138    "cell_type": "code",
1139    "execution_count": 40,
1140    "metadata": {},
1141    "outputs": [
1142     {
1143      "name": "stdout",
1144      "output_type": "stream",
1145      "text": [
1146       "1 loop, best of 3: 38.6 s per loop\n"
1147      ]
1148     }
1149    ],
1150    "source": [
1151     "%%timeit\n",
1152     "show_machine(execute(program, initial_state={'a': 937}))"
1153    ]
1154   },
1155   {
1156    "cell_type": "code",
1157    "execution_count": 39,
1158    "metadata": {
1159     "collapsed": true
1160    },
1161    "outputs": [],
1162    "source": [
1163     "# labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1164     "#                              if i.strip() \n",
1165     "#                              if not i.strip().startswith('#')]\n",
1166     "# instructions = replace_labels(labelled_instructions)\n",
1167     "# print('\\n'.join(instructions))\n",
1168     "# open('07-program.txt', 'w').write('\\n'.join(instructions))"
1169    ]
1170   },
1171   {
1172    "cell_type": "code",
1173    "execution_count": null,
1174    "metadata": {
1175     "collapsed": true
1176    },
1177    "outputs": [],
1178    "source": []
1179   }
1180  ],
1181  "metadata": {
1182   "kernelspec": {
1183    "display_name": "Python 3",
1184    "language": "python",
1185    "name": "python3"
1186   },
1187   "language_info": {
1188    "codemirror_mode": {
1189     "name": "ipython",
1190     "version": 3
1191    },
1192    "file_extension": ".py",
1193    "mimetype": "text/x-python",
1194    "name": "python",
1195    "nbconvert_exporter": "python",
1196    "pygments_lexer": "ipython3",
1197    "version": "3.5.2+"
1198   }
1199  },
1200  "nbformat": 4,
1201  "nbformat_minor": 2
1202 }