## Nombre de chemins

def chemins_memo(n: int, p: int)-> int:
    D = {}

    def chemins(i, j):
        if (i, j) in D:
            return D[(i,j)]

        if i == 0 or j == 0:
            r = 1
        else:
            r = chemins(i-1, j) + chemins(i, j-1) + chemins(i-1, j-1)
        D[(i, j)] = r

        return r

    return chemins(n, p)

def chemins_bottom_up(n: int, p: int)-> int:
    D = {}

    for i in range(n+1):
        D[(i, 0)] = 1
    for j in range(p+1):
        D[(0, j)] = 1

    for i in range(1, n+1):
        for j in range(1, p+1):
            D[(i, j)] = D[(i-1, j)] + D[(i, j-1)] + D[(i-1, j-1)]

    return D[(n, p)]


assert chemins_memo(8, 10) == 1256465
assert chemins_bottom_up(8, 10) == 1256465


## Somme maximale

import numpy as np

def somme_max_memo(T: np.array)-> int:
    D = {}

    def somme_max(i, j):
        if (i,j) in D:
            return D[(i,j)]

        n = len(T)
        if i == len(T) - 1:
            r = T[i, j]
        else:
            r = T[i, j] + max(somme_max(i+1, j), somme_max(i+1, j+1))
        D[(i, j)] = r

        return r

    return somme_max(0, 0)

def sommes_bottom_up(T: np.array)-> dict:
    D = {}

    n = len(T)
    for j in range(len(T)):
        D[(n-1, j)] = T[n-1, j]

    for i in range(n-2, -1, -1):
        for j in range(0, i+1):
            D[(i, j)] = T[i, j] + max(D[(i+1, j)], D[(i+1, j+1)])

    return D



def chemin_optimal(T: np.array)-> list:
    D = sommes_bottom_up(T)

    chemin = [T[0, 0]]
    i = j = 0

    while i < len(T) - 1:
        if D[(i+1, j+1)] >= D[(i+1, j)]:
            j += 1
        i += 1
        chemin.append(T[i, j])

    return chemin


T1 = np.array([
    [3, 0, 0, 0],
    [7, 4, 0, 0],
    [2, 4, 6, 0],
    [8, 5, 9, 3]
])

T2 = np.array([
    [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [8, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [13, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [10, 10, 19, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [5, 14, 3, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [6, 19, 14, 14, 16, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [20, 13, 11, 15, 5, 10, 9, 0, 0, 0, 0, 0, 0, 0, 0],
    [12, 14, 5, 6, 7, 10, 6, 1, 0, 0, 0, 0, 0, 0, 0],
    [16, 7, 12, 19, 3, 11, 10, 19, 5, 0, 0, 0, 0, 0, 0],
    [13, 12, 15, 3, 8, 12, 16, 19, 18, 1, 0, 0, 0, 0, 0],
    [13, 6, 9, 9, 15, 6, 18, 16, 16, 8, 11, 0, 0, 0, 0],
    [2, 7, 18, 10, 20, 6, 3, 18, 11, 13, 15, 20, 0, 0, 0],
    [15, 19, 19, 19, 9, 18, 12, 16, 10, 17, 16, 18, 10, 0, 0],
    [20, 14, 3, 17, 9, 15, 12, 14, 20, 13, 17, 3, 18, 6, 0],
    [15, 10, 6, 2, 16, 7, 10, 2, 15, 7, 16, 9, 1, 9, 14],
])

assert somme_max_memo(T1) == 23
assert somme_max_memo(T2) == 199
assert chemin_optimal(T2) == [2, 8, 13, 10, 14, 19, 13, 14, 12, 15, 9, 18, 19, 17, 16]


## Distance d'édition

def dist_naif(a: str, b: str)-> int:
    if len(a) == 0 or len(b) == 0:
        return max(len(a), len(b))
    elif a[-1] != b[-1]:
        return min(dist_naif(a[:-1], b), dist_naif(a, b[:-1]), dist_naif(a[:-1], b[:-1])) + 1
    else:
        return min(dist_naif(a[:-1], b) + 1, dist_naif(a, b[:-1]) + 1, dist_naif(a[:-1], b[:-1]))

def dist_memo(a: str, b: str)-> int:
    D = {}

    def dist(i, j):
        if (i, j) in D:
            return D[(i, j)]

        if i == 0 or j == 0:
            r = max(i, j)
        elif a[i-1] != b[j-1]:
            r = min(dist(i-1, j), dist(i, j-1), dist(i-1, j-1)) + 1
        else:
            r = min(dist(i-1, j) + 1, dist(i, j-1) + 1, dist(i-1, j-1))
        D[(i, j)] = r

        return r

    return dist(len(a), len(b))

def dist_bottom_up(a: str, b: str)-> int:
    D = {}

    for i in range(len(a)+1):
        D[(i, 0)] = i

    for j in range(len(b)+1):
        D[(0, j)] = j

    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] != b[j-1]:
                D[(i, j)] = min(D[(i-1, j)], D[(i, j-1)], D[(i-1, j-1)]) + 1
            else:
                D[(i, j)] = min(D[(i-1, j)] + 1, D[(i, j-1)] + 1, D[(i-1, j-1)])

    return D[(len(a), len(b))]

def distances(a: str, b: str)-> dict:
    D = {}

    for i in range(len(a)+1):
        D[(i, 0)] = i

    for j in range(len(b)+1):
        D[(0, j)] = j

    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i-1] != b[j-1]:
                D[(i, j)] = min(D[(i-1, j)], D[(i, j-1)], D[(i-1, j-1)]) + 1
            else:
                D[(i, j)] = min(D[(i-1, j)] + 1, D[(i, j-1)] + 1, D[(i-1, j-1)])

    return D

def chemin_optimal(a: str, b: str)-> list:
    D = distances(a, b)

    chemin = [a]
    mot = a
    i = len(a)
    j = len(b)


    while mot != b:
        if D[(i, j)] == D[(i-1, j)] + 1:
            mot = mot[:i-1] + mot[i:]
            i -= 1
            chemin.append(mot)
        elif D[(i, j)] == D[(i, j-1)] + 1:
            mot = mot[:i] + b[j-1] + mot[i:]
            j -= 1
            chemin.append(mot)
        elif D[(i, j)] == D[(i-1, j-1)] + 1:
            mot = mot[:i-1] + b[j-1] + mot[i:]
            i -= 1
            j -= 1
            chemin.append(mot)
        else:
            i -= 1
            j -= 1

    return chemin


assert dist_naif("NICHER", "CHIENS") == 5
assert dist_memo("Mémoïsation", "Calcul de bas en haut") == 19
assert dist_bottom_up("Mémoïsation", "Calcul de bas en haut") == 19