import copy as cp
import re

alph = list()
blosum = list()
mat = list()
tb = list()
T = 40
_seq = ""
_dom = ""


with open("blosum62.txt","r") as blofile:
    alph = re.findall("\w",blofile.readline())
    for line in blofile.readlines():
        blosum.append(re.findall("\-?\d+", line))
gapval = int(blosum[len(alph)][len(alph)-1])

def nws(s): #ez csúnya. nagyon.
    ns = ""
    for i in s:
        if i == '\r' or i == '\n':
            pass
        else:
            ns+=i
    return ns

def makemat(seq,dom,mat):
    zeroes = list()
    for i in range(len(seq)+1):
        zeroes.append(0)
    for j in range(len(dom)+1):
        mat.append(cp.deepcopy(zeroes))

def printmat(mat):
    for i in range(len(mat)):
        print mat[i]

def fillval(i,j,s,d): #sor,oszlop,seq,dom
    return max(mat[i-1][j-1]+int(blosum[s][d]),mat[i-1][j]+int(gapval),mat[i][j-1]+int(gapval),max(mat[0][j-1],mat[i][j-1]-T))

def fill_line(i,j):
    return max(mat[0][j-1],mat[i][j-1]-T)

def fillmat(seq,dom):
    for i in range(1,len(mat)): #sor
        for j in range(1,len(mat[i])): #oszlop
            mat[i][j] = fillval(i,j,alph.index(seq[j-1]),alph.index(dom[i-1]))

def traceback(i,j):
    s = ""
    dd = ""
    while i>0 and j>0:
        l = mat[i][j-1]
        u = mat[i-1][j]
        d = mat[i-1][j-1]
        if max(l,u,d) == l:
            s = _seq[j-1] + s
            dd = '-' + dd
            j = j-1
            tb[i][j] = 1
        elif max(l,u,d) == u:

            s = _seq[j-1] + s
            dd = '.' + dd
            i = i-1
            tb[i][j] = 1
        elif max(l,u,d) == d:

            s = _seq[j-1] + s
            dd = _dom[i-1] + dd
            i = i-1
            j = j-1
            tb[i][j] = 1
    print s
    print dd
    print "////////////////////////////"


def getmax(j):
    for i in range(len(mat)):
        mval = max(mat[0][j-1],mat[i][j-1]-T)
    return mval


def findmax(j,val):
    for o in range(j,0,-1):
        for s in range(len(mat)):
            if mat[s][o-1] == val+T:
                return [s,o]
    mval = [0,0,0]
    for i in range(len(mat)):
        for j in range(len(mat[i])):
            if mval[0]<mat[i][j]:
                mval = [mat[i][j],i,j]
    return [mval[1],mval[2]]



def tbproper(coords,dom):
    while coords[0]>0 and coords[1]>0:
        l = mat[coords[0]][coords[1]-1]
        u = mat[coords[0]-1][coords[1]]
        d = mat[coords[0]-1][coords[1]-1]
        if max(l,u,d) == l:
            coords[1] = coords[1]-1
            dom = '-' + dom
            tb[coords[0]][coords[1]] = 1 #jobbról jött
        elif max(l,u,d) == u:
            coords[0] = coords[0]-1
            tb[coords[0]][coords[1]] = 2
            dom = '.' + dom #lentről
        elif max(l,u,d) == d:
            coords[0] = coords[0]-1
            coords[1] = coords[1]-1
            tb[coords[0]][coords[1]] = 3
            dom = _dom[coords[0]]+dom #átlósan
    if coords[0] ==0 and coords[1]!=0: #vagyis csak a tetejét értük el
        print "called again at " + str(coords[0]) +'-'+ str(coords[1])
        tbproper(findmax(coords[1],getmax(coords[1])),dom) #for the lulz
    return dom

def move(crd,dom):
    _outdom = ""
    i = crd[0]
    j = crd[1]
    while i<len(mat)-1 and j<len(mat[i])-1 and tb[i][j]!=0:
        print [i,j]
        if tb[i][j] == 1:
            print "j"
            j = j+1
            _outdom = '-' + _outdom
        if tb[i][j] == 2:
            print "l"
            i = i+1
            _outdom = '.' + _outdom
        if tb[i][j] == 3:
            print "á"
            _outdom = dom[i-1] + _outdom
            i = i + 1
            j = j + 1
    print _outdom

def reconstr(dom):
    for i in range(len(mat)):
        if tb[i][0] != 0:
            print "let's do this shit"
            move([i,0],dom)


#INTMÉJN
with open("q2tay7.fasta") as seqfile, open("q2tay7_domain.fasta") as domfile:
    seqfile.readline()
    domfile.readline()
    _seq = nws(seqfile.read())
    _dom = nws(domfile.read())
#    _seq = "HEAGAWGHEE"
#    _dom = "PAWHEAE"

makemat(_seq, _dom,mat)
makemat(_seq, _dom,tb)
fillmat(_seq,_dom)
print getmax(len(mat[0]))
_crd = findmax(len(mat[0]),getmax(len(mat[0])))
print _crd
_od = ""
print _seq
#print tbproper(_crd,_od)
traceback(_crd[0],_crd[1])
#printmat(tb)
#reconstr(_od)