f1=open("acids.txt", "r") ## reading acids
ak=f1.readline()
f1.close()

bm=[] ## reading matrix
f1=open("blosum50.txt", "r")
for i in range(20):
    line=f1.readline()
    vc=line.split()
    bm.append(vc[:])
for i in range(20): ## integer matrix
    for j in range(20):
        bm[i][j]=int(bm[i][j])

x='PEW'
y='GALAPAWALA'

m=len(x)
n=len(y)

sm=[] ## score matrix
tmp=[]
for i in range(m+1):
    tmp.append(0)
for i in range(n+1):
    sm.append(tmp[:])

maxV = 0
maxC = (0, 0)

## rekurzija
for i in range(1,n+1):
    for j in range(1,m+1):
        bb=bm[ak.index(y[i-1])][ak.index(x[j-1])]
        sm[i][j] = max([sm[i-1][j] - 8, sm[i][j - 1] - 8, sm[i - 1][j - 1] + bb, 0])
        if sm[i][j] > maxV:
            maxV = sm[i][j]
            maxC = (i, j)

a1 = ""
a2 = ""

s = map(lambda r : "\t".join(r), [[str(e) for e in row] for row in sm])

print("\nMatrica:")
for r in s:
    print(r)

i = maxC[0]
j = maxC[1]

print("\nPoravnanje:\n")
while i > 0 or j > 0:

    if sm[i][j] == 0:
        break
    if i > 0 and j > 0 and sm[i][j] == sm[i - 1][j - 1] + bm[ak.index(y[i - 1])][ak.index(x[j - 1])]:
        a1 = x[j - 1] + a1
        a2 = y[i - 1] + a2
        i = i - 1
        j = j - 1
    elif i > 0 and sm[i][j] == sm[i - 1][j] - 8:
        a1 = "-" + a1
        a2 = y[i - 1] + a2
        i = i - 1
    else:
        a1 = x[j - 1] + a1
        a2 = "-" + a2
        j = j - 1

print(a1)
print(a2)