From e405461a789315af95c5ae0e90d63d9fd7d81d37 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 21 Jul 2017 10:39:36 +0100 Subject: [PATCH] Changed machine spec to four registers, no memory --- 07-interpreter/07-program.txt | 10 +- 07-interpreter/Setup.hs | 4 + 07-interpreter/day07.hs | 151 +++ 07-interpreter/machine-code-4-reg.ipynb | 1189 +++++++++++++++++++++++ 07-interpreter/machine-code.ipynb | 268 +++-- 07-interpreter/x07-interpreter.cabal | 28 + 6 files changed, 1545 insertions(+), 105 deletions(-) create mode 100755 07-interpreter/Setup.hs create mode 100644 07-interpreter/day07.hs create mode 100644 07-interpreter/machine-code-4-reg.ipynb create mode 100644 07-interpreter/x07-interpreter.cabal diff --git a/07-interpreter/07-program.txt b/07-interpreter/07-program.txt index f12d425..3607472 100644 --- a/07-interpreter/07-program.txt +++ b/07-interpreter/07-program.txt @@ -1,4 +1,4 @@ -sto a 1 +cpy a d set b 0 dec a jpz a 42 @@ -35,14 +35,14 @@ jpz a 2 jmp -7 cpy c a cpy a b -ld c 1 +cpy d c jpz c 5 jpz b 5 dec b dec c jmp -4 -sto a 1 +cpy a d jmp -42 -ld a 1 +cpy d a set c 0 -sto c 1 \ No newline at end of file +set d 0 \ No newline at end of file diff --git a/07-interpreter/Setup.hs b/07-interpreter/Setup.hs new file mode 100755 index 0000000..ea0ba50 --- /dev/null +++ b/07-interpreter/Setup.hs @@ -0,0 +1,4 @@ +#! /usr/bin/env runhaskell + +import Distribution.Simple +main = defaultMain diff --git a/07-interpreter/day07.hs b/07-interpreter/day07.hs new file mode 100644 index 0000000..a6422b7 --- /dev/null +++ b/07-interpreter/day07.hs @@ -0,0 +1,151 @@ +module Main(main) where + +import Text.Parsec hiding (State) +import Text.ParserCombinators.Parsec.Number +import Control.Monad.State.Lazy +-- import Debug.Trace + +type Register = Char +type Location = Int + +data Instruction = Inc Register + | Dec Register + | Set Register Int + | Cpy Register Register + | Jmp Int + | Jpz Register Int + deriving (Show, Eq) + +data Machine = Machine { a :: Int + , b :: Int + , c :: Int + , d :: Int + , pc :: Int + , instructions :: [Instruction]} + deriving (Show, Eq) + +-- testInstructions = "set c 0\n\ +-- \sto a 1" + +testInstructions = "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 a d" + +emptyMachine :: Machine +emptyMachine = Machine {a=0, b=0, c=0, d=0, pc=0, instructions=[]} + +main :: IO () +main = do + text <- readFile "07-program.txt" + let instructions = successfulParse $ parseIfile text + part1 instructions + part2 instructions + -- let text = testInstructions + -- let instrs = successfulParse $ parseIfile text + -- let m0 = emptyMachine {instructions=instrs, a = 7, b = 3} + -- let mf = snd $ runState runMachine m0 + -- print mf + +part1 :: [Instruction] -> IO () +part1 instrs = + do let m0 = emptyMachine {instructions=instrs, a = 7} + let mf = snd $ runState runMachine m0 + print (a mf) + +part2 :: [Instruction] -> IO () +part2 instrs = + do let m0 = emptyMachine {instructions=instrs, a = 937} + let mf = snd $ runState runMachine m0 + print (a mf) + + +runMachine :: State Machine () +runMachine = + do m <- get + if (pc m) >= (length $ instructions m) + then return () + else do executeStep + runMachine + +executeStep :: State Machine () +executeStep = + do m <- get + let i = (instructions m)!!(pc m) + put (executeInstruction i m) + + +executeInstruction :: Instruction -> Machine -> Machine +-- executeInstruction i m | trace (show i ++ " " ++ show m) False = undefined +executeInstruction (Inc r) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = readRegister m r + m' = writeRegister m r (v+1) +executeInstruction (Dec r) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = readRegister m r + m' = writeRegister m r (v-1) +executeInstruction (Set r v) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + m' = writeRegister m r v +executeInstruction (Cpy s d) m = m' {pc=pc1} + where pc1 = (pc m) + 1 + v = readRegister m s + m' = writeRegister m d v +executeInstruction (Jmp d) m = m {pc=pcj} + where pcj = (pc m) + d +executeInstruction (Jpz r d) m + | v == 0 = m {pc=pcj} + | otherwise = m {pc=pc1} + where pc1 = (pc m) + 1 + pcj = (pc m) + d + v = readRegister m r + + + +readRegister :: Machine -> Register -> Int +readRegister m r = + case r of + 'a' -> (a m) + 'b' -> (b m) + 'c' -> (c m) + 'd' -> (d m) + +writeRegister :: Machine -> Register -> Int -> Machine +writeRegister m r v = + case r of + 'a' -> m {a=v} + 'b' -> m {b=v} + 'c' -> m {c=v} + 'd' -> m {d=v} + + +instructionFile = instructionLine `sepEndBy` newline +instructionLine = incL <|> decL <|> setL <|> cpyL <|> jmpL <|> jpzL + +incL = Inc <$> (try (string "inc") *> spaces *> register) +decL = Dec <$> (try (string "dec") *> spaces *> register) +setL = Set <$> (try (string "set") *> spaces *> register) <*> (spaces *> location) +cpyL = Cpy <$> (try (string "cpy") *> spaces *> register) <*> (spaces *> register) +jmpL = Jmp <$> (try (string "jmp") *> spaces *> location) +jpzL = Jpz <$> (try (string "jpz") *> spaces *> register) <*> (spaces *> location) + +location = int +register = oneOf "abcd" + +parseIfile :: String -> Either ParseError [Instruction] +parseIfile input = parse instructionFile "(unknown)" input + +parseIline :: String -> Either ParseError Instruction +parseIline input = parse instructionLine "(unknown)" input + +successfulParse :: Either ParseError [a] -> [a] +successfulParse (Left _) = [] +successfulParse (Right a) = a diff --git a/07-interpreter/machine-code-4-reg.ipynb b/07-interpreter/machine-code-4-reg.ipynb new file mode 100644 index 0000000..3d000c6 --- /dev/null +++ b/07-interpreter/machine-code-4-reg.ipynb @@ -0,0 +1,1189 @@ +{ + "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
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': [(, ['a']),\n", + " (, ['a']),\n", + " (, ['a', 'b']),\n", + " (, ['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': [(, ['a', 10]),\n", + " (, ['a']),\n", + " (, ['b']),\n", + " (, ['a', 2]),\n", + " (, [-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': [(, ['a', 10]),\n", + " (, ['a']),\n", + " (, ['b']),\n", + " (, ['a', 2]),\n", + " (, [-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': [(, ['c', 'a']),\n", + " (, ['b', 0]),\n", + " (, ['a']),\n", + " (, ['b', 3]),\n", + " (, ['b']),\n", + " (, [2]),\n", + " (, ['b']),\n", + " (, ['a', 3]),\n", + " (, [-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': [(, ['c', 'a']),\n", + " (, ['b', 0]),\n", + " (, ['a']),\n", + " (, ['b', 3]),\n", + " (, ['b']),\n", + " (, [2]),\n", + " (, ['b']),\n", + " (, ['a', 2]),\n", + " (, [-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 +} diff --git a/07-interpreter/machine-code.ipynb b/07-interpreter/machine-code.ipynb index c6b62b0..69cd43f 100644 --- a/07-interpreter/machine-code.ipynb +++ b/07-interpreter/machine-code.ipynb @@ -416,16 +416,16 @@ { "data": { "text/plain": [ - "{'pc': 6,\n", + "{'a': 0,\n", + " 1: 10,\n", + " 'pc': 6,\n", + " 'c': 20,\n", " 'instructions': [(, ['a', 10]),\n", " (, ['a']),\n", " (, ['b']),\n", " (, ['b', 1]),\n", " (, ['a', 2]),\n", " (, [-4])],\n", - " 1: 10,\n", - " 'c': 20,\n", - " 'a': 0,\n", " 'b': 10}" ] }, @@ -457,16 +457,16 @@ { "data": { "text/plain": [ - "{'pc': 6,\n", + "{'a': 0,\n", + " 1: 10,\n", + " 'pc': 6,\n", + " 'c': 20,\n", " 'instructions': [(, ['a', 10]),\n", " (, ['a']),\n", " (, ['b']),\n", " (, ['b', 1]),\n", " (, ['a', 2]),\n", " (, [-4])],\n", - " 1: 10,\n", - " 'c': 20,\n", - " 'a': 0,\n", " 'b': 10}" ] }, @@ -658,7 +658,7 @@ }, { "cell_type": "code", - "execution_count": 28, + "execution_count": 39, "metadata": {}, "outputs": [ { @@ -667,7 +667,7 @@ "'1: 0, a: 0, b: 0, c: 27, pc: 11'" ] }, - "execution_count": 28, + "execution_count": 39, "metadata": {}, "output_type": "execute_result" } @@ -694,6 +694,35 @@ "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))" ] }, + { + "cell_type": "code", + "execution_count": 40, + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "set c 0\n", + "sto a 1\n", + "jpz b 8\n", + "dec b\n", + "ld a 1\n", + "jpz a 4\n", + "inc c\n", + "dec a\n", + "jmp -3\n", + "jmp -7\n", + "sto a 1\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": 29, @@ -736,13 +765,15 @@ }, { "cell_type": "code", - "execution_count": 49, + "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ + "set a 2\n", + "set b 5\n", "set c 0\n", "sto a 1\n", "jpz b 8\n", @@ -767,7 +798,7 @@ }, { "cell_type": "code", - "execution_count": 51, + "execution_count": 31, "metadata": {}, "outputs": [ { @@ -776,7 +807,7 @@ "'1: 0, a: 52, b: 0, c: 0, pc: 48'" ] }, - "execution_count": 51, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -858,7 +889,7 @@ }, { "cell_type": "code", - "execution_count": 30, + "execution_count": 32, "metadata": {}, "outputs": [ { @@ -867,7 +898,7 @@ "40" ] }, - "execution_count": 30, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -878,7 +909,7 @@ }, { "cell_type": "code", - "execution_count": 31, + "execution_count": 33, "metadata": { "collapsed": true }, @@ -899,7 +930,7 @@ }, { "cell_type": "code", - "execution_count": 32, + "execution_count": 34, "metadata": {}, "outputs": [ { @@ -908,7 +939,7 @@ "52" ] }, - "execution_count": 32, + "execution_count": 34, "metadata": {}, "output_type": "execute_result" } @@ -919,7 +950,7 @@ }, { "cell_type": "code", - "execution_count": 33, + "execution_count": 35, "metadata": {}, "outputs": [ { @@ -928,7 +959,7 @@ "(250504, 937)" ] }, - "execution_count": 33, + "execution_count": 35, "metadata": {}, "output_type": "execute_result" } @@ -939,16 +970,116 @@ }, { "cell_type": "code", - "execution_count": 34, - "metadata": {}, + "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": 34, + "execution_count": 36, "metadata": {}, "output_type": "execute_result" } @@ -965,7 +1096,7 @@ }, { "cell_type": "code", - "execution_count": 52, + "execution_count": 38, "metadata": {}, "outputs": [ { @@ -974,7 +1105,7 @@ "'1: 0, a: 250504, b: 0, c: 0, pc: 48'" ] }, - "execution_count": 52, + "execution_count": 38, "metadata": {}, "output_type": "execute_result" } @@ -985,81 +1116,18 @@ }, { "cell_type": "code", - "execution_count": 53, - "metadata": {}, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "sto a 1\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", - "ld c 1\n", - "jpz c 5\n", - "jpz b 5\n", - "dec b\n", - "dec c\n", - "jmp -4\n", - "sto a 1\n", - "jmp -42\n", - "ld a 1\n", - "set c 0\n", - "sto c 1\n" - ] - }, - { - "data": { - "text/plain": [ - "342" - ] - }, - "execution_count": 53, - "metadata": {}, - "output_type": "execute_result" - } - ], + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], "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))" + "# 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))" ] }, { diff --git a/07-interpreter/x07-interpreter.cabal b/07-interpreter/x07-interpreter.cabal new file mode 100644 index 0000000..ed6179c --- /dev/null +++ b/07-interpreter/x07-interpreter.cabal @@ -0,0 +1,28 @@ +-- Initial x07-interpreter.cabal generated by cabal init. For further +-- documentation, see http://haskell.org/cabal/users-guide/ + +name: x07-interpreter +version: 0.1.0.0 +-- synopsis: +-- description: +-- license: +-- license-file: LICENSE +author: Neil Smith +maintainer: neil.smith@open.ac.uk +-- copyright: +-- category: +build-type: Simple +-- extra-source-files: +cabal-version: >=1.10 + +executable x07-interpreter + main-is: day07.hs + -- other-modules: + -- other-extensions: + build-depends: base >=4.8 && <4.9 + , parsec + , parsec-numbers + , mtl + , unordered-containers + -- hs-source-dirs: + default-language: Haskell2010 \ No newline at end of file -- 2.34.1