Project Euler : solution au problème 18, en Python
Le problème 18 est un peu traître par son exemple.
En effet, la question est de déterminer quelle est la somme maximale qu'on peut obtenir en parcourant un triangle d'entiers positifs au départ de sa pointe et en ne se déplaçant que vers les 2 entiers situés "sous" celui où on se trouve.
Une approche gloutonne fonctionne bien sur l'exemple fourni; en se déplaçant à chaque étape vers le plus grand des suivants, on obtient bien la somme maximale de 23 dans le triangle suivant:
3
7 5
2 4 6
8 5 9 3
Malheureusement, cette approche gloutonne n'est pas la bonne, et ne fonctionne pas sur les données du problème.
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
J'ai donc opté pour une solution récursive exhaustive, qui est viable étant donnée la petite taille du problème, mais ne le sera pas pour le problème 67. C'est le matin.
#! /usr/bin/env python
# 2009/02/26 - euler018.py
# Solution au Probleme 18 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=18
# Jean Karim Bockstael - jkb@jkbockstael.be
def recsum(tri,row,col):
if row < len(tri) - 1:
return tri[row][col] + max(recsum(tri,row+1,col),recsum(tri,row+1,col+1))
else:
return tri[row][col]
def euler18(triangle):
return recsum(triangle,0,0)
tri = \
[[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20,4,82,47,65],
[19,1,23,75,3,34],
[88,2,77,73,7,63,67],
[99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31],
[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
print euler18(tri)