import numpy as np

#approche naive
def distanceEdition_rec(a, b):
    if len(a) == 0 or len(b) == 0:
        return max(len(a), len(b))
    elif a[0] == b[0]:
        return distanceEdition_rec(a[1:], b[1:])
    else:
        return 1 + min(distanceEdition_rec(a[1:], b), distanceEdition_rec(a[1:], b[1:]), distanceEdition_rec(a, b[1:]))

print ( distanceEdition_rec( "niche", "chien"))
print ( distanceEdition_rec( "pirate", "pilote"))
# approche programmation dynamique - iterative ascendante
# Calcul de la distance d'édition  avec la matrice d'edition
def distanceEdition_PD_ite(ch1, ch2):  
    lg1, lg2 = len(ch1), len(ch2)
    mat_edition    = np.zeros((lg1+1,lg2+1), dtype=int)
    # Constitution de la 1e colonne
    for i in range(0, lg1+1):
        mat_edition[i,0] = i 
    # Constitution de la 1e ligne
    for j in range(0, lg2+1):
        mat_edition[0,j] = j 

    # remplissage du reste de la matrice
    for i in range( 1, lg1+1 ):
        for j in range( 1, lg2+1 ):
            if ch1[i-1] == ch2[j-1]:
                mat_edition[i,j] = mat_edition[i-1,j-1]
            else:
                mat_edition[i,j] = 1+ min( mat_edition[i-1,j-1] , mat_edition[i-1,j] , mat_edition[i,j-1]  )
        # mat_edition[lg1,lg2] : correspond à la distance d'edition   
        print(mat_edition)     
    return mat_edition[ lg1,lg2 ]#, mat_edition  

def distanceEdition_PD_rec(a, b, mem):
    if (a, b) in mem:
        return mem[(a, b)]  #  already computed !
    else:
        if len(a) == 0 or len(b) == 0:
            mem[(a, b)] = max(len(a), len(b))
        elif a[0] == b[0]:
            mem[(a, b)] = distanceEdition_PD_rec(a[1:], b[1:], mem)
        else:
            mem[(a, b)] = 1 + min(distanceEdition_PD_rec(a[1:], b, mem), distanceEdition_PD_rec(a[1:], b[1:], mem), distanceEdition_PD_rec(a, b[1:], mem))
        return mem[(a, b)]

#reconstitution des transformations sur les 2 mots
def Alignement(A, B, mat_edition):
    i,j = np.shape(mat_edition)
    i=i-1
    j=j-1
    Afinal ='' 
    Bfinal = ''
    while  (i > 0) and (j > 0) :   
        if (mat_edition[i,j] == mat_edition[i-1,j-1]) and (A[i-1] == B[j-1]) :# A et B décalage
            print("1" , i, "-",j)
            Afinal = A[i-1]+Afinal
            Bfinal = A[i-1]+Bfinal
            i = i-1
            j = j-1
        elif mat_edition[i,j] == mat_edition[i-1,j-1] + 1 : #cas remplacement
            Afinal = A[i-1]+Afinal
            Bfinal = B[j-1]+Bfinal
            i = i-1
            j = j-1
        elif mat_edition[i,j] == mat_edition[i-1,j] + 1 : # cas suppression
            Afinal =  A[i-1] + Afinal
            Bfinal = '-' + Bfinal
            i = i-1 
        elif mat_edition[i,j] == mat_edition[i,j-1] + 1 : # cas insertion
            print("4",i, "-",j)
            Afinal = '-' + Afinal
            if( i <len(B)):
                Bfinal = B[i] + Bfinal
            else: # cas oerniere lettre du 1er mot ne correspond pas à celle du 2e 
                Bfinal = B[i-1] + Bfinal
            j = j - 1
    while i > 0 :
        Afinal = A[i-1] + Afinal
        Bfinal = ' - ' + Bfinal
        i=i-1
    while j > 0 :
        Bfinal = B[i-1] + Bfinal
        Afinal = '-' + Afinal
        j=j-1
    return Afinal, Bfinal

mat = np.array([[0,1,2,3,4,5], [1,1,2,2,3,4], [2,2,2,3,2,3], [3,3,2,3,3,3], [4,4,3,3,4,3], [5,4,4,4,4,4]])
print( Alignement("chien", "niche", mat))
"""
if __name__ == "__main__":
    words = [("mardi", "mercredi"), ("chien", "niche"), ("AGATGC", "AGTATCT"), ("Levenshtein", "Lavenshtein"),
             ("sitting", "kitten"), ('mots', 'mois'), ('janvier', 'février'), ('aminci', 'machine'),
             ('aviron', 'avion'),
             ('courir', 'mourir'), ('mourir', 'mourrir'), ('courir', 'partir'), ('adroit', 'gauche'),
             ('liens', 'links')]
    for a, b in words:
            ite = distanceEdition_PD_ite(a, b)  # [len(a), len(b)]
            mem = distanceEdition_PD_rec(a, b, {})
            print(f"{a} --> {b} :  Bottom/Up --> {ite}, memoisation --> {mem}")
            assert ite == mem, f"Different results --< {a} vs {b}"
"""