First clear solution for DNA Common Sequence by Sim0000 - python coding challenges

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

First solution in Clear category for DNA Common Sequence by Sim0000

def common(dna1, dna2):
    d = {}
    for i, c1 in enumerate(dna1):
        for j, c2 in enumerate(dna2):
            if c1 == c2:
                n, s = d.get((i - 1, j - 1), (0, {''}))
                d[(i, j)] = (n + 1, {x + c1 for x in s})
            else:
                n1, s1 = d.get((i - 1, j), (0, {''}))
                n2, s2 = d.get((i, j - 1), (0, {''}))
                d[(i, j)] = (n1, s1 | s2) if n1 == n2 else (n1, s1) if n1 > n2 else (n2, s2)
    return ','.join(sorted(d[(len(dna1) - 1, len(dna2) - 1)][1]))
    
    # Dynamic Programming

Dec. 11, 2014

Comments:

veky on Dec. 27, 2014, 8:59 a.m.
First, a defaultdict would really help here. :-) Second, you don't need () inside [] indexing. Just d[i, j]. Third, end of line 11 can be just `... else max((n1, s1), (n2, s2))`. Tuples compare sensibly. :-) And fourth, you can get by without tracking lengths all the time, just calculate when needed. See my solution. :-)

Sim0000 on Dec. 31, 2014, 11:24 a.m.
Thanks veky. I publish <a href="http://www.checkio.org/mission/dna-common-sequence/publications/Sim0000/python-3/defaultdict/">revised version</a>.

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.