Voici un résumé de l'énoncé du problème 18 "Maximum path sum I" du Project Euler (traduction complète en français ici) :

Find the maximum total from top to bottom of the triangle below (voir énoncé complet)

Compréhension du problème

Reformulons le problème : il nous faut trouver le plus grand total en allant de haut en bas dans le triangle de l'énoncé (voir énoncé complet).

La première idée pour résoudre ce problème serait de tester les 16384 chemins possibles, mais cette façon de faire, comme dit dans l'énoncé, n'est pas optimale et ne fonctionnerait pas pour des triangles beaucoup plus grands comme dans le problème 67. Il nous faut donc réfléchir à une autre méthode, plus efficace.

Une autre façon de faire est de trouver le plus grand total petit à petit, c'est à dire en passant par des totaux intermédiaires. Pour se faire, il nous faut commencer par calculer le plus grand total possible si on part du 1er nombre de l'avant dernière ligne, soit 63 + maximum entre 4 et 62, soit 125. Il nous faut ensuite remplacer ce nombre par son total maximal. Nous savons donc maintenant que si nous arrivons, en partant de la 1ère ligne du triangle, au 1er nombre de l'avant dernière ligne, le total maximum à partir de ce nombre sera 125, nous permettant de ne pas avoir besoin de continuer jusqu'à la dernière ligne.

Une fois le total maximal en partant du 1er nombre de l'avant dernière ligne trouvé, il nous faut faire la même chose pour tous les autres nombres de cette ligne, c'est à dire trouver les totaux maximums et remplacer les nombres par ces totaux. Ainsi, nous devons obtenir le nouveau triangle suivant :

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
125 164 102 95 112 123 165 128 166 109 122 147 100 54
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Nous pouvons voir que les nombres de l'avant dernière ligne ont augmenté. Notez aussi que maintenant la dernière ligne ne sert plus à rien et peut être supprimée si l'on veut.

Maintenant, il ne nous reste plus qu'à reproduire tout ce que nous venons de faire pour l'avant avant dernière ligne, l'avant avant avant dernière ligne... jusqu'à la première, c'est à dire trouver, pour tous les nombres de chacune des lignes, le total maximal pour aller de ce nombre à la ligne du dessous. Une fois fait, la solution du problème correspondra à la valeur de l'unique nombre de la 1ère ligne.

Le programme

Voici donc le programme Python que nous pouvons utiliser pour résoudre ce problème :

def max_path_sum(triangle):
    #Transformation de la chaîne de caractère en une liste contenant
    #des sous listes (représentant les lignes) qui contiennent
    #les nombres de chaque ligne
    triangle = [[int(j) for j in i.split()] for i in triangle.split("\n")]
    #Inversion de la liste triangle
    triangle.reverse()
    #Teste de toutes les valeurs à partir de la seconde ligne
    #pour trouver quel est la somme maximale possible en partant de ces valeurs
    for i in range(1, len(triangle)):
        for j, k in enumerate(triangle[i]):
            triangle[i][j] = k + max([triangle[i-1][j], triangle[i-1][j+1]])
    return triangle[-1][0]
​
triangle = """75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"""
print(max_path_sum(triangle))

Maintenant que vous savez que ce programme peut trouver facilement la plus grand maximum dans un triangle, vous pouvez, sans trop d'effort, résoudre le problème 67.

Le résultat

La réponse à ce problème est 1074.