02-lifts/part2-brainfuck.ipynb

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