Aller au contenu

TP — Le Donjon du Dragon

Contexte

Vous jouez à un RPG en vue du dessus. Vous venez d'entrer dans un donjon représenté par une grille de n lignes et m colonnes.

Chaque case de la grille contient une quantité d'or : - Une valeur positive : de l'or à ramasser 🪙 - Une valeur négative : un piège qui vous coûte de l'or 💀

Règles du jeu : - Vous commencez en haut à gauche : case (0, 0) - Vous devez atteindre la sortie en bas à droite : case (n-1, m-1) - Vous ne pouvez vous déplacer que vers la droite ou vers le bas - Vous souhaitez maximiser l'or total ramassé

Exemple de grille 3×4 :

[  3,  -1,   4,   1 ]
[  5,   9,  -2,   6 ]
[ -3,   2,   8,  -5 ]

Un chemin possible : (0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(2,3) → or = 3+5+9-2+8-5 = 18

Est-ce le meilleur chemin ? C'est ce que vous allez découvrir.

Partie 1 — Comprendre le problème

Question 1. Sur la grille ci-dessus, listez tous les chemins possibles de (0,0) à (2,3) en ne se déplaçant que vers la droite ou vers le bas. Combien y en a-t-il ?

Question 2. Pour chaque chemin, calculez l'or total ramassé. Quel est le chemin optimal ?

Question 3. Pour une grille de dimensions n × m, combien y a-t-il de chemins possibles en tout ? (Indice : c'est une formule combinatoire.)

Partie 2 — Formulation récursive

Notons donjon(i, j) l'or maximum qu'on peut ramasser depuis (0, 0) jusqu'à (i, j).

Question 4. Quels sont les cas de base de cette fonction récursive ? (Pensez aux bords de la grille.)

Question 5. Écrivez la relation de récurrence générale pour donjon(i, j) quand i > 0 et j > 0.

Question 6. Implémentez la version naïve donjon_naif(grille, i, j) :

def donjon_naif(grille, i, j):
    # À compléter
    pass

# Test
grille = [
    [ 3, -1,  4,  1],
    [ 5,  9, -2,  6],
    [-3,  2,  8, -5]
]
n, m = len(grille), len(grille[0])
print(donjon_naif(grille, n-1, m-1))   # doit afficher 22

Partie 3 — Version Top-Down (mémoïsation)

Question 7. La version naïve recalcule-t-elle des sous-problèmes plusieurs fois ? Pour répondre, ajoutez un compteur d'appels et testez sur la grille ci-dessus.

Question 8. Implémentez donjon_memo(grille) avec mémoïsation :

def donjon_memo(grille):
    n = len(grille)
    m = len(grille[0])
    memo = {}

    def donjon(i, j):
        # À compléter
        pass

    return donjon(n - 1, m - 1)

Question 9. Vérifiez que vous obtenez le même résultat que la version naïve.

Partie 4 — Version Bottom-Up (tableau)

Question 10. Remplissez à la main le tableau t[i][j] représentant l'or maximum qu'on peut ramasser depuis (0,0) jusqu'à (i,j) pour la grille de l'exemple.

Question 11. Implémentez donjon_bottom_up(grille) :

def donjon_bottom_up(grille):
    n = len(grille)
    m = len(grille[0])
    tableau = [[0] * m for _ in range(n)]

    # Initialiser tableau[0][0]
    # Initialiser la première ligne (on ne peut aller que vers la droite)
    # Initialiser la première colonne (on ne peut aller que vers le bas)
    # Remplir le reste du tableau
    # À compléter

    return tableau[n - 1][m - 1]

Question 12. Vérifiez que vous obtenez le même résultat que les versions précédentes.

Partie 5 — Bonus : retrouver le chemin optimal

Question 13. (Bonus) Modifiez donjon_bottom_up pour qu'elle retourne non seulement la valeur optimale, mais aussi la liste des cases du chemin optimal.

(Indice : une fois le tableau rempli, remontez depuis (n-1, m-1) vers (0,0) en choisissant à chaque étape la case voisine (gauche ou haut) qui a la plus grande valeur.)

def donjon_chemin(grille):
    # À compléter
    # Retourne (valeur_max, chemin)
    # chemin = liste de tuples (i, j) de (0,0) à (n-1, m-1)
    pass

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.