## Distance de Levenshtein : algorithme force brute

import numpy as np

n,p = 5,5
F = np.zeros((n+1,p+1),dtype = int)

for i in range(n+1) : # initialisation première colonne
    F[i,0] = 1

for j in range(p+1) : # initialisation première ligne
    F[0,j] = 1

for i in range(1,n+1) :
    for j in range(1,p+1) :
        F[i,j] = F[i-1,j-1] + F[i,j-1] + F[i-1,j]




## Distance de Levenshtein : version récursive naïve

def lev1(ch1,ch2) :
    n,p = len(ch1), len(ch2)
    if n == 0 :
        return p
    elif p == 0 :
        return n
    else :
        val1 = 1 + lev1(ch1[0:n-1],ch2)
        val2 = 1 + lev1(ch1,ch2[0:p-1])
        if ch1[n-1] == ch2[p-1] :
            val3 = lev1(ch1[0:n-1],ch2[0:p-1])
        else :
            val3 = 1 + lev1(ch1[0:n-1],ch2[0:p-1])
        minimum = min(val1,val2,val3)
        return minimum


## Distance de Levenshtein : version récursive avec mémoïsation

dico = {}

def lev2(ch1,ch2) :
    n,p = len(ch1), len(ch2)
    if (n,p) in dico.keys() :
        return dico[(n,p)]
    elif n == 0 :
        dico[(n,p)] = p
        return p
    elif p == 0 :
        dico[(n,p)] = n
        return n
    else :
        val1 = 1 + lev2(ch1[0:n-1],ch2)
        val2 = 1 + lev2(ch1,ch2[0:p-1])
        if ch1[n-1] == ch2[p-1] :
            val3 = lev2(ch1[0:n-1],ch2[0:p-1])
        else :
            val3 = 1 + lev2(ch1[0:n-1],ch2[0:p-1])
        minimum = min(val1,val2,val3)
        dico[(n,p)] = minimum
        return minimum

## Distance de Levenshtein : version récursive avec mémoïsation
## plus information supplémentaire

dico = {}

def lev2_modif(ch1,ch2) :
    n,p = len(ch1), len(ch2)
    if (n,p) in dico.keys() :
        return dico[(n,p)]
    elif n == 0 :
        dico[(n,p)] = (p,"Ins")
        return (p,"Ins")
    elif p == 0 :
        dico[(n,p)] = (n,"Supp")
        return (n,"Supp")
    else :
        val1 = 1 + lev2_modif(ch1[0:n-1],ch2)[0]
        val2 = 1 + lev2_modif(ch1,ch2[0:p-1])[0]
        if ch1[n-1] == ch2[p-1] :
            val3 = lev2_modif(ch1[0:n-1],ch2[0:p-1])[0]
        else :
            val3 = 1 + lev2_modif(ch1[0:n-1],ch2[0:p-1])[0]
        minimum = min(val1,val2,val3)
        if minimum == val1 :
            resultat = (val1,"Supp")
        elif minimum == val2 :
            resultat = (val2,"Ins")
        else :
            if ch1[n-1] == ch2[p-1] :
                resultat = (val3,"Rien")
            else :
                resultat = (val3,"Remp")

        dico[(n,p)] = resultat
        return resultat

## Distance de Levenshtein : construction de la solution

dico = {}

def construire(ch1,ch2) :
    n,p = len(ch1), len(ch2)
    if n == 0 :
        return p*["Ins"]
    elif p == 0 :
        return n*["Supp"]
    else :
        mini, ch = lev2_modif(ch1,ch2)
        if ch == "Ins" :
            return ["Ins"] + construire(ch1,ch2[0:p-1])
        elif ch == "Supp" :
            return ["Supp"] + construire(ch1[0:n-1],ch2)
        elif ch == "Remp" :
            return ["Remp"] + construire(ch1[0:n-1],ch2[0:p-1])
        else :
            return ["Rien"] + construire(ch1[0:n-1],ch2[0:p-1])


def presentation(ch1,ch2) :
    bilan = {}
    L = construire(ch1,ch2)
    for ch in L :
        if ch != "Rien" :
            if ch in bilan.keys() :
                bilan[ch] += 1
            else :
                bilan[ch] = 1
    return bilan


















## Distance de Levenshtein : version itérative avec matrice

# import numpy as np
#
#
# def levenshtein1(ch1,ch2) :
#     n,p = len(ch1), len(ch2)
#
#     if n == 0 :
#         return p
#     elif p == 0 :
#         return n
#
#     else :
#         d = np.zeros( (n+1,p+1), dtype = int)
#         for i in range(n+1) :
#             d[i,0] = i
#         for j in range(p+1) :
#             d[0,j] = j
#         for i in range(1,n+1) :
#             for j in range(1,p+1) :
#                 if ch1[i-1] == ch2[j-1] :
#                     val = d[i-1,j-1]
#                 else :
#                     val = 1 + d[i-1,j-1]
#                 minimum = min(1+d[i-1,j], 1+d[i,j-1], val)
#                 d[i,j] = minimum
#         print(d)
#         return d[n,p]