+ "print(show_table_md(et, e1, e2, e3))"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "| |<br />0|a<br />1|a<br />b<br />2|a<br />b<br />a<br />3|\n",
+ "|:---:|:---:|:---:|:---:|:---:|\n",
+ "|**0<br />**|<br />T|a<br />T|ab<br />T|aba<br />T|\n",
+ "|**1<br />a**|a<br />T|ab<br />.|aba<br />T|abac<br />.|\n",
+ "|**2<br />ac**|ab<br />.|aba<br />.|abac<br />T|abaca<br />T|\n",
+ "|**3<br />acb**|aba<br />.|abac<br />.|abaca<br />.|abacab<br />T|"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 42,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "ndf96f65c85de45ba814c3aebe4afed65 [label=\"aabcc\\ndbbca\\naadbbcbcac\"];\n",
+ "ndf96f65c85de45ba814c3aebe4afed65 -> n0e6e480c9d664ba2af7e041445763b66;\n",
+ "n0e6e480c9d664ba2af7e041445763b66 [label=\"aabc\\ndbbca\\naadbbcbca\"];\n",
+ "n0e6e480c9d664ba2af7e041445763b66 -> nc7f25932eaf1431cb98430f8b1644221;\n",
+ "nc7f25932eaf1431cb98430f8b1644221 [label=\"aabc\\ndbbc\\naadbbcbc\"];\n",
+ "nc7f25932eaf1431cb98430f8b1644221 -> ncd2942f9e99443619c6ce1d72a10da75;\n",
+ "nc7f25932eaf1431cb98430f8b1644221 -> n0e76b3b46aba4a8abdbd569a0762170a;\n",
+ "ncd2942f9e99443619c6ce1d72a10da75 [label=\"aab\\ndbbc\\naadbbcb\"];\n",
+ "ncd2942f9e99443619c6ce1d72a10da75 -> n4762ffa7e0c6426792438c6f84c9d2f9;\n",
+ "n4762ffa7e0c6426792438c6f84c9d2f9 [label=\"aa\\ndbbc\\naadbbc\"];\n",
+ "n4762ffa7e0c6426792438c6f84c9d2f9 -> n9434633af1674b45ae72a987932bcacc;\n",
+ "n9434633af1674b45ae72a987932bcacc [label=\"aa\\ndbb\\naadbb\"];\n",
+ "n9434633af1674b45ae72a987932bcacc -> n72dd6ed85e8d43d39b1c6b240f672815;\n",
+ "n72dd6ed85e8d43d39b1c6b240f672815 [label=\"aa\\ndb\\naadb\"];\n",
+ "n72dd6ed85e8d43d39b1c6b240f672815 -> nf904e4ea330a48028602500e910001ba;\n",
+ "nf904e4ea330a48028602500e910001ba [label=\"aa\\nd\\naad\"];\n",
+ "nf904e4ea330a48028602500e910001ba -> nc2246b72d95748f5984f7a9a922afafa;\n",
+ "nc2246b72d95748f5984f7a9a922afafa [label=\"aa\\n-\\naa\\nTrue\"];\n",
+ "n0e76b3b46aba4a8abdbd569a0762170a [label=\"aabc\\ndbb\\naadbbcb\"];\n",
+ "n0e76b3b46aba4a8abdbd569a0762170a -> nde239312af534c47988db27094dc5e3b;\n",
+ "nde239312af534c47988db27094dc5e3b [label=\"aabc\\ndb\\naadbbc\"];\n",
+ "nde239312af534c47988db27094dc5e3b -> n0571e43544db4baea762dd9382a90eab;\n",
+ "n0571e43544db4baea762dd9382a90eab [label=\"aab\\ndb\\naadbb\"];\n",
+ "n0571e43544db4baea762dd9382a90eab -> nd24f1944051440d6b94710a3b971c134;\n",
+ "n0571e43544db4baea762dd9382a90eab -> n671eff7dd1f945a28e7bcd0647d7d40d;\n",
+ "nd24f1944051440d6b94710a3b971c134 [label=\"aa\\ndb\\naadb\"];\n",
+ "nd24f1944051440d6b94710a3b971c134 -> n26480b1bcee847adaeb205f2e844a4e5;\n",
+ "n26480b1bcee847adaeb205f2e844a4e5 [label=\"aa\\nd\\naad\"];\n",
+ "n26480b1bcee847adaeb205f2e844a4e5 -> n162a36ef08174bafa51dbf89a58965df;\n",
+ "n162a36ef08174bafa51dbf89a58965df [label=\"aa\\n-\\naa\\nTrue\"];\n",
+ "n671eff7dd1f945a28e7bcd0647d7d40d [label=\"aab\\nd\\naadb\"];\n",
+ "n671eff7dd1f945a28e7bcd0647d7d40d -> n8d9c2dc78a9047d4a243d316e87dd782;\n",
+ "n8d9c2dc78a9047d4a243d316e87dd782 [label=\"aa\\nd\\naad\"];\n",
+ "n8d9c2dc78a9047d4a243d316e87dd782 -> n6d893e899f6f4f77a30c3be1eeef25d0;\n",
+ "n6d893e899f6f4f77a30c3be1eeef25d0 [label=\"aa\\n-\\naa\\nTrue\"];\n"
+ ]
+ }
+ ],
+ "source": [
+ "root, graph = is_interleave_recursive_dot(s1, s2, s3t)\n",
+ "print('\\n'.join(graph))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 43,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "n8ab105a57ff44daa8fa8c0bd8275721c [label=\"aaa\\naaa\\naaaaaa\"];\n",
+ "n8ab105a57ff44daa8fa8c0bd8275721c -> ndd3ec050e4d441ba9f5eca4140804aa2;\n",
+ "n8ab105a57ff44daa8fa8c0bd8275721c -> n5fe9af06410d4e3796f3e5b09724befb;\n",
+ "ndd3ec050e4d441ba9f5eca4140804aa2 [label=\"aa\\naaa\\naaaaa\"];\n",
+ "ndd3ec050e4d441ba9f5eca4140804aa2 -> n4da003b54dd94728a1aa1890f1a9250a;\n",
+ "ndd3ec050e4d441ba9f5eca4140804aa2 -> ncb2a3fd92dc6414a99dc115990760e7c;\n",
+ "n4da003b54dd94728a1aa1890f1a9250a [label=\"a\\naaa\\naaaa\"];\n",
+ "n4da003b54dd94728a1aa1890f1a9250a -> n699e6ec8bba74ec394a68d5c2d306c30;\n",
+ "n4da003b54dd94728a1aa1890f1a9250a -> n71376b3b5e614617ba68dccf8d9677cc;\n",
+ "n699e6ec8bba74ec394a68d5c2d306c30 [label=\"-\\naaa\\naaa\\nTrue\"];\n",
+ "n71376b3b5e614617ba68dccf8d9677cc [label=\"a\\naa\\naaa\"];\n",
+ "n71376b3b5e614617ba68dccf8d9677cc -> nb876b970b38f4ba2937a69ba491f308c;\n",
+ "n71376b3b5e614617ba68dccf8d9677cc -> nfb2ebec95c5c46c6b160c511031f5417;\n",
+ "nb876b970b38f4ba2937a69ba491f308c [label=\"-\\naa\\naa\\nTrue\"];\n",
+ "nfb2ebec95c5c46c6b160c511031f5417 [label=\"a\\na\\naa\"];\n",
+ "nfb2ebec95c5c46c6b160c511031f5417 -> ndcf30cbbd8f646adb30c01e8fbc8aaaf;\n",
+ "nfb2ebec95c5c46c6b160c511031f5417 -> n9bb6593bab3c47e59f83df2767b67a3a;\n",
+ "ndcf30cbbd8f646adb30c01e8fbc8aaaf [label=\"-\\na\\na\\nTrue\"];\n",
+ "n9bb6593bab3c47e59f83df2767b67a3a [label=\"a\\n-\\na\\nTrue\"];\n",
+ "ncb2a3fd92dc6414a99dc115990760e7c [label=\"aa\\naa\\naaaa\"];\n",
+ "ncb2a3fd92dc6414a99dc115990760e7c -> n937d754714994223bc97015534e1806e;\n",
+ "ncb2a3fd92dc6414a99dc115990760e7c -> n553eac2d6c4542448a5c82b781e963b1;\n",
+ "n937d754714994223bc97015534e1806e [label=\"a\\naa\\naaa\"];\n",
+ "n937d754714994223bc97015534e1806e -> n08a6688eb7df48f8834787728a0e36a2;\n",
+ "n937d754714994223bc97015534e1806e -> n063d395576474c5b82d810b2b70e7e3c;\n",
+ "n08a6688eb7df48f8834787728a0e36a2 [label=\"-\\naa\\naa\\nTrue\"];\n",
+ "n063d395576474c5b82d810b2b70e7e3c [label=\"a\\na\\naa\"];\n",
+ "n063d395576474c5b82d810b2b70e7e3c -> n04b9f6aea46c458da227558ab02a0b4c;\n",
+ "n063d395576474c5b82d810b2b70e7e3c -> nc067208a5ab64f8c9904d58b738b81e4;\n",
+ "n04b9f6aea46c458da227558ab02a0b4c [label=\"-\\na\\na\\nTrue\"];\n",
+ "nc067208a5ab64f8c9904d58b738b81e4 [label=\"a\\n-\\na\\nTrue\"];\n",
+ "n553eac2d6c4542448a5c82b781e963b1 [label=\"aa\\na\\naaa\"];\n",
+ "n553eac2d6c4542448a5c82b781e963b1 -> n5d50905c46ce4dc8bcb59fb62984fa54;\n",
+ "n553eac2d6c4542448a5c82b781e963b1 -> n6768e9ad78804e65b1bde9cb655f2a60;\n",
+ "n5d50905c46ce4dc8bcb59fb62984fa54 [label=\"a\\na\\naa\"];\n",
+ "n5d50905c46ce4dc8bcb59fb62984fa54 -> n22bc48dd2aa84e79a387252cc28f3a92;\n",
+ "n5d50905c46ce4dc8bcb59fb62984fa54 -> n853ef88a20ee48a4bccf390498c96f5d;\n",
+ "n22bc48dd2aa84e79a387252cc28f3a92 [label=\"-\\na\\na\\nTrue\"];\n",
+ "n853ef88a20ee48a4bccf390498c96f5d [label=\"a\\n-\\na\\nTrue\"];\n",
+ "n6768e9ad78804e65b1bde9cb655f2a60 [label=\"aa\\n-\\naa\\nTrue\"];\n",
+ "n5fe9af06410d4e3796f3e5b09724befb [label=\"aaa\\naa\\naaaaa\"];\n",
+ "n5fe9af06410d4e3796f3e5b09724befb -> ne6b19fc7e02b4981a1edc20c7fe0cce0;\n",
+ "n5fe9af06410d4e3796f3e5b09724befb -> ne0c07d6d54f045a5b4bf9eb10bd8d810;\n",
+ "ne6b19fc7e02b4981a1edc20c7fe0cce0 [label=\"aa\\naa\\naaaa\"];\n",
+ "ne6b19fc7e02b4981a1edc20c7fe0cce0 -> n9d2cfd4e9cf2473bbd05a8a7e2a96714;\n",
+ "ne6b19fc7e02b4981a1edc20c7fe0cce0 -> n3d4e61bc032c4f8387c269d8ac49cc3f;\n",
+ "n9d2cfd4e9cf2473bbd05a8a7e2a96714 [label=\"a\\naa\\naaa\"];\n",
+ "n9d2cfd4e9cf2473bbd05a8a7e2a96714 -> n214f88e71d504eaba78b46c5a5bbe31d;\n",
+ "n9d2cfd4e9cf2473bbd05a8a7e2a96714 -> n2890559b11cb49c9aa083a76a7b68ce4;\n",
+ "n214f88e71d504eaba78b46c5a5bbe31d [label=\"-\\naa\\naa\\nTrue\"];\n",
+ "n2890559b11cb49c9aa083a76a7b68ce4 [label=\"a\\na\\naa\"];\n",
+ "n2890559b11cb49c9aa083a76a7b68ce4 -> n5d37f312b10341d09e2faa4fb4f40e3c;\n",
+ "n2890559b11cb49c9aa083a76a7b68ce4 -> nd73fc499c4214ddbbe7155f97c9ff394;\n",
+ "n5d37f312b10341d09e2faa4fb4f40e3c [label=\"-\\na\\na\\nTrue\"];\n",
+ "nd73fc499c4214ddbbe7155f97c9ff394 [label=\"a\\n-\\na\\nTrue\"];\n",
+ "n3d4e61bc032c4f8387c269d8ac49cc3f [label=\"aa\\na\\naaa\"];\n",
+ "n3d4e61bc032c4f8387c269d8ac49cc3f -> nfac20fc8bb7441f891ac0380259f3b76;\n",
+ "n3d4e61bc032c4f8387c269d8ac49cc3f -> n9d9c86dc313f48b69d9c2693ee32e7ab;\n",
+ "nfac20fc8bb7441f891ac0380259f3b76 [label=\"a\\na\\naa\"];\n",
+ "nfac20fc8bb7441f891ac0380259f3b76 -> n14489559bae24e99b2d816716ceef683;\n",
+ "nfac20fc8bb7441f891ac0380259f3b76 -> n44c425cd261c4c19971a47901723f942;\n",
+ "n14489559bae24e99b2d816716ceef683 [label=\"-\\na\\na\\nTrue\"];\n",
+ "n44c425cd261c4c19971a47901723f942 [label=\"a\\n-\\na\\nTrue\"];\n",
+ "n9d9c86dc313f48b69d9c2693ee32e7ab [label=\"aa\\n-\\naa\\nTrue\"];\n",
+ "ne0c07d6d54f045a5b4bf9eb10bd8d810 [label=\"aaa\\na\\naaaa\"];\n",
+ "ne0c07d6d54f045a5b4bf9eb10bd8d810 -> n8d8289489db44271b99f22c572668eaa;\n",
+ "ne0c07d6d54f045a5b4bf9eb10bd8d810 -> n4eda0dd1e0e34c8c9a81beba5c70fe5f;\n",
+ "n8d8289489db44271b99f22c572668eaa [label=\"aa\\na\\naaa\"];\n",
+ "n8d8289489db44271b99f22c572668eaa -> n156514e9dbcb44a8a6b4d96f1ec3e48f;\n",
+ "n8d8289489db44271b99f22c572668eaa -> n3ba7c5a0cc3b405aa6ca7899ee85a518;\n",
+ "n156514e9dbcb44a8a6b4d96f1ec3e48f [label=\"a\\na\\naa\"];\n",
+ "n156514e9dbcb44a8a6b4d96f1ec3e48f -> n3b99ff94eb914661bafe9ba4c0c997e2;\n",
+ "n156514e9dbcb44a8a6b4d96f1ec3e48f -> n91eac98d4ed74a1f99fd48ca60111d2c;\n",
+ "n3b99ff94eb914661bafe9ba4c0c997e2 [label=\"-\\na\\na\\nTrue\"];\n",
+ "n91eac98d4ed74a1f99fd48ca60111d2c [label=\"a\\n-\\na\\nTrue\"];\n",
+ "n3ba7c5a0cc3b405aa6ca7899ee85a518 [label=\"aa\\n-\\naa\\nTrue\"];\n",
+ "n4eda0dd1e0e34c8c9a81beba5c70fe5f [label=\"aaa\\n-\\naaa\\nTrue\"];\n"
+ ]
+ }
+ ],
+ "source": [
+ "root, graph = is_interleave_recursive_dot('aaa', 'aaa', 'aaaaaa')\n",
+ "print('\\n'.join(graph))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 44,
+ "metadata": {
+ "scrolled": true
+ },
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "n5d63e71661ed4a8ead31b5c5f9c1949b [label=\"acb\\naba\\nabacab\"];\n",
+ "n5d63e71661ed4a8ead31b5c5f9c1949b -> n11bd1802979b4332bdf9cf6cc3b2a51c;\n",
+ "n11bd1802979b4332bdf9cf6cc3b2a51c [label=\"ac\\naba\\nabaca\"];\n",
+ "n11bd1802979b4332bdf9cf6cc3b2a51c -> n8a082af1ba074b84b7410b97554be94f;\n",
+ "n8a082af1ba074b84b7410b97554be94f [label=\"ac\\nab\\nabac\"];\n",
+ "n8a082af1ba074b84b7410b97554be94f -> n6ec78858d88046c8b8531a63f38825b3;\n",
+ "n6ec78858d88046c8b8531a63f38825b3 [label=\"a\\nab\\naba\"];\n",
+ "n6ec78858d88046c8b8531a63f38825b3 -> na563514a3f194725be7160850c3c8369;\n",
+ "na563514a3f194725be7160850c3c8369 [label=\"-\\nab\\nab\\nTrue\"];\n"
+ ]
+ }
+ ],
+ "source": [
+ "root, graph = is_interleave_recursive_dot(e1, e2, e3)\n",
+ "print('\\n'.join(graph))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "s1 = make_string(500)\n",
+ "s2 = make_string(500)\n",
+ "s3 = make_string(500)\n",
+ "s12 = interleave(s1, s2)\n",
+ "s23 = interleave(s2, s3)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "execution_count": 48,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "is_interleave_recursive(s1, s2, s12)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "False"
+ ]
+ },
+ "execution_count": 49,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "is_interleave_recursive(s1, s2, s23)"
+ ]
+ },
+ {
+ "cell_type": "markdown",
+ "metadata": {},
+ "source": [
+ "## Example"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 50,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_annotated_table(table, bps):\n",
+ " return '\\n'.join(' '.join('*' if (i, j) == (0, 0) 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": 51,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def show_backtrace_star(bps):\n",
+ " i = max([0] + [k[0] for k in bps])\n",
+ " j = max([0] + [k[1] for k in bps])\n",
+ " chars = ''\n",
+ " stars = ''\n",
+ " if (i, j) in bps:\n",
+ " while i != 0 or j != 0:\n",
+ " chars += bps[i, j][2]\n",
+ " if bps[i, j][3] == 'seq1':\n",
+ " stars += '*'\n",
+ " else:\n",
+ " stars += ' '\n",
+ " i, j = bps[i, j][0], bps[i, j][1] \n",
+ " return ''.join(list(reversed(chars))) + '\\n' + ''.join(list(reversed(stars)))\n",
+ " else:\n",
+ " return ''"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "0: ddadbdcbdc\n",
+ "1: bbcbbabdab\n",
+ "2: dcddddbbdb\n",
+ "3: cccbbbcbabadbddcabda\n",
+ "4: ddcdddadddbbbddbcbdc\n",
+ "5: dcccdddcbdbadbdbdcda\n",
+ "6: ddadbbcbbbdacbbdcdab\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "['ddadbbcbbbdacbbdcdab']"
+ ]
+ },
+ "execution_count": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "s1 = make_string(10, alphabet='abcd')\n",
+ "s2 = make_string(10, alphabet='abcd')\n",
+ "s3 = make_string(10, alphabet='abcd')\n",
+ "s4 = make_string(10, alphabet='abcd')\n",
+ "il = interleave(s1, s2)\n",
+ "bs = [s3, il, interleave(s3, s4), interleave(s2, s4), interleave(s1, s3)]\n",
+ "random.shuffle(bs)\n",
+ "bs = [s1, s2] + bs\n",
+ "tg = [l for l in bs if is_interleave(s1, s2, l)]\n",
+ "print('\\n'.join(['{}: {}'.format(i, s) for i, s in enumerate(bs)]))\n",
+ "tg"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 53,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "* . . . . . . . . . .\n",
+ "d . . . . . . . . . .\n",
+ "d . . . . . . . . . .\n",
+ "a . . . . . . . . . .\n",
+ "d b b c b b . . . . .\n",
+ "b b . b b b . . . . .\n",
+ ". . . . . d a . . . .\n",
+ ". . . . . . c b . . .\n",
+ ". . . . . . b b d . .\n",
+ ". . . . . . . d . . .\n",
+ ". . . . . . . c d a b\n",
+ "DDADbbcbbBDaCbBDCdab\n",
+ "ddadbbcbbbdacbbdcdab\n",
+ "**** ** * *** \n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "execution_count": 53,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "v, bp, t = is_interleave(s1, s2, il, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace(bp))\n",
+ "print(show_backtrace_star(bp))\n",
+ "v"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 54,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "ddcdddadddbbbddbcbdc\n",
+ " * ** * * * ****\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "4"
+ ]
+ },
+ "execution_count": 54,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "ind = [i for i, b in enumerate(bs) if is_interleave(s1, s3, b)][0]\n",
+ "v, bp = is_interleave(s1, s3, bs[ind], return_backpointers=True)\n",
+ "print(show_backtrace_star(bp))\n",
+ "ind"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 55,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "* d d a d b . . . . .\n",
+ ". . . . b b . . . . .\n",
+ ". . . . b . . . . . .\n",
+ ". . . . c b . . . . .\n",
+ ". . . . b b . . . . .\n",
+ ". . . . b b d . . . .\n",
+ ". . . . . . a c b . .\n",
+ ". . . . . . . b b d c\n",
+ ". . . . . . . . d . d\n",
+ ". . . . . . . . . . a\n",
+ ". . . . . . . . . . b\n",
+ "ddadBBCbBBdAcbBdcDAB\n",
+ "ddadbbcbbbdacbbdcdab\n",
+ " *** ** * * ***\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "True"
+ ]
+ },
+ "execution_count": 55,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "v, bp, t = is_interleave(s2, s1, il, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace(bp))\n",
+ "print(show_backtrace_star(bp))\n",
+ "v"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 56,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "* d . . . . . . . . .\n",
+ "d d . . . . . . . . .\n",
+ "d . . . . . . . . . .\n",
+ "a d . . . . . . . . .\n",
+ "d . . . . . . . . . .\n",
+ "b . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ "\n",
+ "\n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "False"
+ ]
+ },
+ "execution_count": 56,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "v, bp, t = is_interleave(s1, s3, il, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace(bp))\n",
+ "print(show_backtrace_star(bp))\n",
+ "v"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 57,
+ "metadata": {},
+ "outputs": [
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "text": [
+ "* d . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ ". . . . . . . . . . .\n",
+ "d\n",
+ "d\n",
+ " \n"
+ ]
+ },
+ {
+ "data": {
+ "text/plain": [
+ "False"
+ ]
+ },
+ "execution_count": 57,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "v, bp, t = is_interleave(s2, s3, il, return_backpointers=True, return_table=True)\n",
+ "print(show_annotated_table(t, bp))\n",
+ "print(show_backtrace(bp))\n",
+ "print(show_backtrace_star(bp))\n",