## transformation

def transformation(M1,M2):
    dico = lev(M1,M2)
    i,j,M,LM = len(M1),len(M2),M2,[M2]
    while i>0 or j>0:
        il,jl = i-1,j-1
        l1,l2 = M1[il],M2[jl]
        if i==0: # Horizontal
            M = sup(M,jl)
            j -= 1
            LM.append(M)
        elif j==0: # Vertical
            M = ins(M,j,l1)
            i -= 1
            LM.append(M)
        else:
            if l1 == l2 : # Diagonale
                i,j = i-1,j-1
            else:
                if dico[(i,j)] == dico[(i-1,j-1)] + 1: # Diagonale
                    M = sub(M,jl,l1)
                    i,j = i-1,j-1
                elif dico[(i,j)] == dico[(i-1,j)] + 1: # Vertical
                    M = ins(M,j,l1)
                    i -= 1
                elif dico[(i,j)] == dico[(i,j-1)] + 1: # Horizontal
                    M = sup(M,jl)
                    j -= 1
                LM.append(M)
    LM.reverse()
    return LM

## Transformation rec

def transformation_bis(M1,M2):
    dico = lev_rec_mem_bis(M1,M2)
    i,j,M,LM = 0,0,M1,[M1]
    il = i
    while i<len(M1) or j<len(M2):
        if i==len(M1):
            l2 = M2[j]
            M = #####
            j += 1
            il += 1
            LM.append(M)
        elif j==len(M2):
            M = #####
            i += 1
            LM.append(M)
        else:
            l1,l2 = M1[i],M2[j]
            if l1 == l2 :
                i,j = i+1,j+1
                il += 1
            else:
                if dico[(i,j)] == dico[(i+1,j+1)] + 1:
                    M = #####
                    i,j = i+1,j+1
                    il += 1
                elif dico[(i,j)] == dico[(i+1,j)] + 1:
                    M = #####
                    i += 1
                elif dico[(i,j)] == dico[(i,j+1)] + 1:
                    M = #####
                    j += 1
                    il += 1
                LM.append(M)
    return LM