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

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