def compte(mot):
    d = {}
    for c in mot:
        d[c] = d.get(c, 0) + 1
    return d

compte("aza")

def distance_simple(h1, h2):
    d = 0
    tout = set(h1).union(set(h2))
    for c in tout:
        d += abs(h1.get(c, 0) - h2.get(c, 0))
    return d

distance_simple(compte("journal"), compte("journaux"))

distance_simple(compte("journal"), compte("naljour"))

"""
Explanation: 2018-09-25 - Distance entre mots
La distance proposée est naïve puisqu'elle considère uniquement les lettres communes entre deux mots.
$m ={ c_1, ..., c_n}$
$C = m_1 \cap m_2$
$d(m_1,m_2)=#{c \in m_1 \backslash C} + #{c \in m_2 \backslash C}$
Un indice pour l'implémenter : il peut être utile de passer par les dictionnaires.
End of explanation
"""


def decoupe(mot):
    couples = []
    for i in range(1, len(mot)):
        couples.append(mot[i-1:i+1])
    return [mot[:1]] + couples + [mot[-1:]]
decoupe("journal")

"""
Explanation: La distance ne tient pas compte de l'ordre des lettres, on en tient compte de façon locale en considèrent les couples de lettres consécutives plutôt que les lettres.
End of explanation
"""


distance_simple(compte(decoupe("ninon")),
                compte(decoupe("nonin")))

distance_simple(compte(decoupe("journal")),
                compte(decoupe("jourinal")))

distance_simple(compte(decoupe("journal")),
                compte(decoupe("naljour")))

"""
Explanation: Mais ce n'est pas une distance à proprement parler comme en témoigne le contre-exemple suivant :
End of explanation
"""


def distance_edition(m1, m2):
    mat = [[len(m1) + len(m2) for j in range(len(m2))] for i in range(len(m1))]
    drt = [["n" for j in range(len(m2))] for i in range(len(m1))]
    mat[0][0] = 0 if m1[0] == m2[0] else 1
    for i in range(len(m1)):
        for j in range(len(m2)):
            if i > 0 and mat[i][j] > mat[i-1][j] + 1:
                mat[i][j] = mat[i-1][j] + 1
                drt[i][j] = "^"
            if j > 0 and mat[i][j] > mat[i][j-1] + 1:
                mat[i][j] = mat[i][j-1] + 1
                drt[i][j] = "<"
            if i > 0 and j > 0:
                c = 0 if m1[i] == m2[j] else 1
                if mat[i][j] > mat[i-1][j-1] + c:
                    mat[i][j] = mat[i-1][j-1] + c
                    drt[i][j] = "=" if c == 0 else "\\"
    return mat[len(m1)-1][len(m2)-1], drt

d, drt = distance_edition("jourinal", "joirnal")
d

"""
Explanation: On passe alors à la distance d'édition :
End of explanation
"""


for l in drt:
    print(" ".join(l))

"""
Explanation: Pour retrouver le chemin, il suffit de remonter le chemin suivant depuis l'arrivée jusqu'au point de départ.
End of explanation
"""


