02-lifts/part1-brainfuck.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 121,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "#!/usr/bin/python\n",
  10     "#\n",
  11     "# Brainfuck Interpreter\n",
  12     "# Copyright 2011 Sebastian Kaspari\n",
  13     "#\n",
  14     "# Usage: ./brainfuck.py [FILE]\n",
  15     "\n",
  16     "import sys\n",
  17     "\n",
  18     "def execute(filename):\n",
  19     "    f = open(filename, \"r\")\n",
  20     "    evaluate(f.read())\n",
  21     "    f.close()\n",
  22     "\n",
  23     "\n",
  24     "def evaluate(code, inp=None, debug=False):\n",
  25     "    code     = cleanup(list(code))\n",
  26     "    bracemap = buildbracemap(code)\n",
  27     "\n",
  28     "    cells, codeptr, cellptr = [0], 0, 0\n",
  29     "    inputptr = 0\n",
  30     "\n",
  31     "    try:\n",
  32     "        while codeptr < len(code):\n",
  33     "            command = code[codeptr]\n",
  34     "            \n",
  35     "            if debug:\n",
  36     "                print(command, cellptr, cells)\n",
  37     "\n",
  38     "            if command == \">\":\n",
  39     "                cellptr += 1\n",
  40     "                if cellptr == len(cells): cells.append(0)\n",
  41     "\n",
  42     "            if command == \"<\":\n",
  43     "                cellptr = 0 if cellptr <= 0 else cellptr - 1\n",
  44     "\n",
  45     "            if command == \"+\":\n",
  46     "                cells[cellptr] = cells[cellptr] + 1 if cells[cellptr] < 255 else 0\n",
  47     "\n",
  48     "            if command == \"-\":\n",
  49     "                cells[cellptr] = cells[cellptr] - 1 if cells[cellptr] > 0 else 255\n",
  50     "\n",
  51     "            if command == \"[\" and cells[cellptr] == 0: codeptr = bracemap[codeptr]\n",
  52     "            if command == \"]\" and cells[cellptr] != 0: codeptr = bracemap[codeptr]\n",
  53     "            if command == \".\": sys.stdout.write(chr(cells[cellptr]))\n",
  54     "            if command == \",\": \n",
  55     "                if inp is not None:\n",
  56     "                    if inputptr >= len(inp):\n",
  57     "                        raise EOFError\n",
  58     "                    cells[cellptr] = ord(inp[inputptr])\n",
  59     "                    inputptr += 1\n",
  60     "                else:\n",
  61     "                    cells[cellptr] = ord(getch.getch())\n",
  62     "\n",
  63     "            codeptr += 1\n",
  64     "    except EOFError:\n",
  65     "        pass\n",
  66     "    return cells, codeptr, cellptr\n",
  67     "\n",
  68     "\n",
  69     "def cleanup(code):\n",
  70     "      return list(filter(lambda x: x in ['.', ',', '[', ']', '<', '>', '+', '-'], code))\n",
  71     "\n",
  72     "\n",
  73     "def buildbracemap(code):\n",
  74     "    temp_bracestack, bracemap = [], {}\n",
  75     "\n",
  76     "    for position, command in enumerate(code):\n",
  77     "        if command == \"[\": temp_bracestack.append(position)\n",
  78     "        if command == \"]\":\n",
  79     "            start = temp_bracestack.pop()\n",
  80     "            bracemap[start] = position\n",
  81     "            bracemap[position] = start\n",
  82     "    return bracemap\n",
  83     "\n",
  84     "\n",
  85     "# def main():\n",
  86     "#     if len(sys.argv) == 2: execute(sys.argv[1])\n",
  87     "#     else: print(\"Usage:\", sys.argv[0], \"filename\")\n",
  88     "\n",
  89     "# if __name__ == \"__main__\": main()\n"
  90    ]
  91   },
  92   {
  93    "cell_type": "code",
  94    "execution_count": 128,
  95    "metadata": {},
  96    "outputs": [
  97     {
  98      "data": {
  99       "text/plain": [
 100        "(118, 94, 61)"
 101       ]
 102      },
 103      "execution_count": 128,
 104      "metadata": {},
 105      "output_type": "execute_result"
 106     }
 107    ],
 108    "source": [
 109     "ord('v'), ord('^'), ord('=')"
 110    ]
 111   },
 112   {
 113    "cell_type": "markdown",
 114    "metadata": {},
 115    "source": [
 116     "```\n",
 117     "set cell 1 to 94\n",
 118     "set cell 2 to 118-94=24\n",
 119     "copy cell 1 into cell 0, using cell 3\n",
 120     "\n",
 121     "set cell 5 to 0\n",
 122     "read character into cell 6\n",
 123     "while cell 6 != 0\n",
 124     "  subtract cell 0 from cell 6\n",
 125     "  if cell 6 == 0\n",
 126     "     increment cell 5\n",
 127     "  else\n",
 128     "     copy cell 2 into cell 0, using cell 3\n",
 129     "     subtract cell 0 from cell 6\n",
 130     "     if cell 6 == 0\n",
 131     "       decrement cell 5\n",
 132     "  read character into cell 6\n",
 133     "output cell 3\n",
 134     "```\n"
 135    ]
 136   },
 137   {
 138    "cell_type": "code",
 139    "execution_count": 129,
 140    "metadata": {},
 141    "outputs": [
 142     {
 143      "data": {
 144       "text/plain": [
 145        "24"
 146       ]
 147      },
 148      "execution_count": 129,
 149      "metadata": {},
 150      "output_type": "execute_result"
 151     }
 152    ],
 153    "source": [
 154     "118-94"
 155    ]
 156   },
 157   {
 158    "cell_type": "code",
 159    "execution_count": 7,
 160    "metadata": {
 161     "collapsed": true
 162    },
 163    "outputs": [],
 164    "source": [
 165     "helloworld= '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.'"
 166    ]
 167   },
 168   {
 169    "cell_type": "code",
 170    "execution_count": 20,
 171    "metadata": {},
 172    "outputs": [
 173     {
 174      "name": "stdout",
 175      "output_type": "stream",
 176      "text": [
 177       "Hello World!\n"
 178      ]
 179     },
 180     {
 181      "data": {
 182       "text/plain": [
 183        "([0, 0, 72, 100, 87, 33, 10], 106, 6)"
 184       ]
 185      },
 186      "execution_count": 20,
 187      "metadata": {},
 188      "output_type": "execute_result"
 189     }
 190    ],
 191    "source": [
 192     "evaluate(helloworld)"
 193    ]
 194   },
 195   {
 196    "cell_type": "code",
 197    "execution_count": 19,
 198    "metadata": {},
 199    "outputs": [
 200     {
 201      "name": "stdout",
 202      "output_type": "stream",
 203      "text": [
 204       "hello"
 205      ]
 206     },
 207     {
 208      "data": {
 209       "text/plain": [
 210        "([111], 3, 0)"
 211       ]
 212      },
 213      "execution_count": 19,
 214      "metadata": {},
 215      "output_type": "execute_result"
 216     }
 217    ],
 218    "source": [
 219     "evaluate(',[.,]', input='hello')"
 220    ]
 221   },
 222   {
 223    "cell_type": "code",
 224    "execution_count": 196,
 225    "metadata": {},
 226    "outputs": [],
 227    "source": [
 228     "program = '>' + '+' * 94 + '>' + '+' * 24\n",
 229     "program += \"\"\"\n",
 230     "copy cell 1 into cell 0 using cell 3\n",
 231     "\n",
 232     "<\n",
 233     "[-<+>>>+<<]\n",
 234     "\n",
 235     ">>\n",
 236     "[-<<+>>]\n",
 237     "\n",
 238     "read into cell 5\n",
 239     ">>,\n",
 240     "\n",
 241     "[\n",
 242     "    subtract cell 0 from cell 5\n",
 243     "    <<<<<[->>>>>-<<<<<]\n",
 244     "    >>>>>\n",
 245     "\n",
 246     "    if cell 5 != 0 do more\n",
 247     "    [\n",
 248     "\n",
 249     "      copy cell 2 into cell 0 using cell 3\n",
 250     "      <<<[->+<<<+>>]\n",
 251     "\n",
 252     "      move cell 3 into cell 2\n",
 253     "      >[-<+>]\n",
 254     "      <\n",
 255     "\n",
 256     "      subtract cell 0 from cell 5\n",
 257     "      <<[->>>>>-<<<<<]\n",
 258     "      >>>>>\n",
 259     "\n",
 260     "      if cell 5 != 0\n",
 261     "      [\n",
 262     "        increment cell 4 by 1\n",
 263     "        <+>\n",
 264     "\n",
 265     "        clear cell 5 to stop the loop\n",
 266     "        [-]\n",
 267     "      ]\n",
 268     "      decrement cell 4 by 2\n",
 269     "      <-->\n",
 270     "\n",
 271     "    ]\n",
 272     "\n",
 273     "    increment cell 4 by 1\n",
 274     "    <+\n",
 275     "\n",
 276     "    copy cell 1 into cell 0 using cell 3\n",
 277     "    <<<[-<+>>>+<<]\n",
 278     "\n",
 279     "    move cell 3 into cell 1\n",
 280     "    >>[-<<+>>]\n",
 281     "\n",
 282     "    >>\n",
 283     "\n",
 284     "    read next input\n",
 285     "    ,\n",
 286     "]\n",
 287     "write the output\n",
 288     "<.\n",
 289     "\n",
 290     "\"\"\""
 291    ]
 292   },
 293   {
 294    "cell_type": "code",
 295    "execution_count": 200,
 296    "metadata": {},
 297    "outputs": [
 298     {
 299      "data": {
 300       "text/plain": [
 301        "([94, 94, 24, 0, 3, 0], 255, 5)"
 302       ]
 303      },
 304      "execution_count": 200,
 305      "metadata": {},
 306      "output_type": "execute_result"
 307     }
 308    ],
 309    "source": [
 310     "evaluate(program, inp='^^v=^^^v')"
 311    ]
 312   },
 313   {
 314    "cell_type": "code",
 315    "execution_count": 198,
 316    "metadata": {},
 317    "outputs": [
 318     {
 319      "data": {
 320       "text/plain": [
 321        "'>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++<[-<+>>>+<<]>>[-<<+>>]>>,[<<<<<[->>>>>-<<<<<]>>>>>[<<<[->+<<<+>>]>[-<+>]<<<[->>>>>-<<<<<]>>>>>[<+>[-]]<-->]<+<<<[-<+>>>+<<]>>[-<<+>>]>>,]<.'"
 322       ]
 323      },
 324      "execution_count": 198,
 325      "metadata": {},
 326      "output_type": "execute_result"
 327     }
 328    ],
 329    "source": [
 330     "''.join(cleanup(program))"
 331    ]
 332   },
 333   {
 334    "cell_type": "code",
 335    "execution_count": 123,
 336    "metadata": {},
 337    "outputs": [
 338     {
 339      "data": {
 340       "text/plain": [
 341        "([60, 60, 0, 15, 0], 152, 4)"
 342       ]
 343      },
 344      "execution_count": 123,
 345      "metadata": {},
 346      "output_type": "execute_result"
 347     }
 348    ],
 349    "source": [
 350     "inp = open('02-lifts.txt').read().strip()\n",
 351     "evaluate(program, inp=inp)"
 352    ]
 353   },
 354   {
 355    "cell_type": "code",
 356    "execution_count": 124,
 357    "metadata": {
 358     "collapsed": true
 359    },
 360    "outputs": [],
 361    "source": [
 362     "def value(instr):\n",
 363     "    if instr == '^':\n",
 364     "        return 1\n",
 365     "    elif instr == 'v':\n",
 366     "        return -1\n",
 367     "    else:\n",
 368     "        return 0"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 125,
 374    "metadata": {
 375     "collapsed": true
 376    },
 377    "outputs": [],
 378    "source": [
 379     "def final(sequence):\n",
 380     "    current = 0\n",
 381     "    for c in sequence:\n",
 382     "        current += value(c)\n",
 383     "    return current"
 384    ]
 385   },
 386   {
 387    "cell_type": "code",
 388    "execution_count": 126,
 389    "metadata": {},
 390    "outputs": [
 391     {
 392      "data": {
 393       "text/plain": [
 394        "209"
 395       ]
 396      },
 397      "execution_count": 126,
 398      "metadata": {},
 399      "output_type": "execute_result"
 400     }
 401    ],
 402    "source": [
 403     "final(inp)"
 404    ]
 405   },
 406   {
 407    "cell_type": "code",
 408    "execution_count": 193,
 409    "metadata": {
 410     "scrolled": true
 411    },
 412    "outputs": [
 413     {
 414      "name": "stdout",
 415      "output_type": "stream",
 416      "text": [
 417       "0 ([94, 94, 24, 0, 0, 0], 144, 5) \n",
 418       "-1 ([94, 94, 24, 0, 255, 0], 255, 5) v\n",
 419       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vv\n",
 420       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv\n",
 421       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^\n",
 422       "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^\n",
 423       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v\n",
 424       "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^v^\n",
 425       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v\n",
 426       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=\n",
 427       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=v\n",
 428       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv\n",
 429       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^\n",
 430       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v\n",
 431       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^\n",
 432       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^\n",
 433       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^^v\n",
 434       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vv\n",
 435       "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvv\n",
 436       "-6 ([94, 94, 24, 0, 250, 0], 255, 5) vvv^^v^v=vv^v^^vvvv\n",
 437       "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^\n",
 438       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^\n",
 439       "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v\n",
 440       "-5 ([94, 94, 24, 0, 251, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=\n",
 441       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^\n",
 442       "-4 ([94, 94, 24, 0, 252, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=\n",
 443       "-3 ([94, 94, 24, 0, 253, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^\n",
 444       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^\n",
 445       "-2 ([94, 94, 24, 0, 254, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=\n",
 446       "-1 ([94, 94, 24, 0, 255, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^\n",
 447       "0 ([94, 94, 24, 0, 0, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^\n",
 448       "1 ([94, 94, 24, 0, 1, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^\n",
 449       "1 ([94, 94, 24, 0, 1, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=\n",
 450       "2 ([94, 94, 24, 0, 2, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^\n",
 451       "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^\n",
 452       "4 ([94, 94, 24, 0, 4, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^\n",
 453       "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v\n",
 454       "3 ([94, 94, 24, 0, 3, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=\n",
 455       "4 ([94, 94, 24, 0, 4, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^\n",
 456       "5 ([94, 94, 24, 0, 5, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^\n",
 457       "6 ([94, 94, 24, 0, 6, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^\n",
 458       "6 ([94, 94, 24, 0, 6, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=\n",
 459       "7 ([94, 94, 24, 0, 7, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^\n",
 460       "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^\n",
 461       "7 ([94, 94, 24, 0, 7, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v\n",
 462       "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^\n",
 463       "9 ([94, 94, 24, 0, 9, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^\n",
 464       "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v\n",
 465       "9 ([94, 94, 24, 0, 9, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v^\n",
 466       "8 ([94, 94, 24, 0, 8, 0], 255, 5) vvv^^v^v=vv^v^^vvvv^^v=^=^^=^^^=^^^v=^^^=^^v^^v^v\n"
 467      ]
 468     }
 469    ],
 470    "source": [
 471     "for i in range(50):\n",
 472     "    print(final(inp[:i]), evaluate(program, inp[:i]), inp[:i])"
 473    ]
 474   },
 475   {
 476    "cell_type": "code",
 477    "execution_count": 194,
 478    "metadata": {
 479     "scrolled": true
 480    },
 481    "outputs": [
 482     {
 483      "data": {
 484       "text/plain": [
 485        "(209, ([94, 94, 24, 0, 209, 0], 255, 5))"
 486       ]
 487      },
 488      "execution_count": 194,
 489      "metadata": {},
 490      "output_type": "execute_result"
 491     }
 492    ],
 493    "source": [
 494     "final(inp), evaluate(program, inp)"
 495    ]
 496   },
 497   {
 498    "cell_type": "code",
 499    "execution_count": 199,
 500    "metadata": {
 501     "collapsed": true
 502    },
 503    "outputs": [],
 504    "source": [
 505     "! bf -n part1.bf < 02-lifts.txt > part1.bf.out"
 506    ]
 507   },
 508   {
 509    "cell_type": "code",
 510    "execution_count": null,
 511    "metadata": {
 512     "collapsed": true
 513    },
 514    "outputs": [],
 515    "source": []
 516   }
 517  ],
 518  "metadata": {
 519   "kernelspec": {
 520    "display_name": "Python 3",
 521    "language": "python",
 522    "name": "python3"
 523   },
 524   "language_info": {
 525    "codemirror_mode": {
 526     "name": "ipython",
 527     "version": 3
 528    },
 529    "file_extension": ".py",
 530    "mimetype": "text/x-python",
 531    "name": "python",
 532    "nbconvert_exporter": "python",
 533    "pygments_lexer": "ipython3",
 534    "version": "3.5.2+"
 535   }
 536  },
 537  "nbformat": 4,
 538  "nbformat_minor": 2
 539 }