09-resolving-the-bill/subsequence.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Subsequence strings\n",
   8     "\n",
   9     "Given two strings `a` and `b`, is `a` a subsequence of `b`?\n",
  10     "\n",
  11     "For example,\n",
  12     "Given:\n",
  13     "a = \"aabcc\",\n",
  14     "b = \"dabaabcacb\",\n",
  15     "\n",
  16     "return True : dAbAaBCaCb\n",
  17     "\n"
  18    ]
  19   },
  20   {
  21    "cell_type": "code",
  22    "execution_count": 1,
  23    "metadata": {
  24     "collapsed": true
  25    },
  26    "outputs": [],
  27    "source": [
  28     "s1 = \"aabcc\"\n",
  29     "s2t = \"dabaabcacb\"\n",
  30     "s2f = \"dabacc\"\n",
  31     "\n",
  32     "s2 = s2t"
  33    ]
  34   },
  35   {
  36    "cell_type": "markdown",
  37    "metadata": {},
  38    "source": [
  39     "`dp_table[i, j]` is True if first `i` characters of `s1` can be found in first `j` characters of `s2`."
  40    ]
  41   },
  42   {
  43    "cell_type": "code",
  44    "execution_count": 2,
  45    "metadata": {
  46     "scrolled": true
  47    },
  48    "outputs": [
  49     {
  50      "data": {
  51       "text/plain": [
  52        "{(0, 0): False,\n",
  53        " (0, 1): False,\n",
  54        " (0, 2): False,\n",
  55        " (0, 3): False,\n",
  56        " (0, 4): False,\n",
  57        " (0, 5): False,\n",
  58        " (0, 6): False,\n",
  59        " (0, 7): False,\n",
  60        " (0, 8): False,\n",
  61        " (0, 9): False,\n",
  62        " (0, 10): False,\n",
  63        " (1, 0): False,\n",
  64        " (1, 1): False,\n",
  65        " (1, 2): False,\n",
  66        " (1, 3): False,\n",
  67        " (1, 4): False,\n",
  68        " (1, 5): False,\n",
  69        " (1, 6): False,\n",
  70        " (1, 7): False,\n",
  71        " (1, 8): False,\n",
  72        " (1, 9): False,\n",
  73        " (1, 10): False,\n",
  74        " (2, 0): False,\n",
  75        " (2, 1): False,\n",
  76        " (2, 2): False,\n",
  77        " (2, 3): False,\n",
  78        " (2, 4): False,\n",
  79        " (2, 5): False,\n",
  80        " (2, 6): False,\n",
  81        " (2, 7): False,\n",
  82        " (2, 8): False,\n",
  83        " (2, 9): False,\n",
  84        " (2, 10): False,\n",
  85        " (3, 0): False,\n",
  86        " (3, 1): False,\n",
  87        " (3, 2): False,\n",
  88        " (3, 3): False,\n",
  89        " (3, 4): False,\n",
  90        " (3, 5): False,\n",
  91        " (3, 6): False,\n",
  92        " (3, 7): False,\n",
  93        " (3, 8): False,\n",
  94        " (3, 9): False,\n",
  95        " (3, 10): False,\n",
  96        " (4, 0): False,\n",
  97        " (4, 1): False,\n",
  98        " (4, 2): False,\n",
  99        " (4, 3): False,\n",
 100        " (4, 4): False,\n",
 101        " (4, 5): False,\n",
 102        " (4, 6): False,\n",
 103        " (4, 7): False,\n",
 104        " (4, 8): False,\n",
 105        " (4, 9): False,\n",
 106        " (4, 10): False,\n",
 107        " (5, 0): False,\n",
 108        " (5, 1): False,\n",
 109        " (5, 2): False,\n",
 110        " (5, 3): False,\n",
 111        " (5, 4): False,\n",
 112        " (5, 5): False,\n",
 113        " (5, 6): False,\n",
 114        " (5, 7): False,\n",
 115        " (5, 8): False,\n",
 116        " (5, 9): False,\n",
 117        " (5, 10): False}"
 118       ]
 119      },
 120      "execution_count": 2,
 121      "metadata": {},
 122      "output_type": "execute_result"
 123     }
 124    ],
 125    "source": [
 126     "dp_table = {(i, j): False\n",
 127     "           for i in range(len(s1)+1)\n",
 128     "           for j in range(len(s2)+1)}\n",
 129     "dp_table"
 130    ]
 131   },
 132   {
 133    "cell_type": "code",
 134    "execution_count": 3,
 135    "metadata": {
 136     "collapsed": true
 137    },
 138    "outputs": [],
 139    "source": [
 140     "def show_table(table):\n",
 141     "    return '\\n'.join(\n",
 142     "        ' '.join(str(table[i, j])[0] for j in sorted(set([k[1] for k in table])))\n",
 143     "        for i in sorted(set([k[0] for k in table])))        "
 144    ]
 145   },
 146   {
 147    "cell_type": "code",
 148    "execution_count": 4,
 149    "metadata": {},
 150    "outputs": [
 151     {
 152      "name": "stdout",
 153      "output_type": "stream",
 154      "text": [
 155       "F F F F F F F F F F F\n",
 156       "F F F F F F F F F F F\n",
 157       "F F F F F F F F F F F\n",
 158       "F F F F F F F F F F F\n",
 159       "F F F F F F F F F F F\n",
 160       "F F F F F F F F F F F\n"
 161      ]
 162     }
 163    ],
 164    "source": [
 165     "print(show_table(dp_table))"
 166    ]
 167   },
 168   {
 169    "cell_type": "code",
 170    "execution_count": 5,
 171    "metadata": {},
 172    "outputs": [
 173     {
 174      "name": "stdout",
 175      "output_type": "stream",
 176      "text": [
 177       "aaaa aaababb\n",
 178       "aa 0 0 ! ! True\n",
 179       "aa 0 1 ! ! True\n",
 180       "aa 0 2 ! ! True\n",
 181       "aa 0 3 ! ! True\n",
 182       "aa 0 4 ! ! True\n",
 183       "aa 0 5 ! ! True\n",
 184       "aa 0 6 ! ! True\n",
 185       "aa 0 7 ! ! True\n",
 186       "s1 1 1 a a True\n",
 187       "s2 1 2 a a True\n",
 188       "s1 1 2 a a True\n",
 189       "s2 1 3 a a True\n",
 190       "s1 1 3 a a True\n",
 191       "s2 1 4 a b True\n",
 192       "s2 1 5 a a True\n",
 193       "s1 1 5 a a True\n",
 194       "s2 1 6 a b True\n",
 195       "s2 1 7 a b True\n",
 196       "s1 2 2 a a True\n",
 197       "s2 2 3 a a True\n",
 198       "s1 2 3 a a True\n",
 199       "s2 2 4 a b True\n",
 200       "s2 2 5 a a True\n",
 201       "s1 2 5 a a True\n",
 202       "s2 2 6 a b True\n",
 203       "s2 2 7 a b True\n",
 204       "s1 3 3 a a True\n",
 205       "s2 3 4 a b True\n",
 206       "s2 3 5 a a True\n",
 207       "s1 3 5 a a True\n",
 208       "s2 3 6 a b True\n",
 209       "s2 3 7 a b True\n",
 210       "xx 4 4 a b False\n",
 211       "s1 4 5 a a True\n",
 212       "s2 4 6 a b True\n",
 213       "s2 4 7 a b True\n",
 214       "T T T T T T T T\n",
 215       "F T T T T T T T\n",
 216       "F F T T T T T T\n",
 217       "F F F T T T T T\n",
 218       "F F F F F T T T\n"
 219      ]
 220     },
 221     {
 222      "data": {
 223       "text/plain": [
 224        "{(1, 1): (0, 0, 'a', 's1'),\n",
 225        " (1, 2): (0, 1, 'a', 's1'),\n",
 226        " (1, 3): (0, 2, 'a', 's1'),\n",
 227        " (1, 4): (1, 3, 'b', 's2'),\n",
 228        " (1, 5): (0, 4, 'a', 's1'),\n",
 229        " (1, 6): (1, 5, 'b', 's2'),\n",
 230        " (1, 7): (1, 6, 'b', 's2'),\n",
 231        " (2, 2): (1, 1, 'a', 's1'),\n",
 232        " (2, 3): (1, 2, 'a', 's1'),\n",
 233        " (2, 4): (2, 3, 'b', 's2'),\n",
 234        " (2, 5): (1, 4, 'a', 's1'),\n",
 235        " (2, 6): (2, 5, 'b', 's2'),\n",
 236        " (2, 7): (2, 6, 'b', 's2'),\n",
 237        " (3, 3): (2, 2, 'a', 's1'),\n",
 238        " (3, 4): (3, 3, 'b', 's2'),\n",
 239        " (3, 5): (2, 4, 'a', 's1'),\n",
 240        " (3, 6): (3, 5, 'b', 's2'),\n",
 241        " (3, 7): (3, 6, 'b', 's2'),\n",
 242        " (4, 5): (3, 4, 'a', 's1'),\n",
 243        " (4, 6): (4, 5, 'b', 's2'),\n",
 244        " (4, 7): (4, 6, 'b', 's2')}"
 245       ]
 246      },
 247      "execution_count": 5,
 248      "metadata": {},
 249      "output_type": "execute_result"
 250     }
 251    ],
 252    "source": [
 253     "s2 = s2f\n",
 254     "\n",
 255     "s1 = 'aaaa'\n",
 256     "s2 = 'aaababb'\n",
 257     "\n",
 258     "print(s1, s2)\n",
 259     "\n",
 260     "dp_table = {(i, j): False\n",
 261     "           for i in range(len(s1)+1)\n",
 262     "           for j in range(len(s2)+1)}\n",
 263     "\n",
 264     "backpointers = {}\n",
 265     "\n",
 266     "for i in range(len(s1)+1):\n",
 267     "    for j in range(i, len(s2)+1):\n",
 268     "        if i == 0 or j == 0:\n",
 269     "            dp_table[i, j] = True\n",
 270     "            print('aa', i, j, '!', '!', dp_table[i, j])\n",
 271     "        else:\n",
 272     "            # extend by character from s2\n",
 273     "            if dp_table[i, j-1]:\n",
 274     "                dp_table[i, j] = True\n",
 275     "                backpointers[i, j] = (i, j-1, s2[j-1], 's2')\n",
 276     "                print('s2', i, j, s1[i-1], s2[j-1], dp_table[i, j])                \n",
 277     "            # extend by character from s1\n",
 278     "            if dp_table[i-1, j-1] and s1[i-1] == s2[j-1]:\n",
 279     "                dp_table[i, j] = True\n",
 280     "                backpointers[i, j] = (i-1, j-1, s1[i-1], 's1')                \n",
 281     "                print('s1', i, j, s1[i-1], s2[j-1], dp_table[i, j])\n",
 282     "            if not dp_table[i, j]:\n",
 283     "                print('xx', i, j, s1[i-1], s2[j-1], dp_table[i, j])\n",
 284     "\n",
 285     "print(show_table(dp_table))\n",
 286     "backpointers"
 287    ]
 288   },
 289   {
 290    "cell_type": "code",
 291    "execution_count": 13,
 292    "metadata": {
 293     "collapsed": true
 294    },
 295    "outputs": [],
 296    "source": [
 297     "def show_backtrace(bps):\n",
 298     "    i = max([0] + [k[0] for k in bps])\n",
 299     "    j = max([0] + [k[1] for k in bps])\n",
 300     "    chars = ''\n",
 301     "    if (i, j) in bps:\n",
 302     "        while i != 0 and j != 0:\n",
 303     "            if bps[i, j][3] == 's1':\n",
 304     "                chars += bps[i, j][2].upper()\n",
 305     "            else:\n",
 306     "                chars += bps[i, j][2]\n",
 307     "            i, j = bps[i, j][0], bps[i, j][1] \n",
 308     "        return ''.join(list(reversed(chars)))\n",
 309     "    else:\n",
 310     "        return ''"
 311    ]
 312   },
 313   {
 314    "cell_type": "code",
 315    "execution_count": 7,
 316    "metadata": {},
 317    "outputs": [
 318     {
 319      "data": {
 320       "text/plain": [
 321        "'AAAbAbb'"
 322       ]
 323      },
 324      "execution_count": 7,
 325      "metadata": {},
 326      "output_type": "execute_result"
 327     }
 328    ],
 329    "source": [
 330     "show_backtrace(backpointers)"
 331    ]
 332   },
 333   {
 334    "cell_type": "code",
 335    "execution_count": 28,
 336    "metadata": {},
 337    "outputs": [
 338     {
 339      "name": "stdout",
 340      "output_type": "stream",
 341      "text": [
 342       "aa 0 0 ! ! True\n",
 343       "aa 0 1 ! ! True\n",
 344       "aa 0 2 ! ! True\n",
 345       "aa 0 3 ! ! True\n",
 346       "aa 0 4 ! ! True\n",
 347       "aa 0 5 ! ! True\n",
 348       "aa 0 6 ! ! True\n",
 349       "aa 0 7 ! ! True\n",
 350       "aa 0 8 ! ! True\n",
 351       "aa 0 9 ! ! True\n",
 352       "aa 0 10 ! ! True\n",
 353       "xx 1 1 a d False\n",
 354       "s1 1 2 a a True\n",
 355       "s2 1 3 a b True\n",
 356       "s2 1 4 a a True\n",
 357       "s1 1 4 a a True\n",
 358       "s2 1 5 a a True\n",
 359       "s1 1 5 a a True\n",
 360       "s2 1 6 a b True\n",
 361       "s2 1 7 a c True\n",
 362       "s2 1 8 a a True\n",
 363       "s1 1 8 a a True\n",
 364       "s2 1 9 a c True\n",
 365       "s2 1 10 a b True\n",
 366       "xx 2 2 a a False\n",
 367       "xx 2 3 a b False\n",
 368       "s1 2 4 a a True\n",
 369       "s2 2 5 a a True\n",
 370       "s1 2 5 a a True\n",
 371       "s2 2 6 a b True\n",
 372       "s2 2 7 a c True\n",
 373       "s2 2 8 a a True\n",
 374       "s1 2 8 a a True\n",
 375       "s2 2 9 a c True\n",
 376       "s2 2 10 a b True\n",
 377       "xx 3 3 a b False\n",
 378       "xx 3 4 a a False\n",
 379       "s1 3 5 a a True\n",
 380       "s2 3 6 a b True\n",
 381       "s2 3 7 a c True\n",
 382       "s2 3 8 a a True\n",
 383       "s1 3 8 a a True\n",
 384       "s2 3 9 a c True\n",
 385       "s2 3 10 a b True\n",
 386       "xx 4 4 a a False\n",
 387       "xx 4 5 a a False\n",
 388       "xx 4 6 a b False\n",
 389       "xx 4 7 a c False\n",
 390       "s1 4 8 a a True\n",
 391       "s2 4 9 a c True\n",
 392       "s2 4 10 a b True\n"
 393      ]
 394     },
 395     {
 396      "data": {
 397       "text/plain": [
 398        "True"
 399       ]
 400      },
 401      "execution_count": 28,
 402      "metadata": {},
 403      "output_type": "execute_result"
 404     }
 405    ],
 406    "source": [
 407     "is_subseq(s1, s2t, debug=True)"
 408    ]
 409   },
 410   {
 411    "cell_type": "code",
 412    "execution_count": 27,
 413    "metadata": {
 414     "collapsed": true
 415    },
 416    "outputs": [],
 417    "source": [
 418     "def is_subseq(seq1, seq2, return_backpointers=False, return_table=False, debug=False):\n",
 419     "    \"\"\"Return true if seq1 is a subsequence of seq2.\n",
 420     "    If return_backpointers, also return the set of backpointers to\n",
 421     "    reconstruct the subsequence\"\"\"\n",
 422     "    \n",
 423     "    # dp_table[i, j] is True if first i characters of seq1 can\n",
 424     "    # be found in the first j characters of seq2\n",
 425     "  \n",
 426     "    dp_table = {(i, j): False\n",
 427     "               for i in range(len(seq1)+1)\n",
 428     "               for j in range(len(seq2)+1)}\n",
 429     "\n",
 430     "    backpointers = {}\n",
 431     "    \n",
 432     "    for i in range(len(seq1)+1):\n",
 433     "        for j in range(i, len(seq2)+1):\n",
 434     "            if i == 0 or j == 0:\n",
 435     "                dp_table[i, j] = True\n",
 436     "                if debug: print('aa', i, j, '!', '!', dp_table[i, j])\n",
 437     "            else:\n",
 438     "                # extend by character from s2\n",
 439     "                if dp_table[i, j-1]:\n",
 440     "                    dp_table[i, j] = True\n",
 441     "                    backpointers[i, j] = (i, j-1, seq2[j-1], 's2')\n",
 442     "                    if debug: print('s2', i, j, seq1[i-1], seq2[j-1], dp_table[i, j])                \n",
 443     "                # extend by character from s1\n",
 444     "                if dp_table[i-1, j-1] and seq1[i-1] == seq2[j-1]:\n",
 445     "                    dp_table[i, j] = True\n",
 446     "                    backpointers[i, j] = (i-1, j-1, seq1[i-1], 's1')                \n",
 447     "                    if debug: print('s1', i, j, seq1[i-1], seq2[j-1], dp_table[i, j])\n",
 448     "                if not dp_table[i, j]:\n",
 449     "                    if debug: print('xx', i, j, seq1[i-1], seq2[j-1], dp_table[i, j]) \n",
 450     "   \n",
 451     "#     if return_backpointers:\n",
 452     "#         return dp_table[len(seq1), len(seq2)], backpointers\n",
 453     "#     else:\n",
 454     "#         return dp_table[len(seq1), len(seq2)]\n",
 455     "    \n",
 456     "    if return_backpointers or return_table:\n",
 457     "        retval = [dp_table[len(seq1), len(seq2)]]\n",
 458     "        if return_backpointers:\n",
 459     "            retval += [backpointers]\n",
 460     "        if return_table:\n",
 461     "            retval += [dp_table]\n",
 462     "        return tuple(retval)\n",
 463     "    else:\n",
 464     "        return dp_table[len(seq1), len(seq2)]"
 465    ]
 466   },
 467   {
 468    "cell_type": "code",
 469    "execution_count": 37,
 470    "metadata": {
 471     "collapsed": true
 472    },
 473    "outputs": [],
 474    "source": [
 475     "def show_annotated_table(table, bps):\n",
 476     "    return '\\n'.join(' '.join('.' if (i, j) not in bps else bps[i, j][2] if table[i, j] else '.' for j in sorted(set([k[1] for k in table])))\n",
 477     "        for i in sorted(set([k[0] for k in table])))"
 478    ]
 479   },
 480   {
 481    "cell_type": "code",
 482    "execution_count": 29,
 483    "metadata": {},
 484    "outputs": [
 485     {
 486      "data": {
 487       "text/plain": [
 488        "True"
 489       ]
 490      },
 491      "execution_count": 29,
 492      "metadata": {},
 493      "output_type": "execute_result"
 494     }
 495    ],
 496    "source": [
 497     "tf, bps, tb = is_subseq(s1, s2t, return_backpointers=True, return_table=True)\n",
 498     "tf"
 499    ]
 500   },
 501   {
 502    "cell_type": "code",
 503    "execution_count": 20,
 504    "metadata": {},
 505    "outputs": [
 506     {
 507      "data": {
 508       "text/plain": [
 509        "'AbAAbcAcb'"
 510       ]
 511      },
 512      "execution_count": 20,
 513      "metadata": {},
 514      "output_type": "execute_result"
 515     }
 516    ],
 517    "source": [
 518     "show_backtrace(bps)"
 519    ]
 520   },
 521   {
 522    "cell_type": "code",
 523    "execution_count": 32,
 524    "metadata": {},
 525    "outputs": [
 526     {
 527      "name": "stdout",
 528      "output_type": "stream",
 529      "text": [
 530       "T T T T T T T T T T T\n",
 531       "F F T T T T T T T T T\n",
 532       "F F F F T T T T T T T\n",
 533       "F F F F F T T T T T T\n",
 534       "F F F F F F F F T T T\n"
 535      ]
 536     }
 537    ],
 538    "source": [
 539     "print(show_table(tb))"
 540    ]
 541   },
 542   {
 543    "cell_type": "code",
 544    "execution_count": 38,
 545    "metadata": {},
 546    "outputs": [
 547     {
 548      "name": "stdout",
 549      "output_type": "stream",
 550      "text": [
 551       ". . . . . . . . . . .\n",
 552       ". . a b a a b c a c b\n",
 553       ". . . . a a b c a c b\n",
 554       ". . . . . a b c a c b\n",
 555       ". . . . . . . . a c b\n"
 556      ]
 557     }
 558    ],
 559    "source": [
 560     "print(show_annotated_table(tb, bps))"
 561    ]
 562   },
 563   {
 564    "cell_type": "code",
 565    "execution_count": 21,
 566    "metadata": {},
 567    "outputs": [
 568     {
 569      "data": {
 570       "text/plain": [
 571        "False"
 572       ]
 573      },
 574      "execution_count": 21,
 575      "metadata": {},
 576      "output_type": "execute_result"
 577     }
 578    ],
 579    "source": [
 580     "len(show_backtrace(bps)) == len(s2t)"
 581    ]
 582   },
 583   {
 584    "cell_type": "code",
 585    "execution_count": 24,
 586    "metadata": {},
 587    "outputs": [
 588     {
 589      "data": {
 590       "text/plain": [
 591        "('aaaa', 'dabaabcacb')"
 592       ]
 593      },
 594      "execution_count": 24,
 595      "metadata": {},
 596      "output_type": "execute_result"
 597     }
 598    ],
 599    "source": [
 600     "s1, s2t"
 601    ]
 602   },
 603   {
 604    "cell_type": "code",
 605    "execution_count": 23,
 606    "metadata": {},
 607    "outputs": [
 608     {
 609      "data": {
 610       "text/plain": [
 611        "{(1, 2): (0, 1, 'a', 's1'),\n",
 612        " (1, 3): (1, 2, 'b', 's2'),\n",
 613        " (1, 4): (0, 3, 'a', 's1'),\n",
 614        " (1, 5): (0, 4, 'a', 's1'),\n",
 615        " (1, 6): (1, 5, 'b', 's2'),\n",
 616        " (1, 7): (1, 6, 'c', 's2'),\n",
 617        " (1, 8): (0, 7, 'a', 's1'),\n",
 618        " (1, 9): (1, 8, 'c', 's2'),\n",
 619        " (1, 10): (1, 9, 'b', 's2'),\n",
 620        " (2, 4): (1, 3, 'a', 's1'),\n",
 621        " (2, 5): (1, 4, 'a', 's1'),\n",
 622        " (2, 6): (2, 5, 'b', 's2'),\n",
 623        " (2, 7): (2, 6, 'c', 's2'),\n",
 624        " (2, 8): (1, 7, 'a', 's1'),\n",
 625        " (2, 9): (2, 8, 'c', 's2'),\n",
 626        " (2, 10): (2, 9, 'b', 's2'),\n",
 627        " (3, 5): (2, 4, 'a', 's1'),\n",
 628        " (3, 6): (3, 5, 'b', 's2'),\n",
 629        " (3, 7): (3, 6, 'c', 's2'),\n",
 630        " (3, 8): (2, 7, 'a', 's1'),\n",
 631        " (3, 9): (3, 8, 'c', 's2'),\n",
 632        " (3, 10): (3, 9, 'b', 's2'),\n",
 633        " (4, 8): (3, 7, 'a', 's1'),\n",
 634        " (4, 9): (4, 8, 'c', 's2'),\n",
 635        " (4, 10): (4, 9, 'b', 's2')}"
 636       ]
 637      },
 638      "execution_count": 23,
 639      "metadata": {},
 640      "output_type": "execute_result"
 641     }
 642    ],
 643    "source": [
 644     "bps"
 645    ]
 646   },
 647   {
 648    "cell_type": "code",
 649    "execution_count": null,
 650    "metadata": {},
 651    "outputs": [],
 652    "source": [
 653     "is_subseq(s1, s2f)"
 654    ]
 655   },
 656   {
 657    "cell_type": "code",
 658    "execution_count": null,
 659    "metadata": {},
 660    "outputs": [],
 661    "source": [
 662     "is_subseq('aaaa', 'aaababb', return_backpointers=True, debug=True)"
 663    ]
 664   },
 665   {
 666    "cell_type": "code",
 667    "execution_count": null,
 668    "metadata": {
 669     "collapsed": true
 670    },
 671    "outputs": [],
 672    "source": []
 673   }
 674  ],
 675  "metadata": {
 676   "kernelspec": {
 677    "display_name": "Python 3",
 678    "language": "python",
 679    "name": "python3"
 680   },
 681   "language_info": {
 682    "codemirror_mode": {
 683     "name": "ipython",
 684     "version": 3
 685    },
 686    "file_extension": ".py",
 687    "mimetype": "text/x-python",
 688    "name": "python",
 689    "nbconvert_exporter": "python",
 690    "pygments_lexer": "ipython3",
 691    "version": "3.5.2+"
 692   }
 693  },
 694  "nbformat": 4,
 695  "nbformat_minor": 1
 696 }