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