{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Machine interpreter\n",
"\n",
"## Instructions\n",
"\n",
"Three registers, `a`, `b`, and `c`. \n",
"Program counter, `pc`.\n",
"Unlimited memory in numbered addresses, completely separate from program storage.\n",
"\n",
"Each register and memory location 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` | set contents of register `r` into register `s` | \n",
"| `sto r m` | store contents of register `r` into memory location `m` |\n",
"| `ld r m` | load contents of memory location `m` into register `r` |\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": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def new_machine():\n",
" return {'pc': 0, \n",
" 'a': 0,\n",
" 'b': 0, \n",
" 'c': 0,\n",
" 'instructions': []}"
]
},
{
"cell_type": "code",
"execution_count": 2,
"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": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def inc(reg, machine):\n",
" machine[reg] += 1\n",
" machine['pc'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def dec(reg, machine):\n",
" machine[reg] -= 1\n",
" machine['pc'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def jmp(addr, machine):\n",
" machine['pc'] += addr"
]
},
{
"cell_type": "code",
"execution_count": 6,
"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": 7,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def set_literal(reg, literal, machine):\n",
" machine[reg] = literal\n",
" machine['pc'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 8,
"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": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def sto(reg, addr, machine):\n",
" machine[addr] = machine[reg]\n",
" machine['pc'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def ld(reg, addr, machine):\n",
" if addr in machine:\n",
" machine[reg] = machine[addr]\n",
" else:\n",
" machine[reg] = 0\n",
" machine['pc'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
" 'jpz': jpz, 'set': set_literal, 'cpy': cpy,\n",
" 'sto': sto, 'ld': ld}\n",
"numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
]
},
{
"cell_type": "code",
"execution_count": 12,
"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": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
]
},
"execution_count": 13,
"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": 14,
"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": 42,
"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": 39,
"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": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['inc', 'a']"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'fred: inc a'.split(':')[1].split()"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"set a 10\n",
"dec a\n",
"inc b\n",
"sto b 1\n",
"jpz a 2\n",
"jmp -4\n"
]
}
],
"source": [
"program = \"\"\"\n",
" set a 10\n",
" # comment line\n",
" \n",
"loop: dec a\n",
" inc b\n",
" sto b 1\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": 19,
"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": 20,
"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": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 3,\n",
" 'b': 2,\n",
" 'c': 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": 21,
"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": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
" (<function __main__.dec>, ['a']),\n",
" (<function __main__.inc>, ['b']),\n",
" (<function __main__.sto>, ['b', 1]),\n",
" (<function __main__.jpz>, ['a', 2]),\n",
" (<function __main__.jmp>, [-4])],\n",
" 1: 10,\n",
" 'c': 20,\n",
" 'a': 0,\n",
" 'pc': 6,\n",
" 'b': 10}"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"program = \"\"\"\n",
"set a 10\n",
"dec a\n",
"inc b\n",
"sto b 1\n",
"jpz a 2\n",
"jmp -4\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": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
" (<function __main__.dec>, ['a']),\n",
" (<function __main__.inc>, ['b']),\n",
" (<function __main__.sto>, ['b', 1]),\n",
" (<function __main__.jpz>, ['a', 2]),\n",
" (<function __main__.jmp>, [-4])],\n",
" 1: 10,\n",
" 'c': 20,\n",
" 'a': 0,\n",
" 'pc': 6,\n",
" 'b': 10}"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"program = \"\"\"\n",
" set a 10\n",
"loop: dec a\n",
" inc b\n",
" sto b 1\n",
" jpz a 2\n",
" jmp loop\n",
"\"\"\"\n",
"execute(program, initial_state={'c': 20})"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 0,\n",
" 'b': 1,\n",
" 'c': 5,\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": 24,
"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": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'a': 0,\n",
" 'b': 1,\n",
" 'c': 5,\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": 25,
"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": 85,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1: 8, a: 0, b: 1, c: 8, pc: 11'"
]
},
"execution_count": 85,
"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",
" sto c 1\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": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'a: 4, b: 0, c: 12, pc: 9'"
]
},
"execution_count": 43,
"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": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# c holds a!\n",
"program = \"\"\"\n",
"??????????????\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": 82,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1: 52, a: 0, b: 0, c: 0, pc: 46'"
]
},
"execution_count": 82,
"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",
" sto a 1\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",
" ld c 1\n",
"maxc: jpz c this\n",
" jpz b othr\n",
" dec b\n",
" dec c\n",
" jmp maxc\n",
"this: sto a 1\n",
"othr: jmp main\n",
" \n",
" # end of program \n",
" \n",
"end: set c 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": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"40"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"13*3+1"
]
},
{
"cell_type": "code",
"execution_count": 63,
"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": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"52"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max_collatz(7)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(250504, 937)"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"max([(max_collatz(i), i) for i in range(1, 1000)])"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 73,
"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": 83,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1: 250504, a: 0, b: 0, c: 0, pc: 46'"
]
},
"execution_count": 83,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"show_machine(execute(program, initial_state={'a': 937}))"
]
},
{
"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
}