Added execution traces

[ou-summer-of-code-2017.git] / 09-resolving-the-bill / subsequence.ipynb

diff --git a/09-resolving-the-bill/subsequence.ipynb b/09-resolving-the-bill/subsequence.ipynb
index 0966d73fa8d5afdfd8817465e205fc9f02a2fe5d..53055e8e6f94b1d130292c9549514a5a2f91c358 100644 (file)
--- a/09-resolving-the-bill/subsequence.ipynb
+++ b/09-resolving-the-bill/subsequence.ipynb
@@ -19,7 +19,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 7,
+   "execution_count": 1,
    "metadata": {
     "collapsed": true
    },
@@ -30,7 +30,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 8,
+   "execution_count": 55,
    "metadata": {
     "collapsed": true
    },
@@ -52,7 +52,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 9,
+   "execution_count": 3,
    "metadata": {
     "scrolled": true
    },
@@ -128,7 +128,7 @@
        " (5, 10): False}"
       ]
      },
-     "execution_count": 9,
+     "execution_count": 3,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -142,7 +142,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 10,
+   "execution_count": 4,
    "metadata": {
     "collapsed": true
    },
@@ -156,7 +156,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 11,
+   "execution_count": 5,
    "metadata": {},
    "outputs": [
     {
@@ -178,7 +178,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 12,
+   "execution_count": 6,
    "metadata": {},
    "outputs": [
     {
@@ -255,7 +255,7 @@
        " (4, 7): (4, 6, 'b', 's2')}"
       ]
      },
-     "execution_count": 12,
+     "execution_count": 6,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -299,7 +299,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 13,
+   "execution_count": 7,
    "metadata": {
     "collapsed": true
    },
@@ -323,7 +323,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 14,
+   "execution_count": 8,
    "metadata": {},
    "outputs": [
     {
@@ -332,7 +332,7 @@
        "'AAAbAbb'"
       ]
      },
-     "execution_count": 14,
+     "execution_count": 8,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -343,7 +343,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 15,
+   "execution_count": 9,
    "metadata": {
     "collapsed": true
    },
@@ -400,7 +400,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 16,
+   "execution_count": 10,
    "metadata": {
     "scrolled": true
    },
@@ -468,7 +468,7 @@
        "True"
       ]
      },
-     "execution_count": 16,
+     "execution_count": 10,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -479,7 +479,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 17,
+   "execution_count": 11,
    "metadata": {
     "collapsed": true
    },
@@ -492,7 +492,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 18,
+   "execution_count": 12,
    "metadata": {},
    "outputs": [
     {
@@ -501,7 +501,7 @@
        "True"
       ]
      },
-     "execution_count": 18,
+     "execution_count": 12,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -513,7 +513,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 19,
+   "execution_count": 13,
    "metadata": {},
    "outputs": [
     {
@@ -522,7 +522,7 @@
        "'AbAAbcAcb'"
       ]
      },
-     "execution_count": 19,
+     "execution_count": 13,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -533,7 +533,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 20,
+   "execution_count": 14,
    "metadata": {},
    "outputs": [
     {
@@ -554,7 +554,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 21,
+   "execution_count": 15,
    "metadata": {},
    "outputs": [
     {
@@ -575,7 +575,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 22,
+   "execution_count": 16,
    "metadata": {},
    "outputs": [
     {
@@ -584,7 +584,7 @@
        "False"
       ]
      },
-     "execution_count": 22,
+     "execution_count": 16,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -595,7 +595,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 23,
+   "execution_count": 17,
    "metadata": {},
    "outputs": [
     {
@@ -604,7 +604,7 @@
        "('aaaa', 'dabaabcacb')"
       ]
      },
-     "execution_count": 23,
+     "execution_count": 17,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -615,7 +615,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 24,
+   "execution_count": 18,
    "metadata": {},
    "outputs": [
     {
@@ -648,7 +648,7 @@
        " (4, 10): (4, 9, 'b', 's2')}"
       ]
      },
-     "execution_count": 24,
+     "execution_count": 18,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -659,7 +659,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 25,
+   "execution_count": 19,
    "metadata": {},
    "outputs": [
     {
@@ -668,7 +668,7 @@
        "False"
       ]
      },
-     "execution_count": 25,
+     "execution_count": 19,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -679,7 +679,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 26,
+   "execution_count": 20,
    "metadata": {
     "scrolled": true
    },
@@ -753,7 +753,7 @@
        "  (4, 7): (4, 6, 'b', 's2')})"
       ]
      },
-     "execution_count": 26,
+     "execution_count": 20,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -764,13 +764,14 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 27,
+   "execution_count": 77,
    "metadata": {
     "collapsed": true
    },
    "outputs": [],
    "source": [
     "def is_subseq_recursive(s1, s2):\n",
+    "#     print(s1, s2)\n",
     "    if not s1:\n",
     "        return True\n",
     "    elif len(s1) > len(s2):\n",
@@ -784,7 +785,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 45,
+   "execution_count": 67,
    "metadata": {
     "collapsed": true
    },
@@ -805,6 +806,17 @@
   {
    "cell_type": "code",
    "execution_count": 28,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "import uuid"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
@@ -813,7 +825,7 @@
        "True"
       ]
      },
-     "execution_count": 28,
+     "execution_count": 24,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -824,7 +836,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 29,
+   "execution_count": 25,
    "metadata": {},
    "outputs": [
     {
@@ -833,7 +845,7 @@
        "False"
       ]
      },
-     "execution_count": 29,
+     "execution_count": 25,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -842,6 +854,311 @@
     "is_subseq_recursive(s1, s2f)"
    ]
   },
+  {
+   "cell_type": "code",
+   "execution_count": 76,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def is_subseq_recursive_dot(s1, s2):\n",
+    "    node_id = uuid.uuid4().hex\n",
+    "    node_string = 'n{} [label=\"{}\\\\n{}\"];'.format(node_id, s1, s2)\n",
+    "#     print(s1, s2, node_string)\n",
+    "    if not s1:\n",
+    "        return node_id, ['n{} [label=\"-\\\\n{}\\\\nTrue\"];'.format(node_id, s2)]\n",
+    "    elif len(s1) > len(s2):\n",
+    "        return node_id, ['n{} [label=\"{}\\\\n{}\\\\nFalse\"];'.format(node_id, s1, s2)]\n",
+    "    else:\n",
+    "        if s1[-1] == s2[-1]:\n",
+    "            node1_id, node1_graph = is_subseq_recursive_dot(s1[:-1], s2[:-1])\n",
+    "            node2_id, node2_graph = is_subseq_recursive_dot(s1, s2[:-1])\n",
+    "            return node_id, ([node_string, \n",
+    "                    'n{} -> n{};'.format(node_id, node1_id), \n",
+    "                    'n{} -> n{};'.format(node_id, node2_id)] + \n",
+    "                    node1_graph + node2_graph)\n",
+    "        else:\n",
+    "            node1_id, node1_graph = is_subseq_recursive_dot(s1, s2[:-1])\n",
+    "            return node_id, ([node_string, \n",
+    "                    'n{} -> n{};'.format(node_id, node1_id)] + \n",
+    "                    node1_graph)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 51,
+   "metadata": {},
+   "outputs": [
+    {
+     "data": {
+      "text/plain": [
+       "'ae50b62c418f4ba8902bfa8bab4948e0'"
+      ]
+     },
+     "execution_count": 51,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "uuid.uuid4().hex"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 78,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "nd5092f0e2ba047ba9b662e17a650791a [label=\"daabcc\\ndabaabcacb\"];\n",
+      "nd5092f0e2ba047ba9b662e17a650791a -> nc243f60568164ba495d5f89dc1075a85;\n",
+      "nc243f60568164ba495d5f89dc1075a85 [label=\"daabcc\\ndabaabcac\"];\n",
+      "nc243f60568164ba495d5f89dc1075a85 -> n933e3a2ebca34034866b98ab19ee3f90;\n",
+      "nc243f60568164ba495d5f89dc1075a85 -> n3c49af7ea69340f2a97827a0547f73db;\n",
+      "n933e3a2ebca34034866b98ab19ee3f90 [label=\"daabc\\ndabaabca\"];\n",
+      "n933e3a2ebca34034866b98ab19ee3f90 -> n8d50442e9d704d7a8e9f0ba2f38e73fc;\n",
+      "n8d50442e9d704d7a8e9f0ba2f38e73fc [label=\"daabc\\ndabaabc\"];\n",
+      "n8d50442e9d704d7a8e9f0ba2f38e73fc -> n942c205bd0994681bf159f01fc42d0f5;\n",
+      "n8d50442e9d704d7a8e9f0ba2f38e73fc -> n8aab1aa30e494cef8895ff177a1d0623;\n",
+      "n942c205bd0994681bf159f01fc42d0f5 [label=\"daab\\ndabaab\"];\n",
+      "n942c205bd0994681bf159f01fc42d0f5 -> na797ca966ed045d5a14888ef06ae64ba;\n",
+      "n942c205bd0994681bf159f01fc42d0f5 -> nd7ea02b3fb6348e49929c458903e1c66;\n",
+      "na797ca966ed045d5a14888ef06ae64ba [label=\"daa\\ndabaa\"];\n",
+      "na797ca966ed045d5a14888ef06ae64ba -> nfc8f27c7ea3b45f69d3e28ff7397c211;\n",
+      "na797ca966ed045d5a14888ef06ae64ba -> nfc96ed80812342958197f351bf4bb6c4;\n",
+      "nfc8f27c7ea3b45f69d3e28ff7397c211 [label=\"da\\ndaba\"];\n",
+      "nfc8f27c7ea3b45f69d3e28ff7397c211 -> n0fba1674138c4ee2a437ec3bfe3c0c34;\n",
+      "nfc8f27c7ea3b45f69d3e28ff7397c211 -> n214435af4c204b2bac186c6bc7fd4b43;\n",
+      "n0fba1674138c4ee2a437ec3bfe3c0c34 [label=\"d\\ndab\"];\n",
+      "n0fba1674138c4ee2a437ec3bfe3c0c34 -> nbbbca27c4d794d3396c58908f36ad8b1;\n",
+      "nbbbca27c4d794d3396c58908f36ad8b1 [label=\"d\\nda\"];\n",
+      "nbbbca27c4d794d3396c58908f36ad8b1 -> n4a39eb3283ba4896bd0ae98e695a5e78;\n",
+      "n4a39eb3283ba4896bd0ae98e695a5e78 [label=\"d\\nd\"];\n",
+      "n4a39eb3283ba4896bd0ae98e695a5e78 -> n0f69ba31cb9341b8a0e01b58e94ecc3e;\n",
+      "n4a39eb3283ba4896bd0ae98e695a5e78 -> n01a1efd1fe0148409aa9ae19a57a1c11;\n",
+      "n0f69ba31cb9341b8a0e01b58e94ecc3e [label=\"-\\n\\nTrue\"];\n",
+      "n01a1efd1fe0148409aa9ae19a57a1c11 [label=\"d\\n\\nFalse\"];\n",
+      "n214435af4c204b2bac186c6bc7fd4b43 [label=\"da\\ndab\"];\n",
+      "n214435af4c204b2bac186c6bc7fd4b43 -> n7f75729c74d944199866bc8242166a15;\n",
+      "n7f75729c74d944199866bc8242166a15 [label=\"da\\nda\"];\n",
+      "n7f75729c74d944199866bc8242166a15 -> nfe2ac3cf290844a686eb20c8a1419632;\n",
+      "n7f75729c74d944199866bc8242166a15 -> n99dabcab19424f76aade00e10b247e28;\n",
+      "nfe2ac3cf290844a686eb20c8a1419632 [label=\"d\\nd\"];\n",
+      "nfe2ac3cf290844a686eb20c8a1419632 -> n4ef4c358f84b44f0816ee6c23bc87c23;\n",
+      "nfe2ac3cf290844a686eb20c8a1419632 -> n0fcf711c28b84e869cd5b1ad29147b79;\n",
+      "n4ef4c358f84b44f0816ee6c23bc87c23 [label=\"-\\n\\nTrue\"];\n",
+      "n0fcf711c28b84e869cd5b1ad29147b79 [label=\"d\\n\\nFalse\"];\n",
+      "n99dabcab19424f76aade00e10b247e28 [label=\"da\\nd\\nFalse\"];\n",
+      "nfc96ed80812342958197f351bf4bb6c4 [label=\"daa\\ndaba\"];\n",
+      "nfc96ed80812342958197f351bf4bb6c4 -> n6f68fb9a9f774752ada474efa377f60e;\n",
+      "nfc96ed80812342958197f351bf4bb6c4 -> ne0abe88f3d764703a75eed757cc316bf;\n",
+      "n6f68fb9a9f774752ada474efa377f60e [label=\"da\\ndab\"];\n",
+      "n6f68fb9a9f774752ada474efa377f60e -> n9c89649fee58407db0ff5d0ba2eb4f2d;\n",
+      "n9c89649fee58407db0ff5d0ba2eb4f2d [label=\"da\\nda\"];\n",
+      "n9c89649fee58407db0ff5d0ba2eb4f2d -> n34738b8c332d4e559f9aa7c7eec42e72;\n",
+      "n9c89649fee58407db0ff5d0ba2eb4f2d -> n446a9bd7fa264edcb2bf289b4fe55f71;\n",
+      "n34738b8c332d4e559f9aa7c7eec42e72 [label=\"d\\nd\"];\n",
+      "n34738b8c332d4e559f9aa7c7eec42e72 -> n73e44dd0c7f248a3bd4aa11de6040c5f;\n",
+      "n34738b8c332d4e559f9aa7c7eec42e72 -> n7af9d67feb864b8ea552f84d64b3e610;\n",
+      "n73e44dd0c7f248a3bd4aa11de6040c5f [label=\"-\\n\\nTrue\"];\n",
+      "n7af9d67feb864b8ea552f84d64b3e610 [label=\"d\\n\\nFalse\"];\n",
+      "n446a9bd7fa264edcb2bf289b4fe55f71 [label=\"da\\nd\\nFalse\"];\n",
+      "ne0abe88f3d764703a75eed757cc316bf [label=\"daa\\ndab\"];\n",
+      "ne0abe88f3d764703a75eed757cc316bf -> n639c085cdfa84e26a754dd4aa56a044e;\n",
+      "n639c085cdfa84e26a754dd4aa56a044e [label=\"daa\\nda\\nFalse\"];\n",
+      "nd7ea02b3fb6348e49929c458903e1c66 [label=\"daab\\ndabaa\"];\n",
+      "nd7ea02b3fb6348e49929c458903e1c66 -> nbfa7d3dbec204c328749c3db14b668ea;\n",
+      "nbfa7d3dbec204c328749c3db14b668ea [label=\"daab\\ndaba\"];\n",
+      "nbfa7d3dbec204c328749c3db14b668ea -> nabacc0aef05041c5998655b5e68b6d94;\n",
+      "nabacc0aef05041c5998655b5e68b6d94 [label=\"daab\\ndab\\nFalse\"];\n",
+      "n8aab1aa30e494cef8895ff177a1d0623 [label=\"daabc\\ndabaab\"];\n",
+      "n8aab1aa30e494cef8895ff177a1d0623 -> nd04c429a65b74db8902b1a2725254549;\n",
+      "nd04c429a65b74db8902b1a2725254549 [label=\"daabc\\ndabaa\"];\n",
+      "nd04c429a65b74db8902b1a2725254549 -> nff340dd0af774bf0818a959dad441b84;\n",
+      "nff340dd0af774bf0818a959dad441b84 [label=\"daabc\\ndaba\\nFalse\"];\n",
+      "n3c49af7ea69340f2a97827a0547f73db [label=\"daabcc\\ndabaabca\"];\n",
+      "n3c49af7ea69340f2a97827a0547f73db -> n5f1bfeaf12e247d9bc9ca4641cb72fb5;\n",
+      "n5f1bfeaf12e247d9bc9ca4641cb72fb5 [label=\"daabcc\\ndabaabc\"];\n",
+      "n5f1bfeaf12e247d9bc9ca4641cb72fb5 -> na504494b1bc842bd800600c18478723a;\n",
+      "n5f1bfeaf12e247d9bc9ca4641cb72fb5 -> n13e17edfcd5a4128996ba5dd2473f244;\n",
+      "na504494b1bc842bd800600c18478723a [label=\"daabc\\ndabaab\"];\n",
+      "na504494b1bc842bd800600c18478723a -> n78a73478b48c43d594e6a04a79c61946;\n",
+      "n78a73478b48c43d594e6a04a79c61946 [label=\"daabc\\ndabaa\"];\n",
+      "n78a73478b48c43d594e6a04a79c61946 -> na3c9f1e44c6546ba9b4c49c48ae842ba;\n",
+      "na3c9f1e44c6546ba9b4c49c48ae842ba [label=\"daabc\\ndaba\\nFalse\"];\n",
+      "n13e17edfcd5a4128996ba5dd2473f244 [label=\"daabcc\\ndabaab\"];\n",
+      "n13e17edfcd5a4128996ba5dd2473f244 -> n5624db7a63c643bcafb2ba6797348bba;\n",
+      "n5624db7a63c643bcafb2ba6797348bba [label=\"daabcc\\ndabaa\\nFalse\"];\n"
+     ]
+    }
+   ],
+   "source": [
+    "root, graph = is_subseq_recursive_dot('daabcc', 'dabaabcacb')\n",
+    "print('\\n'.join(graph))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 70,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "bdabcc dabaabcacb\n",
+      "bdabcc dabaabcac\n",
+      "bdabcc dabaabca\n",
+      "bdabcc dabaabc\n",
+      "bdabcc dabaab\n",
+      "bdabcc dabaa\n",
+      "bdabc dabaab\n",
+      "bdabc dabaa\n",
+      "bdabc daba\n",
+      "bdabc dabaabca\n",
+      "bdabc dabaabc\n",
+      "bdabc dabaab\n",
+      "bdabc dabaa\n",
+      "bdabc daba\n",
+      "bdab dabaab\n",
+      "bdab dabaa\n",
+      "bdab daba\n",
+      "bdab dab\n",
+      "bda dabaa\n",
+      "bda daba\n",
+      "bda dab\n",
+      "bda da\n",
+      "bd dab\n",
+      "bd da\n",
+      "bd d\n",
+      "bd daba\n",
+      "bd dab\n",
+      "bd da\n",
+      "bd d\n"
+     ]
+    },
+    {
+     "data": {
+      "text/plain": [
+       "False"
+      ]
+     },
+     "execution_count": 70,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "is_subseq_recursive('bdabcc', 'dabaabcacb')"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 75,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "bdabcc dabaabcacb nae20c69b2c4d4ea2a239af485ca10f16 [label=\"bdabcc\\ndabaabcacb\"];\n",
+      "bdabcc dabaabcac nac3868f0d46645ca8bf1b02110448236 [label=\"bdabcc\\ndabaabcac\"];\n",
+      "bdabc dabaabca nf5a124f6b457426eaa13f9d58a716fe1 [label=\"bdabc\\ndabaabca\"];\n",
+      "bdabc dabaabc nf82bf143985849a9a14d7272ab8be040 [label=\"bdabc\\ndabaabc\"];\n",
+      "bdab dabaab nf5694edb16d84740ad75d3c3a9dc33f4 [label=\"bdab\\ndabaab\"];\n",
+      "bda dabaa n7734cd7f92a34a3bbb223dac592bd496 [label=\"bda\\ndabaa\"];\n",
+      "bd daba nf51d59c7071c4725a4e961fd017fd0b6 [label=\"bd\\ndaba\"];\n",
+      "bd dab n48a2b0c66af943439d0c9767e9181c50 [label=\"bd\\ndab\"];\n",
+      "bd da nfee98ef394994c0b9664921c73ae7882 [label=\"bd\\nda\"];\n",
+      "bd d n077956a8b783437ba5a65c3fd3380e2f [label=\"bd\\nd\"];\n",
+      "bda daba nd7f11536d8df400d860ac372d1c3e9f8 [label=\"bda\\ndaba\"];\n",
+      "bd dab nb1bf7b9e21a64b30a7a536a9b8649e56 [label=\"bd\\ndab\"];\n",
+      "bd da nb0329d485ca14bfaa79caa33670a8699 [label=\"bd\\nda\"];\n",
+      "bd d ne91eaaeffb1443639b733682718f4092 [label=\"bd\\nd\"];\n",
+      "bda dab n115e972256cc4394a1eba134f114e4ab [label=\"bda\\ndab\"];\n",
+      "bda da na78115224d9f4e37b4045f6c30e4ceb1 [label=\"bda\\nda\"];\n",
+      "bdab dabaa nad799597664c441f9ccedc62f06247bb [label=\"bdab\\ndabaa\"];\n",
+      "bdab daba n55c3278b1aea4bdc92b3d5eb3c09366c [label=\"bdab\\ndaba\"];\n",
+      "bdab dab n5d2503b1d062482b898e4682240dcc78 [label=\"bdab\\ndab\"];\n",
+      "bdabc dabaab nd6bf8394c44b4af79b2a91534ba13317 [label=\"bdabc\\ndabaab\"];\n",
+      "bdabc dabaa ne856116c734a46b1967bddb73c56140f [label=\"bdabc\\ndabaa\"];\n",
+      "bdabc daba ne0497380dcb04eb9b64499dca04e370b [label=\"bdabc\\ndaba\"];\n",
+      "bdabcc dabaabca na1b07d40913a48a89651e06846c27489 [label=\"bdabcc\\ndabaabca\"];\n",
+      "bdabcc dabaabc nf7b9fd837f974551b0795d7492210e52 [label=\"bdabcc\\ndabaabc\"];\n",
+      "bdabc dabaab n753dfbdd86b543cbb9b246e976d31406 [label=\"bdabc\\ndabaab\"];\n",
+      "bdabc dabaa na21720c117704e02910b868caeddb9a9 [label=\"bdabc\\ndabaa\"];\n",
+      "bdabc daba nb1bec31f0ddf4a888f941702a407906f [label=\"bdabc\\ndaba\"];\n",
+      "bdabcc dabaab n556f3f77789b40f0b332b55e20828606 [label=\"bdabcc\\ndabaab\"];\n",
+      "bdabcc dabaa n5b6173aea18d41f8b4a2c5ce99cc4d7a [label=\"bdabcc\\ndabaa\"];\n",
+      "nae20c69b2c4d4ea2a239af485ca10f16 [label=\"bdabcc\\ndabaabcacb\"];\n",
+      "nae20c69b2c4d4ea2a239af485ca10f16 -> nac3868f0d46645ca8bf1b02110448236;\n",
+      "nac3868f0d46645ca8bf1b02110448236 [label=\"bdabcc\\ndabaabcac\"];\n",
+      "nac3868f0d46645ca8bf1b02110448236 -> nf5a124f6b457426eaa13f9d58a716fe1;\n",
+      "nac3868f0d46645ca8bf1b02110448236 -> na1b07d40913a48a89651e06846c27489;\n",
+      "nf5a124f6b457426eaa13f9d58a716fe1 [label=\"bdabc\\ndabaabca\"];\n",
+      "nf5a124f6b457426eaa13f9d58a716fe1 -> nf82bf143985849a9a14d7272ab8be040;\n",
+      "nf82bf143985849a9a14d7272ab8be040 [label=\"bdabc\\ndabaabc\"];\n",
+      "nf82bf143985849a9a14d7272ab8be040 -> nf5694edb16d84740ad75d3c3a9dc33f4;\n",
+      "nf82bf143985849a9a14d7272ab8be040 -> nd6bf8394c44b4af79b2a91534ba13317;\n",
+      "nf5694edb16d84740ad75d3c3a9dc33f4 [label=\"bdab\\ndabaab\"];\n",
+      "nf5694edb16d84740ad75d3c3a9dc33f4 -> n7734cd7f92a34a3bbb223dac592bd496;\n",
+      "nf5694edb16d84740ad75d3c3a9dc33f4 -> nad799597664c441f9ccedc62f06247bb;\n",
+      "n7734cd7f92a34a3bbb223dac592bd496 [label=\"bda\\ndabaa\"];\n",
+      "n7734cd7f92a34a3bbb223dac592bd496 -> nf51d59c7071c4725a4e961fd017fd0b6;\n",
+      "n7734cd7f92a34a3bbb223dac592bd496 -> nd7f11536d8df400d860ac372d1c3e9f8;\n",
+      "nf51d59c7071c4725a4e961fd017fd0b6 [label=\"bd\\ndaba\"];\n",
+      "nf51d59c7071c4725a4e961fd017fd0b6 -> n48a2b0c66af943439d0c9767e9181c50;\n",
+      "n48a2b0c66af943439d0c9767e9181c50 [label=\"bd\\ndab\"];\n",
+      "n48a2b0c66af943439d0c9767e9181c50 -> nfee98ef394994c0b9664921c73ae7882;\n",
+      "nfee98ef394994c0b9664921c73ae7882 [label=\"bd\\nda\"];\n",
+      "nfee98ef394994c0b9664921c73ae7882 -> n077956a8b783437ba5a65c3fd3380e2f;\n",
+      "n077956a8b783437ba5a65c3fd3380e2f [label=\"bd\\nd\\nFalse\"];\n",
+      "nd7f11536d8df400d860ac372d1c3e9f8 [label=\"bda\\ndaba\"];\n",
+      "nd7f11536d8df400d860ac372d1c3e9f8 -> nb1bf7b9e21a64b30a7a536a9b8649e56;\n",
+      "nd7f11536d8df400d860ac372d1c3e9f8 -> n115e972256cc4394a1eba134f114e4ab;\n",
+      "nb1bf7b9e21a64b30a7a536a9b8649e56 [label=\"bd\\ndab\"];\n",
+      "nb1bf7b9e21a64b30a7a536a9b8649e56 -> nb0329d485ca14bfaa79caa33670a8699;\n",
+      "nb0329d485ca14bfaa79caa33670a8699 [label=\"bd\\nda\"];\n",
+      "nb0329d485ca14bfaa79caa33670a8699 -> ne91eaaeffb1443639b733682718f4092;\n",
+      "ne91eaaeffb1443639b733682718f4092 [label=\"bd\\nd\\nFalse\"];\n",
+      "n115e972256cc4394a1eba134f114e4ab [label=\"bda\\ndab\"];\n",
+      "n115e972256cc4394a1eba134f114e4ab -> na78115224d9f4e37b4045f6c30e4ceb1;\n",
+      "na78115224d9f4e37b4045f6c30e4ceb1 [label=\"bda\\nda\\nFalse\"];\n",
+      "nad799597664c441f9ccedc62f06247bb [label=\"bdab\\ndabaa\"];\n",
+      "nad799597664c441f9ccedc62f06247bb -> n55c3278b1aea4bdc92b3d5eb3c09366c;\n",
+      "n55c3278b1aea4bdc92b3d5eb3c09366c [label=\"bdab\\ndaba\"];\n",
+      "n55c3278b1aea4bdc92b3d5eb3c09366c -> n5d2503b1d062482b898e4682240dcc78;\n",
+      "n5d2503b1d062482b898e4682240dcc78 [label=\"bdab\\ndab\\nFalse\"];\n",
+      "nd6bf8394c44b4af79b2a91534ba13317 [label=\"bdabc\\ndabaab\"];\n",
+      "nd6bf8394c44b4af79b2a91534ba13317 -> ne856116c734a46b1967bddb73c56140f;\n",
+      "ne856116c734a46b1967bddb73c56140f [label=\"bdabc\\ndabaa\"];\n",
+      "ne856116c734a46b1967bddb73c56140f -> ne0497380dcb04eb9b64499dca04e370b;\n",
+      "ne0497380dcb04eb9b64499dca04e370b [label=\"bdabc\\ndaba\\nFalse\"];\n",
+      "na1b07d40913a48a89651e06846c27489 [label=\"bdabcc\\ndabaabca\"];\n",
+      "na1b07d40913a48a89651e06846c27489 -> nf7b9fd837f974551b0795d7492210e52;\n",
+      "nf7b9fd837f974551b0795d7492210e52 [label=\"bdabcc\\ndabaabc\"];\n",
+      "nf7b9fd837f974551b0795d7492210e52 -> n753dfbdd86b543cbb9b246e976d31406;\n",
+      "nf7b9fd837f974551b0795d7492210e52 -> n556f3f77789b40f0b332b55e20828606;\n",
+      "n753dfbdd86b543cbb9b246e976d31406 [label=\"bdabc\\ndabaab\"];\n",
+      "n753dfbdd86b543cbb9b246e976d31406 -> na21720c117704e02910b868caeddb9a9;\n",
+      "na21720c117704e02910b868caeddb9a9 [label=\"bdabc\\ndabaa\"];\n",
+      "na21720c117704e02910b868caeddb9a9 -> nb1bec31f0ddf4a888f941702a407906f;\n",
+      "nb1bec31f0ddf4a888f941702a407906f [label=\"bdabc\\ndaba\\nFalse\"];\n",
+      "n556f3f77789b40f0b332b55e20828606 [label=\"bdabcc\\ndabaab\"];\n",
+      "n556f3f77789b40f0b332b55e20828606 -> n5b6173aea18d41f8b4a2c5ce99cc4d7a;\n",
+      "n5b6173aea18d41f8b4a2c5ce99cc4d7a [label=\"bdabcc\\ndabaa\\nFalse\"];\n"
+     ]
+    }
+   ],
+   "source": [
+    "root, graph = is_subseq_recursive_dot('bdabcc', 'dabaabcacb')\n",
+    "print('\\n'.join(graph))"
+   ]
+  },
   {
    "cell_type": "code",
    "execution_count": 30,
@@ -1746,7 +2063,9 @@
   {
    "cell_type": "code",
    "execution_count": 67,
-   "metadata": {},
+   "metadata": {
+    "collapsed": true
+   },
    "outputs": [],
    "source": [
     "import pandas as pd\n",