import numpy as np

# Sekwencje i ich dlugosci

sekw1 = list('GATACTA')

# sekw1 = list('TTTTACTGAA')

sekw2 = list('GATTACCA')

# sekw2 = list('TTACTAGGAA')

sekw1_len = len(sekw1)

sekw2_len = len(sekw2)

# kara

kara = 1

#przerwa

przerwa = 2

# Macierz scoringowa

F = np.zeros((sekw2_len + 1, sekw1_len + 1), dtype=int)

# Slownik porownan

S = {'GG': 1, 'GA': -1, 'GT': -1, 'GC': -1,
     'CG': -1, 'CA': -1, 'CT': -1, 'CC': 1,
     'TG': -1, 'TA': -1, 'TT': 1, 'TC': -1,
     'AG': -1, 'AA': 1, 'AT': -1, 'AC': -1}

#wypelnianie 1 wiersza
for j in range(0, F.shape[1]):
    F[0][j] = -j

#wypelnianie 1 kolumny
for i in range(0, F.shape[0]):
    F[i][0] = -i

#wypelnianie macierzy
for i in range(1, F.shape[0]):
    for j in range(1, F.shape[1]):

        literka_gura = sekw1[j - 1]
        literka_bok = sekw2[i - 1]
        literka = literka_gura + literka_bok

        pszekontna = F[i - 1][j - 1] + S[literka]
        gura = F[i - 1][j] - kara
        dul = F[i][j - 1] - kara

        F[i][j] = max(pszekontna, gura, dul)

print(F)

#sekwencje wynikowe
sekw1_wynikowa = list()
sekw2_wynikowa = list()

#traceback
i = F.shape[0] - 1
j = F.shape[1] - 1

while i != 0 and j != 0:
        literka_gura = sekw1[j - 1]
        literka_bok = sekw2[i - 1]
        literka = literka_gura + literka_bok

        pszekontna = F[i - 1][j - 1]
        gura = F[i - 1][j] - kara
        dul = F[i][j - 1] - kara

        F[i][j] = max(pszekontna, gura, dul)

        if F[i][j] == pszekontna:
            i = i - 1
            j = j - 1
            sekw1_wynikowa.append(literka_gura)
            sekw2_wynikowa.append(literka_bok)
        elif F[i][j] == gura:
            i = i - 1
            sekw1_wynikowa.append("-")
            sekw2_wynikowa.append(literka_bok)
        else:
            j = j - 1
            sekw1_wynikowa.append("-")
            sekw2_wynikowa.append(literka_bok)

print()

# print(sekw1_2_wynikowa)
tt = 0
sekw1_2_wynikowa = list()
for i in reversed(sekw1_wynikowa):
    sekw1_2_wynikowa.append(i)
    tt = tt + 1

print("".join(sekw1_2_wynikowa))

# print(sekw2_2_wynikowa)
tt = 0
sekw2_2_wynikowa = list()
for i in reversed(sekw2_wynikowa):
    sekw2_2_wynikowa.append(i)
    tt = tt + 1

print("".join(sekw2_2_wynikowa))