{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "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",
    "    output = []\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 == \".\": output += [cells[cellptr]] # 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] = 0\n",
    "                    else:\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, output\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": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(118, 94, 61)"
      ]
     },
     "execution_count": 3,
     "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": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "118-94"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "helloworld= '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0, 0, 72, 100, 87, 33, 10],\n",
       " 106,\n",
       " 6,\n",
       " [72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate(helloworld)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0], 5, 0, [104, 101, 108, 108, 111])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate(',[.,]', inp='hello')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "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": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([94, 94, 24, 0, 3, 0], 259, 4, [3])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate(program, inp='^^v=^^^v')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++<[-<+>>>+<<]>>[-<<+>>]>>,[<<<<<[->>>>>-<<<<<]>>>>>[<<<[->+<<<+>>]>[-<+>]<<<[->>>>>-<<<<<]>>>>>[<+>[-]]<-->]<+<<<[-<+>>>+<<]>>[-<<+>>]>>,]<.'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "''.join(cleanup(program))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('part1.clean.bf', 'w') as f:\n",
    "    for i, c in enumerate(''.join(cleanup(program))):\n",
    "        f.write('{:03} {}\\n'.format(i, c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "260"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open('part1.clean.bf', 'w').write(''.join(cleanup(program))+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([94, 94, 24, 0, 209, 0], 259, 4, [209])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inp = open('02-lifts.txt').read().strip()\n",
    "evaluate(program, inp=inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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": 14,
   "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": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "209"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final(inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 ([94, 94, 24, 0, 0, 0], 259, 4, [0]) \n",
      "-1 ([94, 94, 24, 0, 255, 0], 259, 4, [255]) v\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vv\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^\n",
      "-1 ([94, 94, 24, 0, 255, 0], 259, 4, [255]) vvv^^\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v\n",
      "-1 ([94, 94, 24, 0, 255, 0], 259, 4, [255]) vvv^^v^\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v^v\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v^v=\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv^^v^v=v\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv^^v^v=vv^\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv^v\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv^^v^v=vv^v^\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v^v=vv^v^^\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv^^v^v=vv^v^^v\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv^v^^vv\n",
      "-5 ([94, 94, 24, 0, 251, 0], 259, 4, [251]) vvv^^v^v=vv^v^^vvv\n",
      "-6 ([94, 94, 24, 0, 250, 0], 259, 4, [250]) vvv^^v^v=vv^v^^vvvv\n",
      "-5 ([94, 94, 24, 0, 251, 0], 259, 4, [251]) vvv^^v^v=vv^v^^vvvv^\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv^v^^vvvv^^\n",
      "-5 ([94, 94, 24, 0, 251, 0], 259, 4, [251]) vvv^^v^v=vv^v^^vvvv^^v\n",
      "-5 ([94, 94, 24, 0, 251, 0], 259, 4, [251]) vvv^^v^v=vv^v^^vvvv^^v=\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv^v^^vvvv^^v=^\n",
      "-4 ([94, 94, 24, 0, 252, 0], 259, 4, [252]) vvv^^v^v=vv^v^^vvvv^^v=^=\n",
      "-3 ([94, 94, 24, 0, 253, 0], 259, 4, [253]) vvv^^v^v=vv^v^^vvvv^^v=^=^\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v^v=vv^v^^vvvv^^v=^=^^\n",
      "-2 ([94, 94, 24, 0, 254, 0], 259, 4, [254]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=\n",
      "-1 ([94, 94, 24, 0, 255, 0], 259, 4, [255]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^\n",
      "0 ([94, 94, 24, 0, 0, 0], 259, 4, [0]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^\n",
      "1 ([94, 94, 24, 0, 1, 0], 259, 4, [1]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^\n",
      "1 ([94, 94, 24, 0, 1, 0], 259, 4, [1]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=\n",
      "2 ([94, 94, 24, 0, 2, 0], 259, 4, [2]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^\n",
      "3 ([94, 94, 24, 0, 3, 0], 259, 4, [3]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^\n",
      "4 ([94, 94, 24, 0, 4, 0], 259, 4, [4]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^\n",
      "3 ([94, 94, 24, 0, 3, 0], 259, 4, [3]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v\n",
      "3 ([94, 94, 24, 0, 3, 0], 259, 4, [3]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=\n",
      "4 ([94, 94, 24, 0, 4, 0], 259, 4, [4]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^\n",
      "5 ([94, 94, 24, 0, 5, 0], 259, 4, [5]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^\n",
      "6 ([94, 94, 24, 0, 6, 0], 259, 4, [6]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^\n",
      "6 ([94, 94, 24, 0, 6, 0], 259, 4, [6]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=\n",
      "7 ([94, 94, 24, 0, 7, 0], 259, 4, [7]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^\n",
      "8 ([94, 94, 24, 0, 8, 0], 259, 4, [8]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^\n",
      "7 ([94, 94, 24, 0, 7, 0], 259, 4, [7]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v\n",
      "8 ([94, 94, 24, 0, 8, 0], 259, 4, [8]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^\n",
      "9 ([94, 94, 24, 0, 9, 0], 259, 4, [9]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^\n",
      "8 ([94, 94, 24, 0, 8, 0], 259, 4, [8]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v\n",
      "9 ([94, 94, 24, 0, 9, 0], 259, 4, [9]) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v^\n",
      "8 ([94, 94, 24, 0, 8, 0], 259, 4, [8]) 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": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(209, ([94, 94, 24, 0, 209, 0], 259, 4, [209]))"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "final(inp), evaluate(program, inp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "! bf -n part1.clean.bf < 02-lifts.txt > part1.bf.out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[209]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[int(b) for b in open('part1.bf.out', 'rb').read()]"
   ]
  },
  {
   "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
}