--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Machine interpreter\n",
+ "\n",
+ "## Instructions\n",
+ "\n",
+ "Four registers, `a`, `b`, `c`, and `d`.\n",
+ "Program counter, `pc`.\n",
+ "\n",
+ "Each register can hold 8-byte integers (Java `long`s).\n",
+ "\n",
+ "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
+ "\n",
+ "`jmp` and `jpz` override this normal change in `pc`.\n",
+ "\n",
+ "| Instruction | Description |\n",
+ "|:------------|:------------|\n",
+ "| `inc r` | increment contents of register `r` |\n",
+ "| `dec r` | decrement contents of register `r` |\n",
+ "| `set r i` | set contents of register `r` to literal value `i` |\n",
+ "| `cpy r s` | copy contents of register `r` into register `s` | \n",
+ "| `jmp i` | jump to instruction `i` places forward |\n",
+ "| `jpz r i` | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
+ "\n",
+ "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."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 4,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def new_machine():\n",
+ " return {'pc': 0, \n",
+ " 'a': 0,\n",
+ " 'b': 0, \n",
+ " 'c': 0,\n",
+ " 'd': 0,\n",
+ " 'instructions': []}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_machine(machine):\n",
+ " return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
+ " for sk in sorted(str(k) for k in machine)\n",
+ " if sk != 'instructions')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def inc(reg, machine):\n",
+ " machine[reg] += 1\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def dec(reg, machine):\n",
+ " machine[reg] -= 1\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def jmp(addr, machine):\n",
+ " machine['pc'] += addr"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def jpz(reg, addr, machine):\n",
+ " if machine[reg] == 0:\n",
+ " machine['pc'] += addr\n",
+ " else:\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def set_literal(reg, literal, machine):\n",
+ " machine[reg] = literal\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def cpy(from_reg, to_reg, machine):\n",
+ " machine[to_reg] = machine[from_reg]\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
+ " 'jpz': jpz, 'set': set_literal, 'cpy': cpy}\n",
+ "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def parse(instruction):\n",
+ " words = instruction.split()\n",
+ " instr = words[0]\n",
+ " args = words[1:]\n",
+ " if instr in numeric_args_table:\n",
+ " for p in numeric_args_table[instr]:\n",
+ " args[p] = int(args[p])\n",
+ " return instruction_table[instr], args"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 2, 'b': 1, 'c': 0, 'd': 0, 'instructions': [], 'pc': 3}"
+ ]
+ },
+ "execution_count": 14,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "m = new_machine()\n",
+ "inc('a', m)\n",
+ "cargs = ['a', 'b']\n",
+ "cpy(*cargs, m)\n",
+ "inc('a', m)\n",
+ "m"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def program_from_instructions(prog, machine):\n",
+ " machine['instructions'] = [parse(instr) for instr in prog]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def program_from_listing(listing, machine):\n",
+ " labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
+ " if i.strip() \n",
+ " if not i.strip().startswith('#')]\n",
+ " instructions = replace_labels(labelled_instructions)\n",
+ " program_from_instructions(instructions, machine)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def replace_labels(listing):\n",
+ " locations = {}\n",
+ " for n, i in enumerate(listing):\n",
+ " if ':' in i:\n",
+ " locations[i.split(':')[0]] = n\n",
+ "\n",
+ " unlabelled_listing = []\n",
+ " for n, i in enumerate(listing):\n",
+ " instr = i.split()\n",
+ " if ':' in i:\n",
+ " instr = i.split(':')[1].split()\n",
+ " else:\n",
+ " instr = i.split()\n",
+ " terms = []\n",
+ " for term in instr:\n",
+ " if term in locations:\n",
+ " terms += [str(locations[term] - n)]\n",
+ " else:\n",
+ " terms += [term]\n",
+ " transformed_instr = ' '.join(terms)\n",
+ " unlabelled_listing += [transformed_instr]\n",
+ " \n",
+ " return unlabelled_listing "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['inc', 'a']"
+ ]
+ },
+ "execution_count": 18,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "'fred: inc a'.split(':')[1].split()"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "set a 10\n",
+ "dec a\n",
+ "inc b\n",
+ "jpz a 2\n",
+ "jmp -3\n"
+ ]
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ " set a 10\n",
+ " # comment line\n",
+ " \n",
+ "loop: dec a\n",
+ " inc b\n",
+ " jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
+ "instructions = replace_labels(labelled_instructions)\n",
+ "print('\\n'.join(instructions))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def run(machine, initial_state=None, trace=False):\n",
+ " if initial_state:\n",
+ " machine.update(initial_state)\n",
+ " while machine['pc'] < len(machine['instructions']):\n",
+ " if trace:\n",
+ " print(show_machine(machine))\n",
+ " cmd, args = machine['instructions'][machine['pc']]\n",
+ " cmd(*args, machine)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def execute(listing, initial_state=None, trace=False):\n",
+ " m = new_machine()\n",
+ " program_from_listing(listing, m)\n",
+ " run(m, initial_state=initial_state, trace=trace)\n",
+ " return m"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 3,\n",
+ " 'b': 2,\n",
+ " 'c': 0,\n",
+ " 'd': 0,\n",
+ " 'instructions': [(<function __main__.inc>, ['a']),\n",
+ " (<function __main__.inc>, ['a']),\n",
+ " (<function __main__.cpy>, ['a', 'b']),\n",
+ " (<function __main__.inc>, ['a'])],\n",
+ " 'pc': 4}"
+ ]
+ },
+ "execution_count": 22,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ "inc a\n",
+ "inc a\n",
+ "cpy a b\n",
+ "inc a\n",
+ "\"\"\"\n",
+ "execute(program)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 24,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 0,\n",
+ " 'b': 10,\n",
+ " 'c': 20,\n",
+ " 'd': 0,\n",
+ " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.jpz>, ['a', 2]),\n",
+ " (<function __main__.jmp>, [-3])],\n",
+ " 'pc': 5}"
+ ]
+ },
+ "execution_count": 24,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ "set a 10\n",
+ "dec a\n",
+ "inc b\n",
+ "jpz a 2\n",
+ "jmp -3\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "execute(program, initial_state={'c': 20})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 0,\n",
+ " 'b': 10,\n",
+ " 'c': 20,\n",
+ " 'd': 0,\n",
+ " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.jpz>, ['a', 2]),\n",
+ " (<function __main__.jmp>, [-3])],\n",
+ " 'pc': 5}"
+ ]
+ },
+ "execution_count": 25,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ " set a 10\n",
+ "loop: dec a\n",
+ " inc b\n",
+ " jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "execute(program, initial_state={'c': 20})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 0,\n",
+ " 'b': 1,\n",
+ " 'c': 5,\n",
+ " 'd': 0,\n",
+ " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
+ " (<function __main__.set_literal>, ['b', 0]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.jpz>, ['b', 3]),\n",
+ " (<function __main__.dec>, ['b']),\n",
+ " (<function __main__.jmp>, [2]),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.jpz>, ['a', 3]),\n",
+ " (<function __main__.jmp>, [-6])],\n",
+ " 'pc': 10}"
+ ]
+ },
+ "execution_count": 26,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ "cpy c a\n",
+ "set b 0\n",
+ "dec a\n",
+ "jpz b 3\n",
+ "dec b\n",
+ "jmp 2\n",
+ "inc b\n",
+ "jpz a 3\n",
+ "jmp -6\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "execute(program, initial_state={'c': 5})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 0,\n",
+ " 'b': 1,\n",
+ " 'c': 5,\n",
+ " 'd': 0,\n",
+ " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
+ " (<function __main__.set_literal>, ['b', 0]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.jpz>, ['b', 3]),\n",
+ " (<function __main__.dec>, ['b']),\n",
+ " (<function __main__.jmp>, [2]),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.jpz>, ['a', 2]),\n",
+ " (<function __main__.jmp>, [-6])],\n",
+ " 'pc': 9}"
+ ]
+ },
+ "execution_count": 27,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# b holds parity of number in c: (c % 2)\n",
+ "program = \"\"\"\n",
+ " cpy c a\n",
+ " set b 0\n",
+ "loop: dec a\n",
+ " jpz b odd\n",
+ " dec b\n",
+ " jmp end\n",
+ "odd: inc b\n",
+ "end: jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "execute(program, initial_state={'c': 5})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 0, b: 1, c: 8, d: 0, pc: 10'"
+ ]
+ },
+ "execution_count": 28,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# c holds floor(a/2)\n",
+ "program = \"\"\"\n",
+ " set c 0\n",
+ " set b 0\n",
+ "loop: dec a\n",
+ " jpz b odd\n",
+ " dec b\n",
+ " inc c\n",
+ " jmp end\n",
+ "odd: inc b\n",
+ "end: jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "show_machine(execute(program, initial_state={'a': 17}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 29,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 4, b: 0, c: 12, d: 0, pc: 9'"
+ ]
+ },
+ "execution_count": 29,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# c holds a * 3\n",
+ "program = \"\"\"\n",
+ " set c 0\n",
+ " cpy a b\n",
+ " # start of main loop\n",
+ "loop: jpz b end\n",
+ " dec b\n",
+ " inc c\n",
+ " inc c\n",
+ " inc c\n",
+ " jmp loop\n",
+ " \n",
+ " # end of program \n",
+ " \n",
+ "end: jmp 1\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "show_machine(execute(program, initial_state={'a': 4}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 0, b: 0, c: 27, d: 0, pc: 11'"
+ ]
+ },
+ "execution_count": 38,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# c holds a * b\n",
+ "program = \"\"\"\n",
+ " set c 0\n",
+ " cpy a d\n",
+ "loop: jpz b end \n",
+ " dec b\n",
+ " cpy d a\n",
+ "smul: jpz a emul\n",
+ " inc c\n",
+ " dec a\n",
+ " jmp smul\n",
+ "emul: jmp loop \n",
+ " \n",
+ "end: set d 0\n",
+ "\"\"\"\n",
+ "m = new_machine()\n",
+ "program_from_listing(program, m)\n",
+ "run(m)\n",
+ "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "set c 0\n",
+ "cpy a d\n",
+ "jpz b 8\n",
+ "dec b\n",
+ "cpy d a\n",
+ "jpz a 4\n",
+ "inc c\n",
+ "dec a\n",
+ "jmp -3\n",
+ "jmp -7\n",
+ "set d 0\n"
+ ]
+ }
+ ],
+ "source": [
+ "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
+ "instructions = replace_labels(labelled_instructions)\n",
+ "print('\\n'.join(instructions))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 2, b: 0, c: 10, d: 2, pc: 13'"
+ ]
+ },
+ "execution_count": 31,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# c holds a * b\n",
+ "program = \"\"\"\n",
+ " set a 2\n",
+ " set b 5\n",
+ " set c 0\n",
+ " cpy a d\n",
+ "loop: jpz b end \n",
+ " dec b\n",
+ " cpy d a\n",
+ "smul: jpz a emul\n",
+ " inc c\n",
+ " dec a\n",
+ " jmp smul\n",
+ "emul: jmp loop \n",
+ " \n",
+ "end: cpy d a\n",
+ "\"\"\"\n",
+ "m = new_machine()\n",
+ "program_from_listing(program, m)\n",
+ "run(m)\n",
+ "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "set a 2\n",
+ "set b 5\n",
+ "set c 0\n",
+ "cpy a d\n",
+ "jpz b 8\n",
+ "dec b\n",
+ "cpy d a\n",
+ "jpz a 4\n",
+ "inc c\n",
+ "dec a\n",
+ "jmp -3\n",
+ "jmp -7\n",
+ "cpy d a\n"
+ ]
+ }
+ ],
+ "source": [
+ "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
+ " if i.strip() \n",
+ " if not i.strip().startswith('#')]\n",
+ "instructions = replace_labels(labelled_instructions)\n",
+ "print('\\n'.join(instructions))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 52, b: 0, c: 0, d: 0, pc: 48'"
+ ]
+ },
+ "execution_count": 33,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
+ "# Location 2 holds number of steps taken\n",
+ "# Location 3 holds max value reached\n",
+ "program = \"\"\"\n",
+ " cpy a d\n",
+ " \n",
+ " set b 0\n",
+ " \n",
+ " # if a is one, finish, \n",
+ "main: dec a\n",
+ " jpz a end\n",
+ " inc a\n",
+ " \n",
+ " # find parity of a\n",
+ " cpy a c\n",
+ " set b 0\n",
+ "prty: dec c\n",
+ " jpz b odd\n",
+ " dec b\n",
+ " jmp prte\n",
+ "odd: inc b\n",
+ "prte: jpz c 2\n",
+ " jmp prty\n",
+ " \n",
+ " # b == 0 means a even; b == 1 means a odd\n",
+ " jpz b isev\n",
+ "\n",
+ " # c holds a * 3 + 1\n",
+ " cpy a b\n",
+ "mul: jpz b emul\n",
+ " dec b\n",
+ " inc c\n",
+ " inc c\n",
+ " inc c\n",
+ " jmp mul\n",
+ "emul: inc c\n",
+ " cpy c a\n",
+ " jmp fin\n",
+ " \n",
+ " \n",
+ "isev: set c 0\n",
+ " set b 0\n",
+ "hlvl: dec a\n",
+ " jpz b oddh\n",
+ " dec b\n",
+ " inc c\n",
+ " jmp endh\n",
+ "oddh: inc b\n",
+ "endh: jpz a 2\n",
+ " jmp hlvl\n",
+ " cpy c a\n",
+ "\n",
+ "fin: cpy a b\n",
+ " cpy d c\n",
+ "maxc: jpz c this\n",
+ " jpz b othr\n",
+ " dec b\n",
+ " dec c\n",
+ " jmp maxc\n",
+ "this: cpy a d\n",
+ "othr: jmp main\n",
+ " \n",
+ " # end of program \n",
+ " \n",
+ "end: cpy d a\n",
+ " set c 0\n",
+ " set d 0\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "show_machine(execute(program, initial_state={'a': 7}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "40"
+ ]
+ },
+ "execution_count": 32,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "13*3+1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def max_collatz(start):\n",
+ " mc = start\n",
+ " i = start\n",
+ " while i != 1:\n",
+ " if i % 2 == 0:\n",
+ " i = i // 2\n",
+ " else:\n",
+ " i = 3 * i + 1\n",
+ " if i > mc:\n",
+ " mc = i\n",
+ " return mc"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "52"
+ ]
+ },
+ "execution_count": 34,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max_collatz(7)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(250504, 937)"
+ ]
+ },
+ "execution_count": 35,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "max([(max_collatz(i), i) for i in range(1, 1000)])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[(1, 0, 1),\n",
+ " (2, 0, 2),\n",
+ " (3, 0, 16),\n",
+ " (4, 0, 4),\n",
+ " (5, 0, 16),\n",
+ " (6, 0, 16),\n",
+ " (7, 0, 52),\n",
+ " (8, 0, 8),\n",
+ " (9, 0, 52),\n",
+ " (10, 0, 16),\n",
+ " (11, 0, 52),\n",
+ " (12, 0, 16),\n",
+ " (13, 0, 40),\n",
+ " (14, 0, 52),\n",
+ " (15, 0, 160),\n",
+ " (16, 0, 16),\n",
+ " (17, 0, 52),\n",
+ " (18, 0, 52),\n",
+ " (19, 0, 88),\n",
+ " (20, 0, 20),\n",
+ " (21, 0, 64),\n",
+ " (22, 0, 52),\n",
+ " (23, 0, 160),\n",
+ " (24, 0, 24),\n",
+ " (25, 0, 88),\n",
+ " (26, 0, 40),\n",
+ " (27, 0, 9232),\n",
+ " (28, 0, 52),\n",
+ " (29, 0, 88),\n",
+ " (30, 0, 160),\n",
+ " (31, 0, 9232),\n",
+ " (32, 0, 32),\n",
+ " (33, 0, 100),\n",
+ " (34, 0, 52),\n",
+ " (35, 0, 160),\n",
+ " (36, 0, 52),\n",
+ " (37, 0, 112),\n",
+ " (38, 0, 88),\n",
+ " (39, 0, 304),\n",
+ " (40, 0, 40),\n",
+ " (41, 0, 9232),\n",
+ " (42, 0, 64),\n",
+ " (43, 0, 196),\n",
+ " (44, 0, 52),\n",
+ " (45, 0, 136),\n",
+ " (46, 0, 160),\n",
+ " (47, 0, 9232),\n",
+ " (48, 0, 48),\n",
+ " (49, 0, 148),\n",
+ " (50, 0, 88),\n",
+ " (51, 0, 232),\n",
+ " (52, 0, 52),\n",
+ " (53, 0, 160),\n",
+ " (54, 0, 9232),\n",
+ " (55, 0, 9232),\n",
+ " (56, 0, 56),\n",
+ " (57, 0, 196),\n",
+ " (58, 0, 88),\n",
+ " (59, 0, 304),\n",
+ " (60, 0, 160),\n",
+ " (61, 0, 184),\n",
+ " (62, 0, 9232),\n",
+ " (63, 0, 9232),\n",
+ " (64, 0, 64),\n",
+ " (65, 0, 196),\n",
+ " (66, 0, 100),\n",
+ " (67, 0, 304),\n",
+ " (68, 0, 68),\n",
+ " (69, 0, 208),\n",
+ " (70, 0, 160),\n",
+ " (71, 0, 9232),\n",
+ " (72, 0, 72),\n",
+ " (73, 0, 9232),\n",
+ " (74, 0, 112),\n",
+ " (75, 0, 340),\n",
+ " (76, 0, 88),\n",
+ " (77, 0, 232),\n",
+ " (78, 0, 304),\n",
+ " (79, 0, 808),\n",
+ " (80, 0, 80),\n",
+ " (81, 0, 244),\n",
+ " (82, 0, 9232),\n",
+ " (83, 0, 9232),\n",
+ " (84, 0, 84),\n",
+ " (85, 0, 256),\n",
+ " (86, 0, 196),\n",
+ " (87, 0, 592),\n",
+ " (88, 0, 88),\n",
+ " (89, 0, 304),\n",
+ " (90, 0, 136),\n",
+ " (91, 0, 9232),\n",
+ " (92, 0, 160),\n",
+ " (93, 0, 280),\n",
+ " (94, 0, 9232),\n",
+ " (95, 0, 9232),\n",
+ " (96, 0, 96),\n",
+ " (97, 0, 9232),\n",
+ " (98, 0, 148),\n",
+ " (99, 0, 448)]"
+ ]
+ },
+ "execution_count": 36,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "ans = []\n",
+ "for i in range(1, 100):\n",
+ " m = execute(program, initial_state={'a': i})\n",
+ " c = max_collatz(i)\n",
+ " if m[1] != c:\n",
+ " ans += [(i, m[1], c)]\n",
+ "ans"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 34,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 250504, b: 0, c: 0, d: 0, pc: 48'"
+ ]
+ },
+ "execution_count": 34,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "show_machine(execute(program, initial_state={'a': 937}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "cpy a d\n",
+ "set b 0\n",
+ "dec a\n",
+ "jpz a 42\n",
+ "inc a\n",
+ "cpy a c\n",
+ "set b 0\n",
+ "dec c\n",
+ "jpz b 3\n",
+ "dec b\n",
+ "jmp 2\n",
+ "inc b\n",
+ "jpz c 2\n",
+ "jmp -6\n",
+ "jpz b 11\n",
+ "cpy a b\n",
+ "jpz b 6\n",
+ "dec b\n",
+ "inc c\n",
+ "inc c\n",
+ "inc c\n",
+ "jmp -5\n",
+ "inc c\n",
+ "cpy c a\n",
+ "jmp 12\n",
+ "set c 0\n",
+ "set b 0\n",
+ "dec a\n",
+ "jpz b 4\n",
+ "dec b\n",
+ "inc c\n",
+ "jmp 2\n",
+ "inc b\n",
+ "jpz a 2\n",
+ "jmp -7\n",
+ "cpy c a\n",
+ "cpy a b\n",
+ "cpy d c\n",
+ "jpz c 5\n",
+ "jpz b 5\n",
+ "dec b\n",
+ "dec c\n",
+ "jmp -4\n",
+ "cpy a d\n",
+ "jmp -42\n",
+ "cpy d a\n",
+ "set c 0\n",
+ "set d 0\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "344"
+ ]
+ },
+ "execution_count": 35,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
+ " if i.strip() \n",
+ " if not i.strip().startswith('#')]\n",
+ "instructions = replace_labels(labelled_instructions)\n",
+ "print('\\n'.join(instructions))\n",
+ "open('07-program.txt', 'w').write('\\n'.join(instructions))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 3",
+ "language": "python",
+ "name": "python3"
+ },
+ "language_info": {
+ "codemirror_mode": {
+ "name": "ipython",
+ "version": 3
+ },
+ "file_extension": ".py",
+ "mimetype": "text/x-python",
+ "name": "python",
+ "nbconvert_exporter": "python",
+ "pygments_lexer": "ipython3",
+ "version": "3.5.2+"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
projects / ou-summer-of-code-2017.git / blobdiff