02-lifts/part1-brainfuck.ipynb

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