#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Nov  5 23:38:33 2024

@author: vincentleprince
"""



def levenProgDyn(mot1,mot2):
    n1 , n2 = len(mot1),len(mot2)
    tabDist = [[0 for j in range(n2+1)] for i in range(n1+1)]
    for i in range(1,n1+1):
        tabDist[i][0] = i
    for j in range(1,n2+1):
        tabDist[0][j] = j
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            if mot1[i-1] == mot2[j-1]:
                tabDist[i][j] = tabDist[i-1][j-1]
            else :
                a,b,c = tabDist[i-1][j-1],tabDist[i-1][j],tabDist[i][j-1]
                tabDist[i][j] = 1 + min(a,b,c)
    return tabDist[n1][n2]

print(levenProgDyn('niches','chien'))


def levenProgDyn2(mot1,mot2):
    n1 , n2 = len(mot1),len(mot2)
    tabDist = [[[0 ,None] for j in range(n2+1)] for i in range(n1+1)]
    for i in range(1,n1+1):
        tabDist[i][0] = [i ,(i-1,0)]
    for j in range(1,n2+1):
        tabDist[0][j] = [j,(0,j-1)]
    for i in range(1,n1+1):
        for j in range(1,n2+1):
            if mot1[i-1] == mot2[j-1]:
                tabDist[i][j] = [tabDist[i-1][j-1][0] , (i-1,j-1)]
            else :
                a,b,c = tabDist[i-1][j-1][0],tabDist[i-1][j][0],tabDist[i][j-1][0]
                if a<b and a<c:
                    tabDist[i][j] = [1 + a , (i-1,j-1)]
                elif b<a and b<c:
                    tabDist[i][j] = [1 + b , (i-1,j)]
                else :
                    tabDist[i][j] = [1 + c , (i,j-1)]
                    
    return tabDist

print(levenProgDyn2('niches','chien'))


def reconstructionLeven(mot1,mot2,tabDist):
    n1 , n2 = len(mot1),len(mot2)
    i , j , res = n1 , n2 , []
    while (i,j) != (0,0):
        i_new , j_new = tabDist[i][j][1]
        if i!=0 and j!=0 and mot1[i-1] == mot2[j-1]:
            res.append(mot1[i-1]+'='+mot2[j-1])
        elif (i_new , j_new) == (i-1,j-1):
            res.append("substitution de "+mot1[i-1]+" par "+ mot2[j-1])
        elif (i_new , j_new) == (i-1,j):
            res.append("suppression de "+mot1[i-1])
        elif (i_new , j_new) == (i,j-1):
            res.append("insertion de "+mot2[j-1])
        i , j = i_new , j_new
    return res
    
#test
tabDist = levenProgDyn2('niches','chien')
print(reconstructionLeven('niches','chien',tabDist))


def levenRecNaive(mot1,mot2):
    n1 , n2 = len(mot1),len(mot2)
    def aux(i,j):
        if i == 0:
            return j
        elif j == 0:
            return i
        elif mot1[i-1] == mot2[j-1]:
            return aux(i-1,j-1)
        else :
            return 1+min(aux(i-1,j-1),aux(i,j-1),aux(i-1,j))
    return aux(n1,n2)

print(levenRecNaive('niches','chien'))
    

def levenMemo(mot1,mot2):
    n1 , n2 = len(mot1),len(mot2)
    dico = {}
    def aux(i,j):
        # cette fonction "remplit" la case (i,j) 
        #(si elle ne l'est pas déjà)
        #et renvoie sa valeur
        if (i,j) not in dico:
            if i == 0:
                dico[(i,j)] = j
            elif j == 0:
                dico[(i,j)] = i
            else :
                if mot1[i-1]==mot2[j-1]:
                    dico[(i,j)] = aux(i-1,j-1)
                else :
                    a , b , c = aux(i-1,j-1) , aux(i,j-1)  , aux(i-1,j) 
                    dico[(i,j)] = 1 + min(a,b,c)
        return dico[(i,j)]
    return aux(n1,n2)

print(levenMemo('niches','chien'))