--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "# Machine interpreter\n",
+ "\n",
+ "## Instructions\n",
+ "\n",
+ "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",
+ "\n",
+ "You could pay a large chunk of bitcoin, or you could defeat the ransomware some other way. \n",
+ "\n",
+ "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",
+ "\n",
+ "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",
+ "\n",
+ "The machine has only a few instructions. They're listed by handy mnemonics:\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",
+ "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",
+ "\n",
+ "Before you start execution of a program, you can set the values of some registers.\n",
+ "\n",
+ "For example, this program multiplies the values in the a and b registers, leaving the result in the c register:\n",
+ "\n",
+ "```\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",
+ "set d 0\n",
+ "```\n",
+ "\n",
+ "# Part 1\n",
+ "\n",
+ "You think you've worked out how to generate the code wanted by the ransomware. The program is given in [07-program](07-program.txt), one instruction per line. \n",
+ "\n",
+ "Starting with register `a` holding 7, and all other registers holding zero, what does register `a` contain when the program finishes?"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "It seems your guess of 7 as the starting value was wrong.\n",
+ "\n",
+ "# Part 2\n",
+ "\n",
+ "The program is still given in [07-program.txt](07-program.txt), one instruction per line. \n",
+ "\n",
+ "Starting with register `a` holding 937, and all other registers and memory locations holding zero, what does register `a` contain when the program finishes?"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {
+ "collapsed": true
+ },
+ "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": 4,
+ "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": 5,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def inc(reg, machine):\n",
+ " machine[reg] += 1\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 6,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def dec(reg, machine):\n",
+ " machine[reg] -= 1\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def jmp(addr, machine):\n",
+ " machine['pc'] += addr"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "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": 9,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def set_literal(reg, literal, machine):\n",
+ " machine[reg] = literal\n",
+ " machine['pc'] += 1"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "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": 11,
+ "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": 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": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def program_from_instructions(prog, machine):\n",
+ " machine['instructions'] = [parse(instr) for instr in prog]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def unlabel_listing(listing):\n",
+ " labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
+ " if i.strip() \n",
+ " if not i.strip().startswith('#')]\n",
+ " return replace_labels(labelled_instructions) "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def program_from_listing(listing, machine):\n",
+ " instructions = unlabel_listing(listing)\n",
+ " program_from_instructions(instructions, machine)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "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": {
+ "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": 18,
+ "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: 52, b: 0, c: 0, d: 0, pc: 48'"
+ ]
+ },
+ "execution_count": 22,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = open('07-program.txt').read()\n",
+ "show_machine(execute(program, initial_state={'a': 7}))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'a: 250504, b: 0, c: 0, d: 0, pc: 48'"
+ ]
+ },
+ "execution_count": 23,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = open('07-program.txt').read()\n",
+ "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
+}
projects / ou-summer-of-code-2017.git / blobdiff