import numpy as np

## Nombre de chemins par mémoïsation


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

    def chemins(i, j):
        if (i, j) in D:
            return D[(i, j)]
        elif i == 0 or j == 0:
            D[(i, j)] = 1
        else:
            D[(i, j)] = chemins(i-1, j) + chemins(i, j-1) + chemins(i-1, j-1)
        return D[(i, j)]

    return chemins(n, p)


print(chemins_memo(8, 10))
# 1256465
print(chemins_memo(20, 30))
# 386733690827821609


## Nombre de chemins : bottom_up

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)]


print(chemins_bottom_up(8, 10))
# 1256465


## Somme maximale

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

    def somme_max(i, j):
        if (i, j) in D:
            return D[(i, j)]
        elif i == len(T) - 1:
            D[(i, j)] = T[i, j]
        else:
            D[(i, j)] = T[i, j] + max(somme_max(i+1, j), somme_max(i+1, j+1))
        return D[(i, j)]

    return somme_max(0, 0)


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

    for j in range(n):
        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)
    res = [T[0, 0]]
    j = 0
    for i in range(1, len(T)):
        if D[i, j + 1] > D[i, j]:
            j = j + 1
        res.append(T[i, j])
    return res


## tests

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],
])


print(somme_max_memo(T1))
# 23
print(somme_max_memo(T2))
# 199
##
print(sommes_bottom_up(T1))
##
print(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)]
        elif i == 0 or j == 0:
            D[(i, j)] = max(i, j)
        elif a[i-1] != b[j-1]:
            D[(i, j)] = min(dist(i-1, j), dist(i, j-1), dist(i-1, j-1)) + 1
        else:
            D[(i, j)] = min(dist(i-1, j) + 1, dist(i, j-1) + 1, dist(i-1, j-1))
        
        return D[(i, j)]

    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


##tests

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


## Algorithme de Floyd-Warshall

def floydwarshall(W):
    n = len(W)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                W[i, j] = min(W[i, j], W[i, k] + W[k, j])
    return W


## test

infini = float('inf')
W = np.array([[0, infini, -2, infini],
              [4, 0, 3, infini],
              [infini, infini, 0, 2],
              [infini, -1, infini, 0]])

print(floydwarshall(W))