X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=09-resolving-the-bill%2Fsubsequence.ipynb;h=4484bfb6c6a1fa5fe979607ccc7d6c4c086d1b26;hb=130c870164e49bc33d63a887ecbaee95e4fa9997;hp=c945df8ef101137430c3218aa4e65af10e8bcf0c;hpb=5347be263de306d813f09432169d2254874c9acf;p=ou-summer-of-code-2017.git

diff --git a/09-resolving-the-bill/subsequence.ipynb b/09-resolving-the-bill/subsequence.ipynb
index c945df8..4484bfb 100644
--- a/09-resolving-the-bill/subsequence.ipynb
+++ b/09-resolving-the-bill/subsequence.ipynb
@@ -19,7 +19,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 54,
+   "execution_count": 1,
    "metadata": {
     "collapsed": true
    },
@@ -41,7 +41,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 4,
+   "execution_count": 2,
    "metadata": {
     "scrolled": true
    },
@@ -117,7 +117,7 @@
        " (5, 10): False}"
       ]
      },
-     "execution_count": 4,
+     "execution_count": 2,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -131,7 +131,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 5,
+   "execution_count": 3,
    "metadata": {
     "collapsed": true
    },
@@ -145,7 +145,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 6,
+   "execution_count": 4,
    "metadata": {},
    "outputs": [
     {
@@ -167,7 +167,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 47,
+   "execution_count": 5,
    "metadata": {},
    "outputs": [
     {
@@ -244,7 +244,7 @@
        " (4, 7): (4, 6, 'b', 's2')}"
       ]
      },
-     "execution_count": 47,
+     "execution_count": 5,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -288,7 +288,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 59,
+   "execution_count": 13,
    "metadata": {
     "collapsed": true
    },
@@ -299,7 +299,7 @@
     "    j = max([0] + [k[1] for k in bps])\n",
     "    chars = ''\n",
     "    if (i, j) in bps:\n",
-    "        while i != 0 or j != 0:\n",
+    "        while i != 0 and j != 0:\n",
     "            if bps[i, j][3] == 's1':\n",
     "                chars += bps[i, j][2].upper()\n",
     "            else:\n",
@@ -312,7 +312,7 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 60,
+   "execution_count": 7,
    "metadata": {},
    "outputs": [
     {
@@ -321,7 +321,7 @@
        "'AAAbAbb'"
       ]
      },
-     "execution_count": 60,
+     "execution_count": 7,
      "metadata": {},
      "output_type": "execute_result"
     }
@@ -332,11 +332,90 @@
   },
   {
    "cell_type": "code",
-   "execution_count": 49,
+   "execution_count": 28,
    "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "aa 0 0 ! ! True\n",
+      "aa 0 1 ! ! True\n",
+      "aa 0 2 ! ! True\n",
+      "aa 0 3 ! ! True\n",
+      "aa 0 4 ! ! True\n",
+      "aa 0 5 ! ! True\n",
+      "aa 0 6 ! ! True\n",
+      "aa 0 7 ! ! True\n",
+      "aa 0 8 ! ! True\n",
+      "aa 0 9 ! ! True\n",
+      "aa 0 10 ! ! True\n",
+      "xx 1 1 a d False\n",
+      "s1 1 2 a a True\n",
+      "s2 1 3 a b True\n",
+      "s2 1 4 a a True\n",
+      "s1 1 4 a a True\n",
+      "s2 1 5 a a True\n",
+      "s1 1 5 a a True\n",
+      "s2 1 6 a b True\n",
+      "s2 1 7 a c True\n",
+      "s2 1 8 a a True\n",
+      "s1 1 8 a a True\n",
+      "s2 1 9 a c True\n",
+      "s2 1 10 a b True\n",
+      "xx 2 2 a a False\n",
+      "xx 2 3 a b False\n",
+      "s1 2 4 a a True\n",
+      "s2 2 5 a a True\n",
+      "s1 2 5 a a True\n",
+      "s2 2 6 a b True\n",
+      "s2 2 7 a c True\n",
+      "s2 2 8 a a True\n",
+      "s1 2 8 a a True\n",
+      "s2 2 9 a c True\n",
+      "s2 2 10 a b True\n",
+      "xx 3 3 a b False\n",
+      "xx 3 4 a a False\n",
+      "s1 3 5 a a True\n",
+      "s2 3 6 a b True\n",
+      "s2 3 7 a c True\n",
+      "s2 3 8 a a True\n",
+      "s1 3 8 a a True\n",
+      "s2 3 9 a c True\n",
+      "s2 3 10 a b True\n",
+      "xx 4 4 a a False\n",
+      "xx 4 5 a a False\n",
+      "xx 4 6 a b False\n",
+      "xx 4 7 a c False\n",
+      "s1 4 8 a a True\n",
+      "s2 4 9 a c True\n",
+      "s2 4 10 a b True\n"
+     ]
+    },
+    {
+     "data": {
+      "text/plain": [
+       "True"
+      ]
+     },
+     "execution_count": 28,
+     "metadata": {},
+     "output_type": "execute_result"
+    }
+   ],
+   "source": [
+    "is_subseq(s1, s2t, debug=True)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 27,
+   "metadata": {
+    "collapsed": true
+   },
    "outputs": [],
    "source": [
-    "def is_subseq(seq1, seq2, return_backpointers=False, debug=False):\n",
+    "def is_subseq(seq1, seq2, return_backpointers=False, return_table=False, debug=False):\n",
     "    \"\"\"Return true if seq1 is a subsequence of seq2.\n",
     "    If return_backpointers, also return the set of backpointers to\n",
     "    reconstruct the subsequence\"\"\"\n",
@@ -369,15 +448,38 @@
     "                if not dp_table[i, j]:\n",
     "                    if debug: print('xx', i, j, seq1[i-1], seq2[j-1], dp_table[i, j]) \n",
     "   \n",
-    "    if return_backpointers:\n",
-    "        return dp_table[len(seq1), len(seq2)], backpointers\n",
+    "#     if return_backpointers:\n",
+    "#         return dp_table[len(seq1), len(seq2)], backpointers\n",
+    "#     else:\n",
+    "#         return dp_table[len(seq1), len(seq2)]\n",
+    "    \n",
+    "    if return_backpointers or return_table:\n",
+    "        retval = [dp_table[len(seq1), len(seq2)]]\n",
+    "        if return_backpointers:\n",
+    "            retval += [backpointers]\n",
+    "        if return_table:\n",
+    "            retval += [dp_table]\n",
+    "        return tuple(retval)\n",
     "    else:\n",
     "        return dp_table[len(seq1), len(seq2)]"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 39,
+   "execution_count": 37,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [],
+   "source": [
+    "def show_annotated_table(table, bps):\n",
+    "    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",
+    "        for i in sorted(set([k[0] for k in table])))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 29,
    "metadata": {},
    "outputs": [
     {
@@ -386,155 +488,176 @@
        "True"
       ]
      },
-     "execution_count": 39,
+     "execution_count": 29,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "is_subseq(s1, s2t)"
+    "tf, bps, tb = is_subseq(s1, s2t, return_backpointers=True, return_table=True)\n",
+    "tf"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 55,
+   "execution_count": 20,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "True"
+       "'AbAAbcAcb'"
       ]
      },
-     "execution_count": 55,
+     "execution_count": 20,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "tf, bps = is_subseq(s1, s2t, return_backpointers=True)\n",
-    "tf"
+    "show_backtrace(bps)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 32,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "T T T T T T T T T T T\n",
+      "F F T T T T T T T T T\n",
+      "F F F F T T T T T T T\n",
+      "F F F F F T T T T T T\n",
+      "F F F F F F F F T T T\n"
+     ]
+    }
+   ],
+   "source": [
+    "print(show_table(tb))"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 38,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      ". . . . . . . . . . .\n",
+      ". . a b a a b c a c b\n",
+      ". . . . a a b c a c b\n",
+      ". . . . . a b c a c b\n",
+      ". . . . . . . . a c b\n"
+     ]
+    }
+   ],
+   "source": [
+    "print(show_annotated_table(tb, bps))"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 56,
+   "execution_count": 21,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "'AABCaCb'"
+       "False"
       ]
      },
-     "execution_count": 56,
+     "execution_count": 21,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "show_backtrace(bps)"
+    "len(show_backtrace(bps)) == len(s2t)"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 42,
+   "execution_count": 24,
    "metadata": {},
    "outputs": [
     {
      "data": {
       "text/plain": [
-       "False"
+       "('aaaa', 'dabaabcacb')"
       ]
      },
-     "execution_count": 42,
+     "execution_count": 24,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
    "source": [
-    "is_subseq(s1, s2f)"
+    "s1, s2t"
    ]
   },
   {
    "cell_type": "code",
-   "execution_count": 43,
+   "execution_count": 23,
    "metadata": {},
    "outputs": [
-    {
-     "name": "stdout",
-     "output_type": "stream",
-     "text": [
-      "aa 0 0 ! ! True\n",
-      "aa 0 1 ! ! True\n",
-      "aa 0 2 ! ! True\n",
-      "aa 0 3 ! ! True\n",
-      "aa 0 4 ! ! True\n",
-      "aa 0 5 ! ! True\n",
-      "aa 0 6 ! ! True\n",
-      "aa 0 7 ! ! True\n",
-      "s1 1 1 a a True\n",
-      "s2 1 2 a a True\n",
-      "s1 1 2 a a True\n",
-      "s2 1 3 a a True\n",
-      "s1 1 3 a a True\n",
-      "s2 1 4 a b True\n",
-      "s2 1 5 a a True\n",
-      "s1 1 5 a a True\n",
-      "s2 1 6 a b True\n",
-      "s2 1 7 a b True\n",
-      "s1 2 2 a a True\n",
-      "s2 2 3 a a True\n",
-      "s1 2 3 a a True\n",
-      "s2 2 4 a b True\n",
-      "s2 2 5 a a True\n",
-      "s1 2 5 a a True\n",
-      "s2 2 6 a b True\n",
-      "s2 2 7 a b True\n",
-      "s1 3 3 a a True\n",
-      "s2 3 4 a b True\n",
-      "s2 3 5 a a True\n",
-      "s1 3 5 a a True\n",
-      "s2 3 6 a b True\n",
-      "s2 3 7 a b True\n",
-      "xx 4 4 a b False\n",
-      "s1 4 5 a a True\n",
-      "s2 4 6 a b True\n",
-      "s2 4 7 a b True\n"
-     ]
-    },
     {
      "data": {
       "text/plain": [
-       "(True,\n",
-       " {(1, 1): (0, 1, 'a', 's1'),\n",
-       "  (1, 2): (0, 2, 'a', 's1'),\n",
-       "  (1, 3): (0, 3, 'a', 's1'),\n",
-       "  (1, 4): (1, 3, 'b', 's2'),\n",
-       "  (1, 5): (0, 5, 'a', 's1'),\n",
-       "  (1, 6): (1, 5, 'b', 's2'),\n",
-       "  (1, 7): (1, 6, 'b', 's2'),\n",
-       "  (2, 2): (1, 2, 'a', 's1'),\n",
-       "  (2, 3): (1, 3, 'a', 's1'),\n",
-       "  (2, 4): (2, 3, 'b', 's2'),\n",
-       "  (2, 5): (1, 5, 'a', 's1'),\n",
-       "  (2, 6): (2, 5, 'b', 's2'),\n",
-       "  (2, 7): (2, 6, 'b', 's2'),\n",
-       "  (3, 3): (2, 3, 'a', 's1'),\n",
-       "  (3, 4): (3, 3, 'b', 's2'),\n",
-       "  (3, 5): (2, 5, 'a', 's1'),\n",
-       "  (3, 6): (3, 5, 'b', 's2'),\n",
-       "  (3, 7): (3, 6, 'b', 's2'),\n",
-       "  (4, 5): (3, 5, 'a', 's1'),\n",
-       "  (4, 6): (4, 5, 'b', 's2'),\n",
-       "  (4, 7): (4, 6, 'b', 's2')})"
+       "{(1, 2): (0, 1, 'a', 's1'),\n",
+       " (1, 3): (1, 2, 'b', 's2'),\n",
+       " (1, 4): (0, 3, 'a', 's1'),\n",
+       " (1, 5): (0, 4, 'a', 's1'),\n",
+       " (1, 6): (1, 5, 'b', 's2'),\n",
+       " (1, 7): (1, 6, 'c', 's2'),\n",
+       " (1, 8): (0, 7, 'a', 's1'),\n",
+       " (1, 9): (1, 8, 'c', 's2'),\n",
+       " (1, 10): (1, 9, 'b', 's2'),\n",
+       " (2, 4): (1, 3, 'a', 's1'),\n",
+       " (2, 5): (1, 4, 'a', 's1'),\n",
+       " (2, 6): (2, 5, 'b', 's2'),\n",
+       " (2, 7): (2, 6, 'c', 's2'),\n",
+       " (2, 8): (1, 7, 'a', 's1'),\n",
+       " (2, 9): (2, 8, 'c', 's2'),\n",
+       " (2, 10): (2, 9, 'b', 's2'),\n",
+       " (3, 5): (2, 4, 'a', 's1'),\n",
+       " (3, 6): (3, 5, 'b', 's2'),\n",
+       " (3, 7): (3, 6, 'c', 's2'),\n",
+       " (3, 8): (2, 7, 'a', 's1'),\n",
+       " (3, 9): (3, 8, 'c', 's2'),\n",
+       " (3, 10): (3, 9, 'b', 's2'),\n",
+       " (4, 8): (3, 7, 'a', 's1'),\n",
+       " (4, 9): (4, 8, 'c', 's2'),\n",
+       " (4, 10): (4, 9, 'b', 's2')}"
       ]
      },
-     "execution_count": 43,
+     "execution_count": 23,
      "metadata": {},
      "output_type": "execute_result"
     }
    ],
+   "source": [
+    "bps"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "is_subseq(s1, s2f)"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
    "source": [
     "is_subseq('aaaa', 'aaababb', return_backpointers=True, debug=True)"
    ]