import numpy as np

## Nombre de chemins par mémoïsation




##tests

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

## Nombre de chemins : bottom_up





##tests

print(chemins_bottom_up(8, 10))
# 1256465

## Somme maximale







## 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(chemin_optimal(T2))
# [2, 8, 13, 10, 14, 19, 13, 14, 12, 15, 9, 18, 19, 17, 16]


## Distance d'édition




##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





##

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