X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=09-resolving-the-bill%2Fresolving-the-bill-solution.ipynb;h=dc846ae48a37dd38c6d0f608bde46ee34550e1d0;hb=7feed95175973490721236795cc7895e252965e2;hp=5b04383b8c8abe67310371a40c4a4aef39183a4e;hpb=3ee4ba25339ed825d790be0e40e5c77dfdd5cbd4;p=ou-summer-of-code-2017.git
diff --git a/09-resolving-the-bill/resolving-the-bill-solution.ipynb b/09-resolving-the-bill/resolving-the-bill-solution.ipynb
index 5b04383..dc846ae 100644
--- a/09-resolving-the-bill/resolving-the-bill-solution.ipynb
+++ b/09-resolving-the-bill/resolving-the-bill-solution.ipynb
@@ -24,7 +24,7 @@
"6: aacccabaddcdaddaabdc\n",
"```\n",
"\n",
- "You know what you spent, so you've helpfully added your bill as the first line of the file, at index 0. \n",
+ "You know what you spent, so you've helpfully included your bill as the first line of the file, at index 0. \n",
"\n",
"You can find your bill in the mixed-up line at index 4, like this:\n",
"\n",
@@ -78,7 +78,19 @@
},
{
"cell_type": "code",
- "execution_count": 26,
+ "execution_count": 2,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "import sys\n",
+ "sys.setrecursionlimit(10**6)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
"metadata": {},
"outputs": [
{
@@ -87,7 +99,7 @@
"148"
]
},
- "execution_count": 26,
+ "execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
@@ -100,7 +112,7 @@
},
{
"cell_type": "code",
- "execution_count": 29,
+ "execution_count": 4,
"metadata": {
"collapsed": true
},
@@ -114,7 +126,7 @@
},
{
"cell_type": "code",
- "execution_count": 30,
+ "execution_count": 5,
"metadata": {
"collapsed": true
},
@@ -134,7 +146,7 @@
},
{
"cell_type": "code",
- "execution_count": 35,
+ "execution_count": 6,
"metadata": {
"collapsed": true
},
@@ -158,7 +170,7 @@
},
{
"cell_type": "code",
- "execution_count": 53,
+ "execution_count": 7,
"metadata": {
"collapsed": true
},
@@ -178,7 +190,24 @@
},
{
"cell_type": "code",
- "execution_count": 66,
+ "execution_count": 8,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_subseq_greedy(s1, s2):\n",
+ " i = j = 0\n",
+ " while i < len(s1) and j < len(s2):\n",
+ " if s1[i] == s2[j]:\n",
+ " i += 1\n",
+ " j += 1\n",
+ " return i == len(s1)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
"metadata": {
"collapsed": true
},
@@ -233,7 +262,58 @@
},
{
"cell_type": "code",
- "execution_count": 54,
+ "execution_count": 10,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_subseq_rows(seq1, seq2, return_backpointers=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",
+ " \n",
+ " # dp_table[i, j] is True if first i characters of seq1 can\n",
+ " # be found in the first j characters of seq2\n",
+ " \n",
+ " backpointers = {}\n",
+ " \n",
+ " for i in range(len(seq1)+1):\n",
+ " row = [False] * (len(seq2)+1)\n",
+ " for j in range(i, len(seq2)+1):\n",
+ " if i == 0:\n",
+ " row[j] = True\n",
+ " if debug: print('aa', i, j, '!', '!', row[j])\n",
+ " elif j == 0:\n",
+ " row[j] = False\n",
+ " if debug: print('zz', i, j, '!', '!', row[j])\n",
+ " else:\n",
+ " # extend by character from s2\n",
+ " if row[j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('s2', i, j, seq1[i-1], seq2[j-1], row[j]) \n",
+ " # extend by character from s1\n",
+ " if previous_row[j-1] and seq1[i-1] == seq2[j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i-1, j-1, seq1[i-1], 'seq1') \n",
+ " if debug: print('s1', i, j, seq1[i-1], seq2[j-1], row[j])\n",
+ " if not row[j]:\n",
+ " if debug: print('xx', i, j, seq1[i-1], seq2[j-1], row[j])\n",
+ " previous_row = row\n",
+ " \n",
+ " if return_backpointers:\n",
+ " retval = [row[-1]]\n",
+ " if return_backpointers:\n",
+ " retval += [backpointers]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return row[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
"metadata": {},
"outputs": [
{
@@ -242,7 +322,7 @@
"22"
]
},
- "execution_count": 54,
+ "execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
@@ -255,11 +335,81 @@
},
{
"cell_type": "code",
- "execution_count": null,
- "metadata": {
- "collapsed": true
- },
- "outputs": [],
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "22"
+ ]
+ },
+ "execution_count": 12,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(1 for s in bills\n",
+ " if s != 0\n",
+ " if is_subseq_rows(bills[0], bills[s]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "22"
+ ]
+ },
+ "execution_count": 13,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(1 for s in bills\n",
+ " if s != 0\n",
+ " if is_subseq_greedy(bills[0], bills[s]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 30,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "100 loops, best of 3: 13.1 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "sum(1 for s in bills\n",
+ " if s != 0\n",
+ " if is_subseq_greedy(bills[0], bills[s]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 7.88 s per loop\n"
+ ]
+ }
+ ],
"source": [
"%%timeit\n",
"sum(1 for s in bills\n",
@@ -269,7 +419,7 @@
},
{
"cell_type": "code",
- "execution_count": 36,
+ "execution_count": 15,
"metadata": {
"scrolled": true
},
@@ -301,7 +451,7 @@
" 146]"
]
},
- "execution_count": 36,
+ "execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
@@ -314,15 +464,15 @@
},
{
"cell_type": "code",
- "execution_count": 65,
+ "execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "CPU times: user 168 ms, sys: 0 ns, total: 168 ms\n",
- "Wall time: 166 ms\n"
+ "CPU times: user 148 ms, sys: 4 ms, total: 152 ms\n",
+ "Wall time: 150 ms\n"
]
},
{
@@ -331,7 +481,7 @@
"(True, False)"
]
},
- "execution_count": 65,
+ "execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
@@ -342,7 +492,7 @@
},
{
"cell_type": "code",
- "execution_count": 73,
+ "execution_count": 17,
"metadata": {
"collapsed": true
},
@@ -353,7 +503,7 @@
},
{
"cell_type": "code",
- "execution_count": 39,
+ "execution_count": 18,
"metadata": {},
"outputs": [
{
@@ -580,7 +730,7 @@
},
{
"cell_type": "code",
- "execution_count": 47,
+ "execution_count": 31,
"metadata": {
"collapsed": true
},
@@ -591,20 +741,24 @@
" return s2 == s3\n",
" elif not s2:\n",
" return s1 == s3\n",
+ " elif len(s1) + len(s2) != len(s3):\n",
+ " return False\n",
" else:\n",
- " if s1[-1] == s2[-1] and s1[-1] == s3[-1]:\n",
- " return is_interleave_recursive(s1[:-1], s2, s3[:-1]) or is_interleave(s1, s2[:-1], s3[:-1])\n",
+ " if s1[-1] == s3[-1] and s2[-1] == s3[-1]:\n",
+ " return (is_interleave_recursive(s1[:-1], s2, s3[:-1]) \n",
+ " or \n",
+ " is_interleave_recursive(s1, s2[:-1], s3[:-1]) )\n",
" elif s1[-1] == s3[-1]:\n",
" return is_interleave_recursive(s1[:-1], s2, s3[:-1])\n",
" elif s2[-1] == s3[-1]:\n",
- " return is_interleave(s1, s2[:-1], s3[:-1])\n",
+ " return is_interleave_recursive(s1, s2[:-1], s3[:-1])\n",
" else:\n",
" return False"
]
},
{
"cell_type": "code",
- "execution_count": 40,
+ "execution_count": 20,
"metadata": {
"collapsed": true
},
@@ -680,7 +834,160 @@
},
{
"cell_type": "code",
- "execution_count": 41,
+ "execution_count": 21,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_interleave_rows(seq1, seq2, seq3, return_backpointers=False, debug=False):\n",
+ " \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n",
+ " If return_backpointers, also return the set of backpointers to\n",
+ " reconstruct the interleaving.\n",
+ " \n",
+ " This version doesn't build the whole table, just keeps the current and previous rows\"\"\"\n",
+ " \n",
+ " # dp_table[i, j] is True if first i+j characters of seq is made up of \n",
+ " # an interleaving of the first i characters of seq1 and the \n",
+ " # first j characters of seq2\n",
+ " \n",
+ " if len(seq1) + len(seq2) != len(seq3):\n",
+ " if return_backpointers:\n",
+ " retval = [False]\n",
+ " if return_backpointers:\n",
+ " retval += [{}]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return False\n",
+ " \n",
+ "\n",
+ " backpointers = {}\n",
+ "\n",
+ " for i in range(len(seq1)+1):\n",
+ " row = [False] * (len(seq2)+1)\n",
+ " for j in range(len(seq2)+1):\n",
+ " if i == 0 and j == 0:\n",
+ " row[j] = True\n",
+ " if debug: print('xxxx', i, j, '!', '!', '!', row[j])\n",
+ " elif i == 0:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], row[j])\n",
+ " elif j == 0:\n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n",
+ " if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j]) \n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1') \n",
+ " if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " if not row[j]:\n",
+ " if debug: print('xxxx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " previous_row = row\n",
+ "\n",
+ " if return_backpointers:\n",
+ " retval = [row[-1]]\n",
+ " if return_backpointers:\n",
+ " retval += [backpointers]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return row[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_interleave_rows2(seq1, seq2, seq3, return_backpointers=False, debug=False):\n",
+ " \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n",
+ " If return_backpointers, also return the set of backpointers to\n",
+ " reconstruct the interleaving.\n",
+ " \n",
+ " This version doesn't keep the whole table, just the current and previous\n",
+ " rows. It also builds the current row as it goes along, rather than\n",
+ " building the whole row and updating elements as required.\"\"\"\n",
+ " \n",
+ " # dp_table[i, j] is True if first i+j characters of seq is made up of \n",
+ " # an interleaving of the first i characters of seq1 and the \n",
+ " # first j characters of seq2\n",
+ " \n",
+ " if len(seq1) + len(seq2) != len(seq3):\n",
+ " if return_backpointers:\n",
+ " retval = [False]\n",
+ " if return_backpointers:\n",
+ " retval += [{}]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return False\n",
+ " \n",
+ "\n",
+ " backpointers = {}\n",
+ "\n",
+ " for i in range(len(seq1)+1):\n",
+ " row = []\n",
+ " for j in range(len(seq2)+1):\n",
+ " if i == 0 and j == 0:\n",
+ " row += [True]\n",
+ " if debug: print('xxxx', i, j, '!', '!', '!', row[j])\n",
+ " elif i == 0:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], row[j])\n",
+ " elif j == 0:\n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j]) \n",
+ " # extend by character from seq1\n",
+ " elif previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1') \n",
+ " if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('xxxx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " previous_row = row\n",
+ "\n",
+ " if return_backpointers:\n",
+ " retval = [row[-1]]\n",
+ " if return_backpointers:\n",
+ " retval += [backpointers]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return row[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
"metadata": {
"collapsed": true
},
@@ -704,7 +1011,7 @@
},
{
"cell_type": "code",
- "execution_count": 44,
+ "execution_count": 24,
"metadata": {},
"outputs": [
{
@@ -713,7 +1020,7 @@
"[30]"
]
},
- "execution_count": 44,
+ "execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
@@ -725,7 +1032,71 @@
},
{
"cell_type": "code",
- "execution_count": 45,
+ "execution_count": 25,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[30]"
+ ]
+ },
+ "execution_count": 25,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[s for s in bills\n",
+ " if is_interleave_rows(bills[0], bills[1], bills[s])]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 26,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[30]"
+ ]
+ },
+ "execution_count": 26,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[s for s in bills\n",
+ " if is_interleave_rows2(bills[0], bills[1], bills[s])]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 27,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "[30]"
+ ]
+ },
+ "execution_count": 27,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "[s for s in bills\n",
+ " if is_subseq(bills[0], bills[s])\n",
+ " if is_subseq(bills[1], bills[s])]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 28,
"metadata": {},
"outputs": [
{
@@ -942,7 +1313,7 @@
"True"
]
},
- "execution_count": 45,
+ "execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
@@ -956,7 +1327,7 @@
},
{
"cell_type": "code",
- "execution_count": 48,
+ "execution_count": 32,
"metadata": {},
"outputs": [
{
@@ -965,7 +1336,7 @@
"[30]"
]
},
- "execution_count": 48,
+ "execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
@@ -977,14 +1348,14 @@
},
{
"cell_type": "code",
- "execution_count": 70,
+ "execution_count": 33,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 2.68 s per loop\n"
+ "1 loop, best of 3: 3.12 s per loop\n"
]
}
],
@@ -996,14 +1367,52 @@
},
{
"cell_type": "code",
- "execution_count": 71,
+ "execution_count": 34,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
- "1 loop, best of 3: 660 ms per loop\n"
+ "1 loop, best of 3: 971 ms per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "[s for s in bills\n",
+ " if is_interleave_rows(bills[0], bills[1], bills[s])]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 35,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1 loop, best of 3: 1.56 s per loop\n"
+ ]
+ }
+ ],
+ "source": [
+ "%%timeit\n",
+ "[s for s in bills\n",
+ " if is_interleave_rows2(bills[0], bills[1], bills[s])]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 36,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "1000 loops, best of 3: 510 µs per loop\n"
]
}
],
@@ -1013,6 +1422,284 @@
" if is_interleave_recursive(bills[0], bills[1], bills[s])]"
]
},
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "collapsed": true
+ },
+ "source": [
+ "# Sense solution\n",
+ "Took \n",
+ "* 25.8 seconds to load file\n",
+ "* 15203.9 seconds to find subsequences (4.22 hours; 4 hours, 13 minutes, 23.9 seconds)\n",
+ "* 40083.8 seconds to check all interleavings (11.13 hours; 11 hours, 8 minutes, 3.8 seconds)\n",
+ "\n",
+ "Total of 15 hours 21 minutes 53.5 seconds."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(4.223305555555555, 4, 13, 23.899999999999636)"
+ ]
+ },
+ "execution_count": 37,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rtime = 15203.9\n",
+ "(rtime / 3600,\n",
+ " int(rtime / 3600), \n",
+ " int(rtime / 60 - int(rtime / 3600) * 60), \n",
+ " rtime - int(rtime / 60) * 60\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(11.13438888888889, 11, 8, 3.8000000000029104)"
+ ]
+ },
+ "execution_count": 38,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rtime = 40083.8\n",
+ "(rtime / 3600,\n",
+ " int(rtime / 3600), \n",
+ " int(rtime / 60 - int(rtime / 3600) * 60), \n",
+ " rtime - int(rtime / 60) * 60\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "(15.36486111111111, 15, 21, 53.5)"
+ ]
+ },
+ "execution_count": 39,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "rtime = 25.8 + 15203.9 +40083.8\n",
+ "(rtime / 3600,\n",
+ " int(rtime / 3600), \n",
+ " int(rtime / 60 - int(rtime / 3600) * 60), \n",
+ " rtime - int(rtime / 60) * 60\n",
+ ")"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {
+ "collapsed": true
+ },
+ "source": [
+ "# Explanations"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "starget = 'acba'\n",
+ "swrong = 'cdabcaca'\n",
+ "sinterleave = 'abcacbba'\n",
+ "ssubseq = 'aaccabab'"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 41,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_subseq_md_table(short, long, table):\n",
+ " header = '| |' + '|'.join('{}
{}'.format('
'.join(str(long[:i])), i) for i in range(len(long) + 1)) + '|'\n",
+ " separator = '|:---:' * (len(long) + 2) + '|'\n",
+ " rows = []\n",
+ " columns = sorted(set(k[1] for k in table))\n",
+ " for r in range(len(short) + 1):\n",
+ " row = '|{}
{}|'.format(r, short[:r])\n",
+ " row += '|'.join('T' if table[r, c] else '.' for c in columns)\n",
+ " row += '|'\n",
+ " rows += [row]\n",
+ " return '\\n'.join([header] + [separator] + rows)\n",
+ "# return '\\n'.join(\n",
+ "# ' '.join('T' 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": 42,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ ". . . . . . . . .\n",
+ ". a a c c a b a b\n",
+ ". . . c c a b a b\n",
+ ". . . . . . b a b\n",
+ ". . . . . . . a b\n",
+ "AcCaBAb\n"
+ ]
+ }
+ ],
+ "source": [
+ "v, bp, t = is_subseq(starget, ssubseq, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace_s(bp))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 43,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "T T T T T T T T T\n",
+ ". T T T T T T T T\n",
+ ". . . T T T T T T\n",
+ ". . . . . . T T T\n",
+ ". . . . . . . T T\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(show_table(t))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "| |
0|a
1|a
a
2|a
a
c
3|a
a
c
c
4|a
a
c
c
a
5|a
a
c
c
a
b
6|a
a
c
c
a
b
a
7|a
a
c
c
a
b
a
b
8|\n",
+ "|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n",
+ "|0
|T|T|T|T|T|T|T|T|T|\n",
+ "|1
a|.|T|T|T|T|T|T|T|T|\n",
+ "|2
ac|.|.|.|T|T|T|T|T|T|\n",
+ "|3
acb|.|.|.|.|.|.|T|T|T|\n",
+ "|4
acba|.|.|.|.|.|.|.|T|T|\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(show_subseq_md_table(starget, ssubseq, t))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "| |
0|a
1|a
a
2|a
a
c
3|a
a
c
c
4|a
a
c
c
a
5|a
a
c
c
a
b
6|a
a
c
c
a
b
a
7|a
a
c
c
a
b
a
b
8|\n",
+ "|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n",
+ "|0
|T|T|T|T|T|T|T|T|T|\n",
+ "|1
a|.|T|T|T|T|T|T|T|T|\n",
+ "|2
ac|.|.|.|T|T|T|T|T|T|\n",
+ "|3
acb|.|.|.|.|.|.|T|T|T|\n",
+ "|4
acba|.|.|.|.|.|.|.|T|T|"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ ". . . . . . . . .\n",
+ ". . . a b c a c a\n",
+ ". . . . . c a c a\n",
+ ". . . . . . . . .\n",
+ ". . . . . . . . .\n",
+ "ACa\n"
+ ]
+ }
+ ],
+ "source": [
+ "v, bp, t = is_subseq(starget, swrong, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace_s(bp))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 46,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "| |
0|c
1|c
d
2|c
d
a
3|c
d
a
b
4|c
d
a
b
c
5|c
d
a
b
c
a
6|c
d
a
b
c
a
c
7|c
d
a
b
c
a
c
a
8|\n",
+ "|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n",
+ "|0
|T|T|T|T|T|T|T|T|T|\n",
+ "|1
a|.|.|.|T|T|T|T|T|T|\n",
+ "|2
ac|.|.|.|.|.|T|T|T|T|\n",
+ "|3
acb|.|.|.|.|.|.|.|.|.|\n",
+ "|4
acba|.|.|.|.|.|.|.|.|.|\n"
+ ]
+ }
+ ],
+ "source": [
+ "print(show_subseq_md_table(starget, swrong, t))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "| |
0|c
1|c
d
2|c
d
a
3|c
d
a
b
4|c
d
a
b
c
5|c
d
a
b
c
a
6|c
d
a
b
c
a
c
7|c
d
a
b
c
a
c
a
8|\n",
+ "|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n",
+ "|0
|T|T|T|T|T|T|T|T|T|\n",
+ "|1
a|.|.|.|T|T|T|T|T|T|\n",
+ "|2
ac|.|.|.|.|.|T|T|T|T|\n",
+ "|3
acb|.|.|.|.|.|.|.|.|.|\n",
+ "|4
acba|.|.|.|.|.|.|.|.|.|"
+ ]
+ },
{
"cell_type": "code",
"execution_count": null,