#EXERCICE 1

# Question 1

# Il y a i opérations (suppressions) à faire pour passer d'une chaine quelconque de longueur i à une chaine vide.
# D[i][0] = i
# Il y a j opérations (insertions) à faire pour passer d'une chaine vide à une chaine quelconque de longueur j.
# D[0][j] = j

# Question 2

# D[n][p] est la distance d'édition entre les deux mots considérés.

# Question 3
# Dans le cas où les dernières lettres sont identiques

# D[i][j] = D[i-1][j-1]

# Question 4
# Dans le cas où les dernières lettres sont différentes

# Si on rajoute la dernière lettre de mot2[:j]
# D[i][j] = D[i][j-1] + 1

# Si on supprime la dernière lettre de mot1[:i]
# D[i][j] = D[i-1][j] + 1

# Si on modifie la dernière lettre de mot1[:i] pour qu'elle vaille la dernière lettre de mot2[:j]
# D[i][j] = D[i-1][j-1] + 1

# Une formule valable dans ces trois cas est :
# D[i][j] = min( D[i-1][j-1], D[i-1][j], D[i][j-1] ) + 1

# Question 5

def distance(mot1,mot2):
    """renvoie la distance de Levenshtein entre deux chaînes de caractères"""
    n,p = len(mot1),len(mot2)
    D = [[0 for j in range(p+1)] for i in range(n+1)]
    for i in range(0,n+1): #on rentre la premiere colonne
        D[i][0] = i
    for j in range(0,p+1): #on rentre la premiere ligne
        D[0][j] = j
    for i in range(1,n+1):
        for j in range(1,p+1):
            if mot1[i-1] == mot2[j-1]:
                D[i][j] = D[i-1][j-1]
            else:
                D[i][j] = min(D[i-1][j-1],
                            D[i-1][j],
                            D[i][j-1]) + 1
    return D[n][p]

# Question 6

print("La distance Sarah -> Natacha vaut :", distance("Sarah","Natacha"))
print("La distance informatique -> affirmative vaut :", distance("informatique","affirmative"))

# Question 7

# Complexité spatiale en O(n*p) (taille de D)
# Complexité temporelle en O(n*p) : deux boucles imbriquées de longueurs n et p, chaque itération en O(1) 

#%%

# Question 8

f = open("ListeMotsFrancais.txt", "r")
Liste = f.readlines()  # on stocke dans une liste les lignes du fichier (1 ligne = 1 mot + 1 retour à la ligne \n) 
f.close()
Liste = [mot[0:len(mot)-1] for mot in Liste] # On retire le \n à la fin de chaque ligne

def ListeMotsPlusProche(maux):
    """Renvoie la liste des mots les plus proches de maux parmi les mots du dictionnaire"""
    L = [] # liste pour stocker les mots les plus proches
    m = len(maux) # distance au mot le plus proche, initialisée par la distance entre "" et maux
    for mot in Liste: # on parcourt la liste des mots français
        d = distance(maux,mot) # on calcule la distance
        if d < m: # on a trouvé une distance plus petite
            m,L = d,[mot]  # on met à jour la distance minimale et la liste des mots à cette distance
        elif d == m: # on a trouvé un autre mot dont la distance vaut aussi min
            L.append(mot) # on ajoute mot dans la liste des mots à cette distance
    return L

# Question 9

maux="imffaurmathiqe"
import time as time
tic=time.time()
L=ListeMotsPlusProche(maux)
tac=time.time()#mesure du temps
print("En",tac-tic,"secondes, on propose",L,"comme correction de",maux)


 #%%
#EXERCICE 3

D={} #dictionnaire de mémoïsation

def dist(mot1,mot2):
    n,p=len(mot1),len(mot2)
    if (mot1,mot2) not in D:
        if n==0 or p==0: #l’un des mots est vide
            D[mot1,mot2]=max(len(mot2),len(mot1))
        elif mot1[n-1]==mot2[p-1]: #les mots finissent par la même lettre
            D[mot1,mot2]=dist(mot1[0:n-1],mot2[0:p-1])
        else:
            D[mot1,mot2]=min(dist(mot1[0:n-1],mot2[0:p-1]),
                             dist(mot1,mot2[0:p-1]),
                             dist(mot1[0:n-1],mot2)) + 1
    return D[mot1,mot2]

print("La distance Sarah -> Natacha vaut :", dist("Sarah","Natacha"))
print("La distance informatique -> affirmative vaut :", dist("informatique","affirmative"))

 #%%
#EXERCICE 4

# Question 1

def distance2(mot1,mot2):
    """renvoie le tableau des distances de Levenshtein entre deux chaînes de caractères"""
    n,p = len(mot1),len(mot2)
    D=[[0 for j in range(p+1)] for i in range(n+1)]
    for i in range(0,n+1): #on rentre la premiere colonne
        D[i][0] = i
    for j in range(0,p+1): #on rentre la premiere ligne
        D[0][j] = j
    for i in range(1,n+1):
        for j in range(1,p+1):
            if mot1[i-1] == mot2[j-1]:
                D[i][j] = D[i-1][j-1]
            else:
                D[i][j] = min(D[i-1][j-1],D[i-1][j],D[i][j-1]) + 1
    return D

# Question 2

# Si mot1 est vide on renvoie la liste des tranches de mot2 :  [ mot2[:k] for k in range(p+1) ]
# Si mot2 est vide on renvoie la liste des tranches mot1 :  [ mot1[:k] for k in range(n+1) ]

# Question 3

# Si mot1 et mot2 se finissent par la même lettre on renvoie :
# [ k + mot1[-1] for k in Chemin(mot1[:n-1],mot2[:p-1])]

# Question 4

# Si mot1 et mot2 finissent par une lettre différente on renvoie :

    # Si D[n][p] == D[n-1][p-1]+1: (modification du dernier caractère)
    # C=Chemin(mot1[:n-1],mot2[:p-1])
    # On renvoie [k+mot1[n-1] for k in C]+[mot2]

    # Si D[n][p]==D[n-1][p]+1: (suppression du dernier caractère de mot1)
    # On renvoie [mot1]+Chemin(mot1[:n-1],mot2)

    # Si D[n][p]==D[n][p-1]+1: (rajout du dernier caractère)
    # On renvoie Chemin(mot1,mot2[:p-1])+[mot2]

# Question 5

def Chemin(mot1,mot2):
    n,p = len(mot1),len(mot2) 
    if mot1 == "":
        return [mot2[:k] for k in range(p+1)] #["",mot2[:1],mot2[:2],...., mot2]
    if mot2 == "":
        return [mot1[k:] for k in range(n+1)]
    if mot1[n-1] == mot2[p-1]:
        C = Chemin(mot1[:n-1],mot2[:p-1])
        return [k+mot1[n-1] for k in C]
    if D[n][p] == D[n-1][p-1]+1:  # modification du dernier caractère:
        C = Chemin(mot1[:n-1],mot2[:p-1])
        return [k+mot1[n-1] for k in C]+[mot2]
    if D[n][p] == D[n-1][p]+1:   # suppression du dernier caractère de mot1
        return [mot1]+Chemin(mot1[:n-1],mot2)
    if D[n][p] == D[n][p-1]+1:  # ajout du dernier caractère:
        return Chemin(mot1,mot2[:p-1])+[mot2]

mot1="informatique"
mot2="affirmative"
D=distance2(mot1,mot2)
print(Chemin(mot1,mot2))

mot1="Sarah"
mot2="Natacha"
D=distance2(mot1,mot2)
print(Chemin(mot1,mot2))

 #%%
#EXERCICE 4

#Voir corrigé du TP précédent