--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 121,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "#!/usr/bin/python\n",
+ "#\n",
+ "# Brainfuck Interpreter\n",
+ "# Copyright 2011 Sebastian Kaspari\n",
+ "#\n",
+ "# Usage: ./brainfuck.py [FILE]\n",
+ "\n",
+ "import sys\n",
+ "\n",
+ "def execute(filename):\n",
+ " f = open(filename, \"r\")\n",
+ " evaluate(f.read())\n",
+ " f.close()\n",
+ "\n",
+ "\n",
+ "def evaluate(code, inp=None, debug=False):\n",
+ " code = cleanup(list(code))\n",
+ " bracemap = buildbracemap(code)\n",
+ "\n",
+ " cells, codeptr, cellptr = [0], 0, 0\n",
+ " inputptr = 0\n",
+ "\n",
+ " try:\n",
+ " while codeptr < len(code):\n",
+ " command = code[codeptr]\n",
+ " \n",
+ " if debug:\n",
+ " print(command, cellptr, cells)\n",
+ "\n",
+ " if command == \">\":\n",
+ " cellptr += 1\n",
+ " if cellptr == len(cells): cells.append(0)\n",
+ "\n",
+ " if command == \"<\":\n",
+ " cellptr = 0 if cellptr <= 0 else cellptr - 1\n",
+ "\n",
+ " if command == \"+\":\n",
+ " cells[cellptr] = cells[cellptr] + 1 if cells[cellptr] < 255 else 0\n",
+ "\n",
+ " if command == \"-\":\n",
+ " cells[cellptr] = cells[cellptr] - 1 if cells[cellptr] > 0 else 255\n",
+ "\n",
+ " if command == \"[\" and cells[cellptr] == 0: codeptr = bracemap[codeptr]\n",
+ " if command == \"]\" and cells[cellptr] != 0: codeptr = bracemap[codeptr]\n",
+ " if command == \".\": sys.stdout.write(chr(cells[cellptr]))\n",
+ " if command == \",\": \n",
+ " if inp is not None:\n",
+ " if inputptr >= len(inp):\n",
+ " raise EOFError\n",
+ " cells[cellptr] = ord(inp[inputptr])\n",
+ " inputptr += 1\n",
+ " else:\n",
+ " cells[cellptr] = ord(getch.getch())\n",
+ "\n",
+ " codeptr += 1\n",
+ " except EOFError:\n",
+ " pass\n",
+ " return cells, codeptr, cellptr\n",
+ "\n",
+ "\n",
+ "def cleanup(code):\n",
+ " return list(filter(lambda x: x in ['.', ',', '[', ']', '<', '>', '+', '-'], code))\n",
+ "\n",
+ "\n",
+ "def buildbracemap(code):\n",
+ " temp_bracestack, bracemap = [], {}\n",
+ "\n",
+ " for position, command in enumerate(code):\n",
+ " if command == \"[\": temp_bracestack.append(position)\n",
+ " if command == \"]\":\n",
+ " start = temp_bracestack.pop()\n",
+ " bracemap[start] = position\n",
+ " bracemap[position] = start\n",
+ " return bracemap\n",
+ "\n",
+ "\n",
+ "# def main():\n",
+ "# if len(sys.argv) == 2: execute(sys.argv[1])\n",
+ "# else: print(\"Usage:\", sys.argv[0], \"filename\")\n",
+ "\n",
+ "# if __name__ == \"__main__\": main()\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 128,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(118, 94, 61)"
+ ]
+ },
+ "execution_count": 128,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "ord('v'), ord('^'), ord('=')"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "```\n",
+ "set cell 1 to 94\n",
+ "set cell 2 to 118-94=24\n",
+ "copy cell 1 into cell 0, using cell 3\n",
+ "\n",
+ "set cell 5 to 0\n",
+ "read character into cell 6\n",
+ "while cell 6 != 0\n",
+ " subtract cell 0 from cell 6\n",
+ " if cell 6 == 0\n",
+ " increment cell 5\n",
+ " else\n",
+ " copy cell 2 into cell 0, using cell 3\n",
+ " subtract cell 0 from cell 6\n",
+ " if cell 6 == 0\n",
+ " decrement cell 5\n",
+ " read character into cell 6\n",
+ "output cell 3\n",
+ "```\n"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 129,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "24"
+ ]
+ },
+ "execution_count": 129,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "118-94"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "helloworld= '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 20,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "Hello World!\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "([0, 0, 72, 100, 87, 33, 10], 106, 6)"
+ ]
+ },
+ "execution_count": 20,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "evaluate(helloworld)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "hello"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "([111], 3, 0)"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "evaluate(',[.,]', input='hello')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 196,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "program = '>' + '+' * 94 + '>' + '+' * 24\n",
+ "program += \"\"\"\n",
+ "copy cell 1 into cell 0 using cell 3\n",
+ "\n",
+ "<\n",
+ "[-<+>>>+<<]\n",
+ "\n",
+ ">>\n",
+ "[-<<+>>]\n",
+ "\n",
+ "read into cell 5\n",
+ ">>,\n",
+ "\n",
+ "[\n",
+ " subtract cell 0 from cell 5\n",
+ " <<<<<[->>>>>-<<<<<]\n",
+ " >>>>>\n",
+ "\n",
+ " if cell 5 != 0 do more\n",
+ " [\n",
+ "\n",
+ " copy cell 2 into cell 0 using cell 3\n",
+ " <<<[->+<<<+>>]\n",
+ "\n",
+ " move cell 3 into cell 2\n",
+ " >[-<+>]\n",
+ " <\n",
+ "\n",
+ " subtract cell 0 from cell 5\n",
+ " <<[->>>>>-<<<<<]\n",
+ " >>>>>\n",
+ "\n",
+ " if cell 5 != 0\n",
+ " [\n",
+ " increment cell 4 by 1\n",
+ " <+>\n",
+ "\n",
+ " clear cell 5 to stop the loop\n",
+ " [-]\n",
+ " ]\n",
+ " decrement cell 4 by 2\n",
+ " <-->\n",
+ "\n",
+ " ]\n",
+ "\n",
+ " increment cell 4 by 1\n",
+ " <+\n",
+ "\n",
+ " copy cell 1 into cell 0 using cell 3\n",
+ " <<<[-<+>>>+<<]\n",
+ "\n",
+ " move cell 3 into cell 1\n",
+ " >>[-<<+>>]\n",
+ "\n",
+ " >>\n",
+ "\n",
+ " read next input\n",
+ " ,\n",
+ "]\n",
+ "write the output\n",
+ "<.\n",
+ "\n",
+ "\"\"\""
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 197,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([94, 94, 24, 0, 3, 0], 255, 5)"
+ ]
+ },
+ "execution_count": 197,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "evaluate(program, inp='^^v=^^^v')"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 198,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "'>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++<[-<+>>>+<<]>>[-<<+>>]>>,[<<<<<[->>>>>-<<<<<]>>>>>[<<<[->+<<<+>>]>[-<+>]<<<[->>>>>-<<<<<]>>>>>[<+>[-]]<-->]<+<<<[-<+>>>+<<]>>[-<<+>>]>>,]<.'"
+ ]
+ },
+ "execution_count": 198,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "''.join(cleanup(program))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 123,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "([60, 60, 0, 15, 0], 152, 4)"
+ ]
+ },
+ "execution_count": 123,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "inp = open('02-lifts.txt').read().strip()\n",
+ "evaluate(program, inp=inp)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 124,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def value(instr):\n",
+ " if instr == '^':\n",
+ " return 1\n",
+ " elif instr == 'v':\n",
+ " return -1\n",
+ " else:\n",
+ " return 0"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 125,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def final(sequence):\n",
+ " current = 0\n",
+ " for c in sequence:\n",
+ " current += value(c)\n",
+ " return current"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 126,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "209"
+ ]
+ },
+ "execution_count": 126,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "final(inp)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 193,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "0 ([94, 94, 24, 0, 0, 0], 144, 5) \n",
+ "-1 ([94, 94, 24, 0, 255, 0], 255, 5) v\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vv\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^\n",
+ "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v\n",
+ "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^v^\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=v\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^^v\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vv\n",
+ "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvv\n",
+ "-6 ([94, 94, 24, 0, 250, 0], 255, 5) vvv^^v^v=vv^v^^vvvv\n",
+ "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^\n",
+ "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v\n",
+ "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^\n",
+ "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=\n",
+ "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^\n",
+ "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=\n",
+ "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^\n",
+ "0 ([94, 94, 24, 0, 0, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^\n",
+ "1 ([94, 94, 24, 0, 1, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^\n",
+ "1 ([94, 94, 24, 0, 1, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=\n",
+ "2 ([94, 94, 24, 0, 2, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^\n",
+ "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^\n",
+ "4 ([94, 94, 24, 0, 4, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^\n",
+ "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v\n",
+ "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=\n",
+ "4 ([94, 94, 24, 0, 4, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^\n",
+ "5 ([94, 94, 24, 0, 5, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^\n",
+ "6 ([94, 94, 24, 0, 6, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^\n",
+ "6 ([94, 94, 24, 0, 6, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=\n",
+ "7 ([94, 94, 24, 0, 7, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^\n",
+ "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^\n",
+ "7 ([94, 94, 24, 0, 7, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v\n",
+ "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^\n",
+ "9 ([94, 94, 24, 0, 9, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^\n",
+ "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v\n",
+ "9 ([94, 94, 24, 0, 9, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v^\n",
+ "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v^v\n"
+ ]
+ }
+ ],
+ "source": [
+ "for i in range(50):\n",
+ " print(final(inp[:i]), evaluate(program, inp[:i]), inp[:i])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 194,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(209, ([94, 94, 24, 0, 209, 0], 255, 5))"
+ ]
+ },
+ "execution_count": 194,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "final(inp), evaluate(program, inp)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 199,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "! bf -n part1.bf < 02-lifts.txt > part1.bf.out"
+ ]
+ },
+ {
+ "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
+}