Dynamursion clear solution for DNA Common Sequence by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Dynamursion solution in Clear category for DNA Common Sequence by veky

import functools

@functools.lru_cache(maxsize=None)
def cset(X, Y):
    if not (X and Y): return {""}
    if X[0] == Y[0]: return {X[0] + seq for seq in cset(X[1:], Y[1:])}
    seqs = cset(X, Y[1:]) | cset(X[1:], Y)
    return {seq for seq in seqs if len(seq) == max(map(len, seqs))}

common = lambda *args: ",".join(sorted(cset(*args)))

Dec. 27, 2014

Comments:

taras-sereda on March 31, 2015, 9:24 p.m.
Your solution is so short! Currently I'm on the way of understanding it with help of <a href="http://www.pythontutor.com/">http://www.pythontutor.com/</a>

veky on April 1, 2015, 4:16 a.m.
It is short because I use Python's batteries. :-) Pseudocode: <pre class='brush: python'>common is just a wrapper around recursive function cset, which returns a set of common subsequences of maximal length (CSOML) common just sorts (lexicographically) and joins (with ",") cset's result cset (memoized recursive function) of sequences X and Y has three cases: if any of them is empty, the only common subsequence is the empty one else if they agree on first letter, every CSOML must start with that letter else, ignore first letter of each, recursively compute csets, union them, and return those sequences in the union having maximal length </pre> See <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences">Wikipedia</a>: the only difference is they go from the end (see if they agree on the last letter) instead of from the beginning as I do. If there's anything more I can help you with understanding, feel free to ask.

taras-sereda on April 1, 2015, 8:42 p.m.
thanks for your clarifications. Python's batteries are clear here, hopefully )) The most tricky part from here is recursion. I also used this approach, but it was more like rewriting pseudocode from <a href="http://www.wikiwand.com/en/Longest_common_subsequence_problem#/Solution_for_two_sequences">Wiki</a> At each return after performing, join only sequences of max len at particular stage are left. So it means that at the time of last return only globally max len LCSs will be considered. Right? I want to make sure if I understand it correctly that, the nature of returning only max len LCSs on each step, eliminates earlier LCSs for strings portions.

veky on April 1, 2015, 9:42 p.m.
Yes, only without ",".joining (it is performed only at the end). The union is filtered to only subsequences of maximal length. It is correct to do so, since if first letter is the same, obviously max(1+l) = 1+max(l), and if not, then we consider all the other cases anyway.

taras-sereda on April 2, 2015, 7:26 a.m.
It's clear. But I can't grasp your proof of correctness of filtering union to only subsequences of max len. How this statement proofs this fact? <pre class='brush: python'>max(1+l) = 1+max(l) </pre> From my understanding, It's more about overall proof of algorithm correctness, considering the fact, that in case first letters are different we consider all other cases. Am I right? But I can't apply this statement for proving correctness of filtering only max LCSs. I consider it in the following way, only max LCSs comes from initial task formulation. Hence it's correct to filter smaller LCSs. (which are also parts of max LCSs)

veky on April 2, 2015, 9:07 a.m.
Yes, but the only point where we actually might lose some shorter subsubsequences of longer final common subsequences, is when the first letters are the same, and there the above identity shows us that we won't lose anything of value - because when we tear off that first letter, concentrate only on maximal subsequences, and then put that one letter back, we will get maximal subsequences of the whole task. It seems we are speaking about the same thing, maybe only in a bit different language. :-)

taras-sereda on April 2, 2015, 9:26 a.m.
Totally agree with you. Thanks for conversation!

hrvoje on July 3, 2015, 2:23 p.m.
Just ... wow. I didn't know about lru_cache and had to improvise with dict(). Also, never seen lambda *args. 5 thumbs!

veky on July 4, 2015, 6:11 a.m.
<blockquote> I didn’t know about lru_cache </blockquote> Naturally. This is one of those things you'll never learn if you concentrate on golfing only. It's 50 characters, and gives you almost nothing functionally. Yet it's incredibly useful. That's why I think you're exaggerating with your focus on golf. <blockquote> never seen lambda *args. </blockquote> That even might come useful when golfing. :-] lambda signature has the same rules as def one. You can use **kw, lone star (you know what that is?:), default values... and since Py3 you cannot use destructuring. :-)

hrvoje on July 4, 2015, 12:06 p.m.
I know, but golfing is sooooo much fun. :) You finish something with a big, proud grin on your face only to find out somebody else did it in 50 characters less and you have no idea how. It's like a game within a game :) Oh, and this code came in an anonymous review so I had no idea it was you, but I suspected. :)

veky on July 4, 2015, 1:33 p.m.
I'm becoming predictable. Even in a Bayesian* way. :-) * By that I man not only P(code|Veky) is high, but P(Veky|code) is high. :-D

CDG.Axel on Dec. 3, 2021, 12:09 a.m.
Interesting, but with this tail for cset proc it works 9 times faster: <pre class='brush: python'>max_len = max(map(len, seqs)) return {seq for seq in seqs if len(seq) == max_len} </pre> Why python calculate max(map(len, seqs)) for all elements?

veky on Dec. 3, 2021, 3:40 a.m.
Because it has to. :-) Python compiler has no idea that (a) max, map and len refer to builtins at the time of execution, and that (b) seqs doesn't conditionally delete some of its elements when iterating through it. Read <a href="https://www.python.org/dev/peps/pep-0509/">PEP 509</a> [including its famous sentence "A risk of a bug every 584 years is acceptable." :]] for some interesting ideas of what can be done to overcome (a), but it's still a long way to a final solution, and besides, (b) is still a possibility to consider.

Codeship

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.