### Rendu monnaie

# Fonction fournie : dictionnaire de mémoïsation rempli
def memo_rendu(a_rendre, valeurs_pieces):
    memo = { 0 : 0 }
    def aux(i):
        if i in memo:
            return memo[i]
        memo[i] = min([1+aux(i - v) for v in valeurs_pieces if v <= i])
        return memo[i]
        # Fin de la fonction aux
    aux(a_rendre)
    return memo

# Fonction à coder : reconstruction de solutions
def pieces_rendues(a_rendre, valeurs_pieces):
    pass
    

### Grenouille

# Exemple de liste de hauteurs
exemple_hauteurs = [6, 7, 4, 8, 2, 9, 0]

# Fonction fournie : dictionnaire de mémoïsation rempli
def memo_grenouille(hauteurs):
    n = len(hauteurs)
    memo = {}
    def aux(depart):
        if depart in memo:
            return memo[depart]
        if depart == n-1:
            memo[depart] = 0
            return memo[depart]
        if depart == n-2:
            memo[depart] = abs(hauteurs[n-2] - hauteurs[n-1])
            return memo[depart]
        saut1 = abs(hauteurs[depart] - hauteurs[depart + 1])
        saut2 = abs(hauteurs[depart] - hauteurs[depart + 2])
        reste1 = aux(depart + 1)
        reste2 = aux(depart + 2)
        memo[depart] = min(saut1 + reste1, saut2 + reste2)
        return memo[depart]
        # Fin de la fonction aux
    aux(0)
    return memo
    
# Fonction à coder : reconstruction de solutions
def longueurs_sauts(hauteurs):
    pass

### Pyramide d'entiers

# Exemple de pyramide
ex_pyramide_1 = [
              { 0: 3 },
           { -1: 5 , 1: 4},
         {-2: 1, 0: 5, 2: 9},
      {-3: 2, -1: 6, 1: 5, 3: 3},
    {-4: 5, -2: 8, 0: 9, 2: 7, 4: 9}
    ]

# Fonction fournie: dictionnaire de mémoïsation
def memo_pyramide(pyr):
    hauteur = len(pyr)
    memo = {}
    def aux (ligne, colonne):
        if (ligne, colonne) in memo :
            return memo[(ligne, colonne)]
        if ligne == hauteur - 1:
            memo[(ligne, colonne)] = pyr[ligne][colonne]
            return memo[(ligne, colonne)]
        else:
            nombre = pyr[ligne][colonne]
            choix_gauche = nombre + aux(ligne+1, colonne-1)
            choix_droite = nombre + aux(ligne+1, colonne+1)
            memo[(ligne, colonne)] = max(choix_gauche, choix_droite)
            return memo[(ligne, colonne)]
    aux(0, 0)
    return memo

# Fonction à coder: reconstruction de solution
def chemin_pyramide(pyr):
    pass


### Distance d'édition entre deux mots

# Fontion fournie : dictionnaire de mémoïsation
def memo_levenshtein(u, v):
    memo = {}
    def aux(i, j):
        if (i,  j) in memo:
            return memo[(i, j)]
        if i == 0:
            memo[(i, j)] = j
            return memo[(i, j)]
        if j == 0:
            memo[(i, j)] = i
            return memo[(i, j)]
        if u[i-1] == v[j-1]:
            memo[(i, j)] = aux(i-1, j-1)
            return memo[(i, j)]
        memo[(i, j)] = 1 + min(aux(i-1, j), aux(i, j-1), aux(i-1, j-1))
        return memo[(i, j)]
        # Fin de la fonction aux
    aux(len(u), len(v))
    return memo

# Fonction à coder: reconstruction de solution
def modifications_mots(u, v):
    pass