#!/usr/bin/env python
# coding=utf-8
 
# Open Reading Frames
# ===================
# 
# Either strand of a DNA double helix can serve as the coding strand for RNA
# transcription. Hence, a given DNA string implies six total reading frames, or
# ways in which the same region of DNA can be translated into amino acids: three
# reading frames result from reading the string itself, whereas three more
# result from reading its reverse complement.
# 
# An open reading frame (ORF) is one which starts from the start codon and ends
# by stop codon, without any other stop codons in between. Thus, a candidate
# protein string is derived by translating an open reading frame into amino
# acids until a stop codon is reached.
# 
# Given: A DNA string s of length at most 1 kbp.
# 
# Return: Every distinct candidate protein string that can be translated from
# ORFs of s. Strings can be returned in any order.
# 
# Sample Dataset
# --------------
# AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG
# 
# Sample Output
# -------------
# MLLGSFRLIPKETLIQVAGSSPCNLS
# M
# MGMTPRLGLESLLE
# MTPRLGLESLLE
 
 
DNA_CODON_TABLE = {
    'TTT': 'F',     'CTT': 'L',     'ATT': 'I',     'GTT': 'V',
    'TTC': 'F',     'CTC': 'L',     'ATC': 'I',     'GTC': 'V',
    'TTA': 'L',     'CTA': 'L',     'ATA': 'I',     'GTA': 'V',
    'TTG': 'L',     'CTG': 'L',     'ATG': 'M',     'GTG': 'V',
    'TCT': 'S',     'CCT': 'P',     'ACT': 'T',     'GCT': 'A',
    'TCC': 'S',     'CCC': 'P',     'ACC': 'T',     'GCC': 'A',
    'TCA': 'S',     'CCA': 'P',     'ACA': 'T',     'GCA': 'A',
    'TCG': 'S',     'CCG': 'P',     'ACG': 'T',     'GCG': 'A',
    'TAT': 'Y',     'CAT': 'H',     'AAT': 'N',     'GAT': 'D',
    'TAC': 'Y',     'CAC': 'H',     'AAC': 'N',     'GAC': 'D',
    'TAA': 'Stop',  'CAA': 'Q',     'AAA': 'K',     'GAA': 'E',
    'TAG': 'Stop',  'CAG': 'Q',     'AAG': 'K',     'GAG': 'E',
    'TGT': 'C',     'CGT': 'R',     'AGT': 'S',     'GGT': 'G',
    'TGC': 'C',     'CGC': 'R',     'AGC': 'S',     'GGC': 'G',
    'TGA': 'Stop',  'CGA': 'R',     'AGA': 'R',     'GGA': 'G',
    'TGG': 'W',     'CGG': 'R',     'AGG': 'R',     'GGG': 'G'
}
 
 
def translate_codon(codon):
    protein = None
    if len(codon) == 3 and DNA_CODON_TABLE.has_key(codon):
        protein = DNA_CODON_TABLE[codon]
    return protein
 
 
def reverse_complement(dna):
    lookup = {'A':'T', 'T':'A', 'G':'C', 'C':'G'}
    return ''.join([lookup[c] for c in reversed(dna)])
 
 
def possible_protein_strings(s):
    results = []
    indices = []
 
    l = len(s)
    for i in range(l):
        protein = translate_codon(s[i:i+3])
        if protein and protein == 'M':
            indices.append(i)
 
    for i in indices:
        found_stop = False
        protein_string = ''
 
        for j in range(i, l, 3):
            protein = translate_codon(s[j:j+3])
 
            if not protein:
                break
 
            if protein == 'Stop':
                found_stop = True
                break
 
            protein_string += protein
 
        if found_stop:
            results.append(protein_string)
 
    return results
 
 
if __name__ == "__main__":
 
    small_dataset = "AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG"
 
    possible_a = possible_protein_strings(small_dataset)
    possible_b = possible_protein_strings(reverse_complement(small_dataset))
    print "\n".join(set(possible_a + possible_b))

IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiMgY29kaW5nPXV0Zi04CgojIE9wZW4gUmVhZGluZyBGcmFtZXMKIyA9PT09PT09PT09PT09PT09PT09CiMgCiMgRWl0aGVyIHN0cmFuZCBvZiBhIEROQSBkb3VibGUgaGVsaXggY2FuIHNlcnZlIGFzIHRoZSBjb2Rpbmcgc3RyYW5kIGZvciBSTkEKIyB0cmFuc2NyaXB0aW9uLiBIZW5jZSwgYSBnaXZlbiBETkEgc3RyaW5nIGltcGxpZXMgc2l4IHRvdGFsIHJlYWRpbmcgZnJhbWVzLCBvcgojIHdheXMgaW4gd2hpY2ggdGhlIHNhbWUgcmVnaW9uIG9mIEROQSBjYW4gYmUgdHJhbnNsYXRlZCBpbnRvIGFtaW5vIGFjaWRzOiB0aHJlZQojIHJlYWRpbmcgZnJhbWVzIHJlc3VsdCBmcm9tIHJlYWRpbmcgdGhlIHN0cmluZyBpdHNlbGYsIHdoZXJlYXMgdGhyZWUgbW9yZQojIHJlc3VsdCBmcm9tIHJlYWRpbmcgaXRzIHJldmVyc2UgY29tcGxlbWVudC4KIyAKIyBBbiBvcGVuIHJlYWRpbmcgZnJhbWUgKE9SRikgaXMgb25lIHdoaWNoIHN0YXJ0cyBmcm9tIHRoZSBzdGFydCBjb2RvbiBhbmQgZW5kcwojIGJ5IHN0b3AgY29kb24sIHdpdGhvdXQgYW55IG90aGVyIHN0b3AgY29kb25zIGluIGJldHdlZW4uIFRodXMsIGEgY2FuZGlkYXRlCiMgcHJvdGVpbiBzdHJpbmcgaXMgZGVyaXZlZCBieSB0cmFuc2xhdGluZyBhbiBvcGVuIHJlYWRpbmcgZnJhbWUgaW50byBhbWlubwojIGFjaWRzIHVudGlsIGEgc3RvcCBjb2RvbiBpcyByZWFjaGVkLgojIAojIEdpdmVuOiBBIEROQSBzdHJpbmcgcyBvZiBsZW5ndGggYXQgbW9zdCAxIGticC4KIyAKIyBSZXR1cm46IEV2ZXJ5IGRpc3RpbmN0IGNhbmRpZGF0ZSBwcm90ZWluIHN0cmluZyB0aGF0IGNhbiBiZSB0cmFuc2xhdGVkIGZyb20KIyBPUkZzIG9mIHMuIFN0cmluZ3MgY2FuIGJlIHJldHVybmVkIGluIGFueSBvcmRlci4KIyAKIyBTYW1wbGUgRGF0YXNldAojIC0tLS0tLS0tLS0tLS0tCiMgQUdDQ0FUR1RBR0NUQUFDVENBR0dUVEFDQVRHR0dHQVRHQUNDQ0NHQ0dBQ1RUR0dBVFRBR0FHVENUQ1RUVFRHR0FBVEFBR0NDVEdBQVRHQVRDQ0dBR1RBR0NBVENUQ0FHCiMgCiMgU2FtcGxlIE91dHB1dAojIC0tLS0tLS0tLS0tLS0KIyBNTExHU0ZSTElQS0VUTElRVkFHU1NQQ05MUwojIE0KIyBNR01UUFJMR0xFU0xMRQojIE1UUFJMR0xFU0xMRQoKCkROQV9DT0RPTl9UQUJMRSA9IHsKICAgICdUVFQnOiAnRicsICAgICAnQ1RUJzogJ0wnLCAgICAgJ0FUVCc6ICdJJywgICAgICdHVFQnOiAnVicsCiAgICAnVFRDJzogJ0YnLCAgICAgJ0NUQyc6ICdMJywgICAgICdBVEMnOiAnSScsICAgICAnR1RDJzogJ1YnLAogICAgJ1RUQSc6ICdMJywgICAgICdDVEEnOiAnTCcsICAgICAnQVRBJzogJ0knLCAgICAgJ0dUQSc6ICdWJywKICAgICdUVEcnOiAnTCcsICAgICAnQ1RHJzogJ0wnLCAgICAgJ0FURyc6ICdNJywgICAgICdHVEcnOiAnVicsCiAgICAnVENUJzogJ1MnLCAgICAgJ0NDVCc6ICdQJywgICAgICdBQ1QnOiAnVCcsICAgICAnR0NUJzogJ0EnLAogICAgJ1RDQyc6ICdTJywgICAgICdDQ0MnOiAnUCcsICAgICAnQUNDJzogJ1QnLCAgICAgJ0dDQyc6ICdBJywKICAgICdUQ0EnOiAnUycsICAgICAnQ0NBJzogJ1AnLCAgICAgJ0FDQSc6ICdUJywgICAgICdHQ0EnOiAnQScsCiAgICAnVENHJzogJ1MnLCAgICAgJ0NDRyc6ICdQJywgICAgICdBQ0cnOiAnVCcsICAgICAnR0NHJzogJ0EnLAogICAgJ1RBVCc6ICdZJywgICAgICdDQVQnOiAnSCcsICAgICAnQUFUJzogJ04nLCAgICAgJ0dBVCc6ICdEJywKICAgICdUQUMnOiAnWScsICAgICAnQ0FDJzogJ0gnLCAgICAgJ0FBQyc6ICdOJywgICAgICdHQUMnOiAnRCcsCiAgICAnVEFBJzogJ1N0b3AnLCAgJ0NBQSc6ICdRJywgICAgICdBQUEnOiAnSycsICAgICAnR0FBJzogJ0UnLAogICAgJ1RBRyc6ICdTdG9wJywgICdDQUcnOiAnUScsICAgICAnQUFHJzogJ0snLCAgICAgJ0dBRyc6ICdFJywKICAgICdUR1QnOiAnQycsICAgICAnQ0dUJzogJ1InLCAgICAgJ0FHVCc6ICdTJywgICAgICdHR1QnOiAnRycsCiAgICAnVEdDJzogJ0MnLCAgICAgJ0NHQyc6ICdSJywgICAgICdBR0MnOiAnUycsICAgICAnR0dDJzogJ0cnLAogICAgJ1RHQSc6ICdTdG9wJywgICdDR0EnOiAnUicsICAgICAnQUdBJzogJ1InLCAgICAgJ0dHQSc6ICdHJywKICAgICdUR0cnOiAnVycsICAgICAnQ0dHJzogJ1InLCAgICAgJ0FHRyc6ICdSJywgICAgICdHR0cnOiAnRycKfQoKCmRlZiB0cmFuc2xhdGVfY29kb24oY29kb24pOgogICAgcHJvdGVpbiA9IE5vbmUKICAgIGlmIGxlbihjb2RvbikgPT0gMyBhbmQgRE5BX0NPRE9OX1RBQkxFLmhhc19rZXkoY29kb24pOgogICAgICAgIHByb3RlaW4gPSBETkFfQ09ET05fVEFCTEVbY29kb25dCiAgICByZXR1cm4gcHJvdGVpbgoKCmRlZiByZXZlcnNlX2NvbXBsZW1lbnQoZG5hKToKICAgIGxvb2t1cCA9IHsnQSc6J1QnLCAnVCc6J0EnLCAnRyc6J0MnLCAnQyc6J0cnfQogICAgcmV0dXJuICcnLmpvaW4oW2xvb2t1cFtjXSBmb3IgYyBpbiByZXZlcnNlZChkbmEpXSkKCgpkZWYgcG9zc2libGVfcHJvdGVpbl9zdHJpbmdzKHMpOgogICAgcmVzdWx0cyA9IFtdCiAgICBpbmRpY2VzID0gW10KCiAgICBsID0gbGVuKHMpCiAgICBmb3IgaSBpbiByYW5nZShsKToKICAgICAgICBwcm90ZWluID0gdHJhbnNsYXRlX2NvZG9uKHNbaTppKzNdKQogICAgICAgIGlmIHByb3RlaW4gYW5kIHByb3RlaW4gPT0gJ00nOgogICAgICAgICAgICBpbmRpY2VzLmFwcGVuZChpKQoKICAgIGZvciBpIGluIGluZGljZXM6CiAgICAgICAgZm91bmRfc3RvcCA9IEZhbHNlCiAgICAgICAgcHJvdGVpbl9zdHJpbmcgPSAnJwoKICAgICAgICBmb3IgaiBpbiByYW5nZShpLCBsLCAzKToKICAgICAgICAgICAgcHJvdGVpbiA9IHRyYW5zbGF0ZV9jb2RvbihzW2o6aiszXSkKCiAgICAgICAgICAgIGlmIG5vdCBwcm90ZWluOgogICAgICAgICAgICAgICAgYnJlYWsKCiAgICAgICAgICAgIGlmIHByb3RlaW4gPT0gJ1N0b3AnOgogICAgICAgICAgICAgICAgZm91bmRfc3RvcCA9IFRydWUKICAgICAgICAgICAgICAgIGJyZWFrCgogICAgICAgICAgICBwcm90ZWluX3N0cmluZyArPSBwcm90ZWluCgogICAgICAgIGlmIGZvdW5kX3N0b3A6CiAgICAgICAgICAgIHJlc3VsdHMuYXBwZW5kKHByb3RlaW5fc3RyaW5nKQoKICAgIHJldHVybiByZXN1bHRzCgoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKCiAgICBzbWFsbF9kYXRhc2V0ID0gIkFHQ0NBVEdUQUdDVEFBQ1RDQUdHVFRBQ0FUR0dHR0FUR0FDQ0NDR0NHQUNUVEdHQVRUQUdBR1RDVENUVFRUR0dBQVRBQUdDQ1RHQUFUR0FUQ0NHQUdUQUdDQVRDVENBRyIKCiAgICBwb3NzaWJsZV9hID0gcG9zc2libGVfcHJvdGVpbl9zdHJpbmdzKHNtYWxsX2RhdGFzZXQpCiAgICBwb3NzaWJsZV9iID0gcG9zc2libGVfcHJvdGVpbl9zdHJpbmdzKHJldmVyc2VfY29tcGxlbWVudChzbWFsbF9kYXRhc2V0KSkKICAgIHByaW50ICJcbiIuam9pbihzZXQocG9zc2libGVfYSArIHBvc3NpYmxlX2IpKQ==