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        "{'pc': 6,\n",
 420        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 421        "  (<function __main__.dec>, ['a']),\n",
 422        "  (<function __main__.inc>, ['b']),\n",
 423        "  (<function __main__.sto>, ['b', 1]),\n",
 424        "  (<function __main__.jpz>, ['a', 2]),\n",
 425        "  (<function __main__.jmp>, [-4])],\n",
 426        " 1: 10,\n",
 427        " 'c': 20,\n",
 428        " 'a': 0,\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        "{'pc': 6,\n",
 461        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 462        "  (<function __main__.dec>, ['a']),\n",
 463        "  (<function __main__.inc>, ['b']),\n",
 464        "  (<function __main__.sto>, ['b', 1]),\n",
 465        "  (<function __main__.jpz>, ['a', 2]),\n",
 466        "  (<function __main__.jmp>, [-4])],\n",
 467        " 1: 10,\n",
 468        " 'c': 20,\n",
 469        " 'a': 0,\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": 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      "data": {
 704       "text/plain": [
 705        "'1: 0, a: 0, b: 0, c: 10, pc: 13'"
 706       ]
 707      },
 708      "execution_count": 29,
 709      "metadata": {},
 710      "output_type": "execute_result"
 711     }
 712    ],
 713    "source": [
 714     "# c holds a * b\n",
 715     "program = \"\"\"\n",
 716     "      set a 2\n",
 717     "      set b 5\n",
 718     "      set c 0\n",
 719     "      sto a 1\n",
 720     "loop: jpz b end      \n",
 721     "      dec b\n",
 722     "      ld a 1\n",
 723     "smul: jpz a emul\n",
 724     "      inc c\n",
 725     "      dec a\n",
 726     "      jmp smul\n",
 727     "emul: jmp loop \n",
 728     "      \n",
 729     "end:  sto a 1\n",
 730     "\"\"\"\n",
 731     "m = new_machine()\n",
 732     "program_from_listing(program, m)\n",
 733     "run(m)\n",
 734     "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
 735    ]
 736   },
 737   {
 738    "cell_type": "code",
 739    "execution_count": 49,
 740    "metadata": {},
 741    "outputs": [
 742     {
 743      "name": "stdout",
 744      "output_type": "stream",
 745      "text": [
 746       "set c 0\n",
 747       "sto a 1\n",
 748       "jpz b 8\n",
 749       "dec b\n",
 750       "ld a 1\n",
 751       "jpz a 4\n",
 752       "inc c\n",
 753       "dec a\n",
 754       "jmp -3\n",
 755       "jmp -7\n",
 756       "sto a 1\n"
 757      ]
 758     }
 759    ],
 760    "source": [
 761     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
 762     "                             if i.strip() \n",
 763     "                             if not i.strip().startswith('#')]\n",
 764     "instructions = replace_labels(labelled_instructions)\n",
 765     "print('\\n'.join(instructions))"
 766    ]
 767   },
 768   {
 769    "cell_type": "code",
 770    "execution_count": 51,
 771    "metadata": {},
 772    "outputs": [
 773     {
 774      "data": {
 775       "text/plain": [
 776        "'1: 0, a: 52, b: 0, c: 0, pc: 48'"
 777       ]
 778      },
 779      "execution_count": 51,
 780      "metadata": {},
 781      "output_type": "execute_result"
 782     }
 783    ],
 784    "source": [
 785     "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
 786     "# Location 2 holds number of steps taken\n",
 787     "# Location 3 holds max value reached\n",
 788     "program = \"\"\"\n",
 789     "      sto a 1\n",
 790     "      \n",
 791     "      set b 0\n",
 792     "      \n",
 793     "      # if a is one, finish, \n",
 794     "main: dec a\n",
 795     "      jpz a end\n",
 796     "      inc a\n",
 797     "      \n",
 798     "      # find parity of a\n",
 799     "      cpy a c\n",
 800     "      set b 0\n",
 801     "prty: dec c\n",
 802     "      jpz b odd\n",
 803     "      dec b\n",
 804     "      jmp prte\n",
 805     "odd:  inc b\n",
 806     "prte: jpz c 2\n",
 807     "      jmp prty\n",
 808     "      \n",
 809     "      # b == 0 means a even; b == 1 means a odd\n",
 810     "      jpz b isev\n",
 811     "\n",
 812     "      # c holds a * 3 + 1\n",
 813     "      cpy a b\n",
 814     "mul:  jpz b emul\n",
 815     "      dec b\n",
 816     "      inc c\n",
 817     "      inc c\n",
 818     "      inc c\n",
 819     "      jmp mul\n",
 820     "emul: inc c\n",
 821     "      cpy c a\n",
 822     "      jmp fin\n",
 823     "      \n",
 824     "      \n",
 825     "isev: set c 0\n",
 826     "      set b 0\n",
 827     "hlvl: dec a\n",
 828     "      jpz b oddh\n",
 829     "      dec b\n",
 830     "      inc c\n",
 831     "      jmp endh\n",
 832     "oddh: inc b\n",
 833     "endh: jpz a 2\n",
 834     "      jmp hlvl\n",
 835     "      cpy c a\n",
 836     "\n",
 837     "fin:  cpy a b\n",
 838     "      ld  c 1\n",
 839     "maxc: jpz c this\n",
 840     "      jpz b othr\n",
 841     "      dec b\n",
 842     "      dec c\n",
 843     "      jmp maxc\n",
 844     "this: sto a 1\n",
 845     "othr: jmp main\n",
 846     "      \n",
 847     "      # end of program \n",
 848     "      \n",
 849     "end:  ld a 1\n",
 850     "      set c 0\n",
 851     "      sto c 1\n",
 852     "\"\"\"\n",
 853     "# m = new_machine()\n",
 854     "# program_from_listing(program, m)\n",
 855     "# run(m)\n",
 856     "show_machine(execute(program, initial_state={'a': 7}))"
 857    ]
 858   },
 859   {
 860    "cell_type": "code",
 861    "execution_count": 30,
 862    "metadata": {},
 863    "outputs": [
 864     {
 865      "data": {
 866       "text/plain": [
 867        "40"
 868       ]
 869      },
 870      "execution_count": 30,
 871      "metadata": {},
 872      "output_type": "execute_result"
 873     }
 874    ],
 875    "source": [
 876     "13*3+1"
 877    ]
 878   },
 879   {
 880    "cell_type": "code",
 881    "execution_count": 31,
 882    "metadata": {
 883     "collapsed": true
 884    },
 885    "outputs": [],
 886    "source": [
 887     "def max_collatz(start):\n",
 888     "    mc = start\n",
 889     "    i = start\n",
 890     "    while i != 1:\n",
 891     "        if i % 2 == 0:\n",
 892     "            i = i // 2\n",
 893     "        else:\n",
 894     "            i = 3 * i + 1\n",
 895     "        if i > mc:\n",
 896     "            mc = i\n",
 897     "    return mc"
 898    ]
 899   },
 900   {
 901    "cell_type": "code",
 902    "execution_count": 32,
 903    "metadata": {},
 904    "outputs": [
 905     {
 906      "data": {
 907       "text/plain": [
 908        "52"
 909       ]
 910      },
 911      "execution_count": 32,
 912      "metadata": {},
 913      "output_type": "execute_result"
 914     }
 915    ],
 916    "source": [
 917     "max_collatz(7)"
 918    ]
 919   },
 920   {
 921    "cell_type": "code",
 922    "execution_count": 33,
 923    "metadata": {},
 924    "outputs": [
 925     {
 926      "data": {
 927       "text/plain": [
 928        "(250504, 937)"
 929       ]
 930      },
 931      "execution_count": 33,
 932      "metadata": {},
 933      "output_type": "execute_result"
 934     }
 935    ],
 936    "source": [
 937     "max([(max_collatz(i), i) for i in range(1, 1000)])"
 938    ]
 939   },
 940   {
 941    "cell_type": "code",
 942    "execution_count": 34,
 943    "metadata": {},
 944    "outputs": [
 945     {
 946      "data": {
 947       "text/plain": [
 948        "[]"
 949       ]
 950      },
 951      "execution_count": 34,
 952      "metadata": {},
 953      "output_type": "execute_result"
 954     }
 955    ],
 956    "source": [
 957     "ans = []\n",
 958     "for i in range(1, 100):\n",
 959     "    m = execute(program, initial_state={'a': i})\n",
 960     "    c = max_collatz(i)\n",
 961     "    if m[1] != c:\n",
 962     "        ans += [(i, m[1], c)]\n",
 963     "ans"
 964    ]
 965   },
 966   {
 967    "cell_type": "code",
 968    "execution_count": 52,
 969    "metadata": {},
 970    "outputs": [
 971     {
 972      "data": {
 973       "text/plain": [
 974        "'1: 0, a: 250504, b: 0, c: 0, pc: 48'"
 975       ]
 976      },
 977      "execution_count": 52,
 978      "metadata": {},
 979      "output_type": "execute_result"
 980     }
 981    ],
 982    "source": [
 983     "show_machine(execute(program, initial_state={'a': 937}))"
 984    ]
 985   },
 986   {
 987    "cell_type": "code",
 988    "execution_count": 53,
 989    "metadata": {},
 990    "outputs": [
 991     {
 992      "name": "stdout",
 993      "output_type": "stream",
 994      "text": [
 995       "sto a 1\n",
 996       "set b 0\n",
 997       "dec a\n",
 998       "jpz a 42\n",
 999       "inc a\n",
1000       "cpy a c\n",
1001       "set b 0\n",
1002       "dec c\n",
1003       "jpz b 3\n",
1004       "dec b\n",
1005       "jmp 2\n",
1006       "inc b\n",
1007       "jpz c 2\n",
1008       "jmp -6\n",
1009       "jpz b 11\n",
1010       "cpy a b\n",
1011       "jpz b 6\n",
1012       "dec b\n",
1013       "inc c\n",
1014       "inc c\n",
1015       "inc c\n",
1016       "jmp -5\n",
1017       "inc c\n",
1018       "cpy c a\n",
1019       "jmp 12\n",
1020       "set c 0\n",
1021       "set b 0\n",
1022       "dec a\n",
1023       "jpz b 4\n",
1024       "dec b\n",
1025       "inc c\n",
1026       "jmp 2\n",
1027       "inc b\n",
1028       "jpz a 2\n",
1029       "jmp -7\n",
1030       "cpy c a\n",
1031       "cpy a b\n",
1032       "ld c 1\n",
1033       "jpz c 5\n",
1034       "jpz b 5\n",
1035       "dec b\n",
1036       "dec c\n",
1037       "jmp -4\n",
1038       "sto a 1\n",
1039       "jmp -42\n",
1040       "ld a 1\n",
1041       "set c 0\n",
1042       "sto c 1\n"
1043      ]
1044     },
1045     {
1046      "data": {
1047       "text/plain": [
1048        "342"
1049       ]
1050      },
1051      "execution_count": 53,
1052      "metadata": {},
1053      "output_type": "execute_result"
1054     }
1055    ],
1056    "source": [
1057     "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1058     "                             if i.strip() \n",
1059     "                             if not i.strip().startswith('#')]\n",
1060     "instructions = replace_labels(labelled_instructions)\n",
1061     "print('\\n'.join(instructions))\n",
1062     "open('07-program.txt', 'w').write('\\n'.join(instructions))"
1063    ]
1064   },
1065   {
1066    "cell_type": "code",
1067    "execution_count": null,
1068    "metadata": {
1069     "collapsed": true
1070    },
1071    "outputs": [],
1072    "source": []
1073   }
1074  ],
1075  "metadata": {
1076   "kernelspec": {
1077    "display_name": "Python 3",
1078    "language": "python",
1079    "name": "python3"
1080   },
1081   "language_info": {
1082    "codemirror_mode": {
1083     "name": "ipython",
1084     "version": 3
1085    },
1086    "file_extension": ".py",
1087    "mimetype": "text/x-python",
1088    "name": "python",
1089    "nbconvert_exporter": "python",
1090    "pygments_lexer": "ipython3",
1091    "version": "3.5.2+"
1092   }
1093  },
1094  "nbformat": 4,
1095  "nbformat_minor": 2
1096 }