#!/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] = ...
    for j in range(1,n2+1):
        tabDist[0][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] = ....
            else :
                a,b,c = tabDist[i-1][j-1],tabDist[i-1][j],tabDist[i][j-1]
                tabDist[i][j] = ...
    return ....

#test
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 levenProgDyn2(mot1,mot2):
    # A compléter


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) == ...:
            ...
        elif (i_new , j_new) == ...:
            ....
        i , j = ... , ...
    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 ...
        elif j == 0:
            return ...
        elif mot1[i-1] == mot2[j-1]:
            return ...
        else :
            return ...
    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'))