## question 3

D={}

def distm(a:str,b:str)->int:
    '''Calcule la distance de Levenshtein entre a et b
    par mémoïsation, les clés du dictionnaire étant des ch de KR
    entrée : 2 ch de caractères
    sotie : entier'''

    if (a,b)in D:
        return D[(a,b)]

    if len(a)==0:
        D[(a,b)]=len(b)
        return len(b)
    elif len(b)==0:
        D[(a,b)]=len(a)
        return len(a)
    else:
        if a[-1]!=b[-1]:
            result= min(distm(a[:-1],b),distm(a,b[:-1]),distm(a[:-1],b[:-1]))+1
        else:
            result= min(distm(a[:-1],b)+1,distm(a,b[:-1])+1,distm(a[:-1],b[:-1]))
        D[(a,b)]=result
        return result

print(distm("NICHER", "CHIENS")) # rép : 5

'''' attention à ne traiter qu'un exemple.
En effet, en créant deux exemples consécutifs,
 le dictionnaire D ne serait pas réinitialiser'''


## puis au sein d'une seule fonction autonome

def dist_memo(a:str,b:str)->int:
    D={}
    def distm(a:str,b:str)->int:
        '''Calcule la distance de Levenshtein entre a et b
        par mémoïsation
        entrée : 2 ch de caractères
        sotie : entier'''

        if (a,b)in D:
            return D[(a,b)]

        if len(a)==0:
            D[(a,b)]=len(b)
            return len(b)
        elif len(b)==0:
            D[(a,b)]=len(a)
            return len(a)
        else:
            if a[-1]!=b[-1]:
                result= min(distm(a[:-1],b),distm(a,b[:-1]),distm(a[:-1],b[:-1]))+1
            else:
                result= min(distm(a[:-1],b)+1,distm(a,b[:-1])+1,distm(a[:-1],b[:-1]))
            D[(a,b)]=result
            return result

    return distm(a,b)

print(dist_memo("NICHER","CHIENS")) # rép : 5
print(dist_memo("Mémoïsation", "Calcul de bas en haut")) # rép : 19


## créons la matrice des d(i,j) sur l'exemple "NICHER", "CHIENS"

a,b="NICHE", "CHIENS"
D={}
distm(a,b)
print(D)
import numpy as np

mat=np.zeros((len(a)+1,len(b)+1))
for i in range(len(a)+1):
    for j in range(len(b)+1):
        mat[i,j]=D[(a[:i],b[:j])]
print(mat)



## question 3 version 2

def dist_memo2(a:str,b:str)->int:
    d={}
    n=len(a)
    m=len(b)
    def distm2(i,j)->int:
        '''Calcule la distance de Levenshtein entre a et b
        par mémoïsation, les clés du dictionnaire étant des entiers
        entrée : 2 entiers
        sotie : entier'''

        if (i,j)in d:
            return d[(i,j)]

        if i==0:
            d[(i,j)]=j

        elif j==0:
            d[(i,j)]=i
        else:
            if a[i-1]!=b[j-1]:
                result= min(distm2(i-1,j),distm2(i,j-1),distm2(i-1,j-1))+1
            else:
                result= min(distm2(i-1,j)+1,distm2(i,j-1)+1,distm2(i-1,j-1))
            d[(i,j)]=result
        return d[(i,j)]

    return distm2(n,m)

print(dist_memo2("NICHER","CHIENS")) # rép : 5
print(dist_memo2("Mémoïsation", "Calcul de bas en haut")) # rép : 19




## question 4

def dist_bottom_up(a:str,b:str)->int:
    '''Calcule la distance de Levenshtein entre a et b
    en procédant de bas en haut
    entrée : 2 ch de caractères
    sotie : entier'''
    d={}
    for i in range(len(a)+1):
        d[(i,0)]=i
    for j in range(len(b)+1):
        d[(0,j)]=j

    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            if a[i-1]!=b[j-1]:  # attention à l'indice, a[i-1] est bien
                                # le i^e caractère de la chaine a
                d[(i,j)]=min(d[(i-1,j)],d[(i,j-1)],d[(i-1,j-1)])+1
            else:
                d[(i,j)]=min(d[(i-1,j)]+1,d[(i,j-1)]+1,d[(i-1,j-1)])

    return d[(len(a),len(b))]


print(dist_bottom_up("NICHER", "CHIENS")) # ok

print(dist_bottom_up("Mémoïsation", "Calcul de bas en haut")) # ok