#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Mar  9 16:45:33 2021

@author: adomps
"""

#https://fr.wikipedia.org/wiki/Distance_de_Levenshtein
#http://www.jeux-et-mathematiques.davalan.org/lang/algo/lev/  # Très pratique pour des essais !
#https://www.codeflow.site/fr/article/java-levenshtein-distance
#http://perso.eleves.ens-rennes.fr/~mruffini/Files/Other/levenstein.pdf
#http://www-igm.univ-mlv.fr/~lecroq/cours/distances.pdf
#https://who.rocq.inria.fr/Simon.Cruanes/enseignement/programmation_dynamique.pdf

# Livre Algorithmique du texte de M. Crochemore (pages numérisées dans le dossier
# programmation_dynamique/documents
# Un peu trop théorique !
# Ce livre introduit le concept d'alignement qui permet de comparer
# les deux chaines dont on calcule la distance, mais j'ai laissé tomber.
# Quand on efface une lettre x de X, on écrit en colonne (x, _). Quand
# on insère un lettre y de Y, on écrit en colonne (_, y). Quand on ne modifie
# rien, on écrit (x, y = x). Quand on remplace, on écrit (x, y).
import numpy as np


def lev_montant(X, Y) :
    ''' Calcule et renvoie la distance de Levenshtein entre
    X et Y, calculée par programmation dynamique. '''
    m = len(X)
    n = len(Y)
    T = np.zeros((m+1, n+1), 'uint8') 
    T[1:, 0] = [i for i in range(1, m+1)] # le coin [0, 0] est déjà à 0
    T[0, 1:] = [j for j in range(1, n+1)]

    for i in range(1, m+1) :
        for j in range(1, n+1) :
            if X[i-1] == Y[j-1] :
                T[i, j] = T[i-1, j-1] 
            else :
                d0 = T[i-1, j-1]
                d1 = T[i-1, j]
                d2 = T[i, j-1]
                T[i, j] = min(d0, d1, d2) + 1
    #print(T)
    return T[m, n]
    
print(lev_montant('niche', 'chiens'))
print(lev_montant('tortue', 'reptile'))
print(lev_montant('voiture', 'betterave'))
print(lev_montant('chimie', 'physique'))
print(lev_montant('physique', 'mystique'))


# # Version récursive naïve sans mémoïsation, avec par conséquent
# # des appels redondants.    
# def lev_descendant_naïf(X, Y) :

#     if X == '' : 
#         return len(Y)
#     if Y == '' :
#         return len(X)
    
#     x, y = X[-1], Y[-1]
    
#     if x == y :
#         return lev_descendant_naïf(X[:-1], Y[:-1])
#     else :
#         dE = lev_descendant_naïf(X[:-1], Y)
#         dI = lev_descendant_naïf(X, Y[:-1])
#         dR = lev_descendant_naïf(X[:-1], Y[:-1])
#         return min(dE, dI, dR) + 1
        

# Version récursive avec mémoïsation dans le tableau T.
# Il faudra initailiser $T$, avec des -1 partout, valeur
# conventionnelle pour dire que le calcul reste à faire.
def lev_descendant(X, Y, T) :
    #print(X, Y)
    m, n = len(X), len(Y)
    # Si le calcul a déjà été fait
    if T[m, n] > -1 :
        return T[m, n]
    # Cas terminaux triviaux, mais je les traite dans l'initialisation
#    if X == '' : 
#        T[m, n] = n        
#        return T[m, n]        
#    if Y == '' :
#        T[m, n] = m
#        return T[m, n]        
    
    # Sinon, appels récursifs

    if X[-1] == Y[-1] :
         T[m, n] = lev_descendant(X[:-1], Y[:-1], T)
    else :
        dE = lev_descendant(X[:-1], Y, T)
        dI = lev_descendant(X, Y[:-1], T)
        dR = lev_descendant(X[:-1], Y[:-1], T)
        T[m, n] = min(dE, dI, dR) + 1            
    return T[m, n]


# Application
X, Y = 'tortue', 'reptile'
T = - np.ones((7, 8), 'int')    
T[0,:] = [j for j in range(8)]
T[:,0] = [ i for i in range(7)]  
print(T)
lev_descendant(X, Y, T)
print(T)


# Fonction qui initialise le tableau T et fait le boulot récursif.
def applique_lev_descendant(X, Y):
    m, n = len(X), len(Y)
    T = - np.ones((m+1, n+1), 'int')    
    T[0,:] = [j for j in range(n+1)]
    T[:,0] = [ i for i in range(m+1)]    
    return lev_descendant(X, Y, T)

print(applique_lev_descendant('niche', 'chiens'))
print(applique_lev_descendant('tortue', 'reptile'))
print(applique_lev_descendant('voiture', 'betterave'))
print(applique_lev_descendant('chimie', 'physique'))
print(applique_lev_descendant('physique', 'mystique'))


#### Récursif avec mémoïsation par dictionnaire D
def lev_descendant_dico(X, Y, D) :
    #print(X, Y)
    m, n = len(X), len(Y)
    
    # Si le calcul a déjà été fait
    if (m, n) in D : 
        return D[m, n]
    
    # Cas terminaux triviaux
    if X == '' : 
        D[m, n] = len(Y)        
        return D[m, n]        
    if Y == '' :
        D[m, n] = len(X)
        return D[m, n]        
    
    # Sinon, appels récursifs
    if X[-1] == Y[-1] :
         D[m, n] = lev_descendant_dico(X[:-1], Y[:-1], D)
    else :
        dE = lev_descendant_dico(X[:-1], Y, D)
        dI = lev_descendant_dico(X, Y[:-1], D)
        dR = lev_descendant_dico(X[:-1], Y[:-1], D)
        D[m, n] = min(dE, dI, dR) + 1            
    return D[m, n]

def applique_lev_descendant_dico(X, Y) :
    D = {}
    rep = lev_descendant_dico(X, Y, D)
    #print(D)
    return rep


print(applique_lev_descendant_dico('niche', 'chiens'))
print(applique_lev_descendant_dico('tortue', 'reptile'))
print(applique_lev_descendant_dico('voiture', 'betterave'))
print(applique_lev_descendant_dico('chimie', 'physique'))
print(applique_lev_descendant_dico('physique', 'mystique'))



def min_de_trois(a, b, c) :
    ''' Renvoie la plus petite des trois valeurs a, b, c, et l'indice 0, 1 ou 2
    de cette valeur. En cas d'égalité, on choisit la première rencontrée.'''
    if a <= b :
        if a <= c :
            return a, 0
        else : 
            return c, 2
    else :
        if b <= c :
            return b, 1
        else :
            return c, 2


# Variable globale
symboles = ('I', 'E', 'R', '*') # R : Remplacer

def lev_montant_avec_action(X, Y) :
    m = len(X)
    n = len(Y)
    T = np.zeros((m+1, n+1), 'uint8')
    T[1:, 0] = [i for i in range(1, m+1)]    
    T[0, 1:] = [j for j in range(1, n+1)]
    operation = np.empty((m+1, n+1), dtype = '<U1') # chaines de 1 caractère
    operation[1:, 0] = 'E'
    operation[0, 1:] = 'I'

    for i in range(1, m+1) :
        for j in range(1, n+1) :
            if X[i-1] == Y[j-1] :
                T[i, j] = T[i-1, j-1] 
                operation[i, j] = '*' # On n'a rien à faire
            else :
                d_I = T[i, j-1]   # il faudra ensuite Insérer une lettre                
                d_E = T[i-1, j]   # il faudra ensuite Effacer une lettre
                d_R = T[i-1, j-1] # il faudra ensuite Remplacer une lettre                
                dmin, choix = min_de_trois(d_I, d_E, d_R) 
                T[i, j] = dmin + 1
                operation[i, j] = symboles[choix]
    #print(T)
    return T[m, n], operation

T, operation = lev_montant_avec_action('tortue', 'reptile')
print(T)
print(operation)




###########################################################################
#  Version récursive avec action, je ne suis pas très sûr de moi !
###########################################################################


def lev_descendant_avec_action(X, Y, T, operation) :
    print('X, Y', 'coucou', X, Y)
    m, n = len(X), len(Y)
    print(m, n)
    print('T :',  T, T.shape)
    # Si le calcul a déjà été fait
    if T[m, n] > -1 :
        return T[m, n]
    
    # Sinon, appels récursifs

    if X[-1] == Y[-1] :
         T[m, n] = lev_descendant_avec_action(X[:-1], Y[:-1], T, operation)
         operation[m, n] = '*'
    else :
        dE = lev_descendant_avec_action(X[:-1], Y, T, operation)
        dI = lev_descendant_avec_action(X, Y[:-1], T, operation)
        dR = lev_descendant_avec_action(X[:-1], Y[:-1], T, operation)
        dmin, choix = min_de_trois(dI, dE, dR)
        T[m, n] = min(dE, dI, dR) + 1 
        operation[m, n] = symboles[choix]
    return T[m, n]    


def applique_lev_descendant_avec_action(X, Y):
    m, n = len(X), len(Y)
    T = - np.ones((m+1, n+1), 'int')    
    T[0,:] = [j for j in range(n+1)]
    T[:,0] = [ i for i in range(m+1)]    
    operation = np.empty((m+1, n+1), dtype = '<U1') # chaines de 1 caractère
    return lev_descendant_avec_action(X, Y, T, operation), T, operation

dist, T, operation = applique_lev_descendant_avec_action('tortue', 'reptile')
print(T)
print(operation)

#########################################################################"
        
def retrouve_transfo(operation) :
    S = []
    a, b = operation.shape
    i, j = a-1, b-1
    while (i, j) != (0, 0) :   
        S.append((i, j))
        if operation[i, j] == 'E' :
            i, j = i-1, j
        elif operation[i, j] == 'I' :
            i, j = i, j-1
        else :
            i, j = i-1, j-1 # pour les deux cas '*' et 'R'
            
    S.reverse()
    return S
# 
S = retrouve_transfo(operation)
print(S)

   

def imprime_suite_transfo(X, Y, operation, S) :
    ''' Attention : si (i, j) sont les indices dans le tableau
    les caractères correspondant sont X[i-1] et Y[j-1]. '''
    print('mot X initial', X)
    X1 = list(X) # liste de lettres qui va évoluer pour former le mot Y
    p = 0 # indice de parcours de X1, la liste qui évolue

    for i, j in S :
        print('________ i, j = ', i, j, '_________________________________')
        op = operation[i, j]
        print('p', p)
        if op == 'E' :
            print('Effacer', X[i-1]) 
            del(X1[p]) # on n'incrémente pas p à cause de la suppression.
                       # la prochaine lettre à traiter aura le même indice p.
        elif op == 'I' :
            print('Insérer', Y[j-1])            
            X1.insert(p, Y[j-1]) # Après insertion, il prend le rang p.
            p += 1     # donc au tour suivant, il faut s'occuper de p+1.
        elif op == 'R' :
            print('Remplacer', X[i-1], ' par ', Y[j-1]) 
            X1[p] = Y[j-1]
            p += 1
        elif op == '*' :
            p += 1
            print('Ne rien faire')
        print(''.join(X1))   

imprime_suite_transfo('tortue', 'reptile', operation, S)


def boulot(X, Y) :
    d, op = lev_montant_avec_action(X, Y)
    print('Il faut effectuer ', d, 'modifications élémentaires')
    print('op\n', op)
    S = retrouve_transfo(op)
    imprime_suite_transfo(X, Y, op, S)

boulot('tortue', 'reptile')
boulot('tortue', '')
boulot('', 'banane')
boulot('tortue', 're')

############################################################
# J'essaie de tout faire en une seule fois.
## Mauvaise idée ! Il faut d'abord faire le parcours à l'envers,
# puis le refaire à l'endroit !!!!!!!!





# Fonction qui initialise les tableaux T et operation, puis fait le boulot récursif.
def boulot_rec(X, Y):
    m, n = len(X), len(Y)
    T = - np.ones((m+1, n+1), 'int')   
    T[0,:] = [j for j in range(n+1)]
    T[:,0] = [ i for i in range(m+1)]
    operation = np.empty((m+1, n+1), dtype = '<U1')
    operation[0, 1:] = 'I'
    operation[1:, 0] = 'E'
    d = lev_descendant_avec_action(X, Y, T, operation)
    print('Il faut effectuer', d, ' opérations élémentaires.')
    print('T', T)
    print('opérations', operation)
    S = retrouve_transfo(operation)
    print('S', S)
    
    imprime_suite_transfo(X, Y, operation, S)    


boulot_rec('tortue', 'reptile')    
boulot_rec('tortue', '')
boulot_rec('', 'tortue')