palindrome.py

import random
import io
import time


def profile(func):
    def wrapper(*args):
        start = time.clock()
        rv = func(*args)
        end = time.clock()
        return (rv, end-start)
    return wrapper


@profile
def longest_palindrome(text):
    current, longest = [], (0, 0)
    # catch the special cases
    if len(text) == 1:
        longest = (0, 1)
    elif text[0] == text[1]:
        longest = (0, 2)
    for i in range(2, len(text)):
        next_round = []
        for start, length in current:
            if start > 0 and text[i] == text[start-1]:
                next_round.append( (start - 1, length + 2))
            elif length > longest[1]: #
                longest = (start, length)
        if text[i] == text[i-1]:
            next_round.append(( i - 1, 2))
        if text[i] == text[i-2]:
            next_round.append(( i - 2, 3))
        current = next_round
    for start, length in current:
        if length > longest[1]:
            longest = (start, length)
    return text[longest[0]:longest[0]+longest[1]]


@profile
def generate_sequence(length, alphabet="ATGC"):
    f = io.StringIO()
    for _ in range(length):
        f.write(random.choice(alphabet))
    return f.getvalue()

def is_palindrome(seq):
    # cheap way out, thanks to SO
    return seq[::-1] == seq


MEGABYTE=1024*1024
ALPHABET='ATCG'
PROFILE=[]

for i in range(1, 16):
    SEQUENCE, _ = generate_sequence(i*MEGABYTE)
    PALINDROME, duration = longest_palindrome(SEQUENCE)
    PROFILE.append((PALINDROME, duration))
    if not is_palindrome(PALINDROME):
        raise ValueError('{O} is not a palindrome'.format(PALINDROME))


for i, (p, d) in enumerate(PROFILE):
    print("{0}M: {1:.3f}s {2} '{3}'".format(i+1, d, len(p), p))