{
"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
}