similarity_table = {'a': {'a': 2, 'g': -2, 'c': -2, 't': -2, '-': -1},
                    'g': {'a': -2, 'g': 2, 'c': -2, 't': -2, '-': -1},
                    'c': {'a': -2, 'g': -2, 'c': 2, 't': -2, '-': -1},
                    't': {'a': -2, 'g': -2, 'c': -2, 't': 2, '-': -1},
                    '-': {'a': -1, 'g': -1, 'c': -1, 't': -1, '-': 0}}


def similarity(table, a, b):
    if a in table and b in table[a]:
        return table[a][b]
    else:
        return 0


def optimal_alignment(code_a, code_b, array):
    i = len(code_a)
    j = len(code_b)

    alignment_a = ""
    alignment_b = ""

    while not (i == 0 and j == 0):
        value_both = array[i - 1][j - 1]
        value_a = array[i - 1][j]
        value_b = array[i][j - 1]

        max_value = max(value_both, value_a, value_b)
        if max_value == value_both:
            alignment_a = code_a[i - 1] + alignment_a
            alignment_b = code_b[j - 1] + alignment_b
            i -= 1
            j -= 1
        elif max_value == value_a:
            alignment_b = '-' + alignment_b
            alignment_a = code_a[i - 1] + alignment_a
            i -= 1
        else:
            alignment_a = '-' + alignment_a
            alignment_b = code_b[j - 1] + alignment_b
            j -= 1

    return alignment_a, alignment_b


def test(code_a, code_b):
    n = len(code_a) + 1
    m = len(code_b) + 1
    array = [[0 for j in range(m)] for i in range(n)]

    for i in range(1, n):
        array[i][0] = similarity(similarity_table, '-', code_a[i - 1]) + array[i - 1][0]

    for j in range(1, m):
        array[0][j] = similarity(similarity_table, code_b[j - 1], '-') + array[0][j - 1]

    for i in range(1, n):
        for j in range(1, m):
            array[i][j] = max(array[i - 1][j - 1] + similarity(similarity_table, code_a[i - 1], code_b[j - 1]),
                              array[i][j - 1] + similarity(similarity_table, '-', code_a[i - 1]),
                              array[i - 1][j] + similarity(similarity_table, code_b[j - 1], '-'))
    print array
    a, b = optimal_alignment(code_a, code_b, array)
    print a
    print b

test('tcagtcgatagtcgatcg', 'tctctggagtcgatctgg')