Exercice : Parcours dans la pyramide

Présentation

Le point de départ est le nœud du haut. On veut atteindre un des nœuds du bas en totalisant le score le plus grand. Par exemple, le chemin marqué en rouge totalise $25 + 16 + 21 + 10 = 72$.

On souhaite seulement connaître le meilleur score possible, on n'a pas besoin de retenir le chemin réalisant ce score.

Cette pyramide a $n = 4$ étages. Il existe $2^{n-1} = 8$ chemins différents. C'est peu, on pourrait les calculer tout et sélectionner le meilleur. On parle alors de force brute. Mais si $n$ devient grand, la force brute devient impossible : pour 1000 étages c'est $2^{999}$ chemins qu'il faudrait envisager…

Faisons d'abord un choix de d'implémentation :

# représentation en mémoire de la pyramide
p = [[25], [16, 12], [15, 21, 24], [17, 13, 10, 11]]

Questions

À quoi correspondent p[0][0] ; p[2][1] ; p[1][2] ?
Combien y a-t-il de nœuds à la ligne i
Si je m'intéresse au nœud à la ligne i et la colonne j avec i > 0, quels sont ses antécédents possibles ?
Précisez les conditions – certains nœuds n'ont qu'un antécédent, d'autres 2.

Approche dynamique

Suivant le principe de la programmation dynamique, nous allons d'abord chercher les meilleurs scores pour atteindre les nœuds en les parcourant depuis le sommet.

Le tableau s aura à la fin le même format que p mais s contiendra les meilleurs scores : s[i][j] sera le meilleur score allant du nœud au sommet en [0][0] jusqu'au nœud en [i][j] inclus.

Questions

Que vaut s[0][0] ?
Le nœud en [i][j], avec i > 0 a un ou deux antécédents. Le meilleur chemin arrivant en [i][j] passe donc par l'un d'eux. Déduisez-en une formule pour s[i][j].
On construit s dans l'ordre lexicographique – de gauche à droite et de haut en bas. Une fois que s est complet, comment extrait-on le meilleur score pour l'ensemble de la pyramide ?
Écrivez la fonction qui reçoit l'argument p et renvoie le meilleur score pour cette pyramide.

Aller plus loin

Modifiez la fonction pour qu'elle renvoie, en plus du meilleur score, une chaine "GDDG" par exemple pour un chemin Gauche - Droite - Droite - Gauche
On fournit une pyramide dans un fichier texte pyramide.txt.
Créez une fonction load_pyramide(filename:str) qui charge le fichier texte et en extrait la pyramide.