Voici un résumé de l'énoncé du problème 11 "Largest product in a grid" du Project Euler (traduction complète en français ici) :

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid ? (voir énoncé complet)

Compréhension du problème

Reformulons le problème : il nous faut trouver le plus grand produit de 4 nombres adjacents se trouvant dans la même direction (horizontalement, verticalement ou en diagonale) dans la grille 20 par 20 donné dans l'énoncé complet. Pour résoudre ce problème, il nous faut donc procéder de la manière suivante :

• Convertir la grille dans l'énoncé en un tableau contenant tous les nombres
• Lire les nombres 1 par 1 et faire pour chacun le produit horizontal, vertical et en diagonale ou plutôt dans les 2 diagonales (celle qui va du haut à gauche au bas à droite et celle qui va du haut à droite au bas à gauche)
• Afficher le plus grand produit

Avant de passer au programme, il nous faut juste expliciter un point, celui qui consiste à calculer les produits car, réellement, comment calculer les produits horizontaux, verticaux et dans les diagonales ? Pour se faire, posons \(p\) la position, dans la grille (ou notre tableau dans le programme), du nombre pour lequel on veut calculer les produits, alors :

• le produit horizontal correspond au produit du nombre de position \(p\) par celui de position \(p+1\) par celui de position \(p+2\) par celui de position \(p+3\). Ce produit n'est possible que si \(p < 17\) dans chaque ligne.
• le produit vertical correspond au produit du nombre de position \(p\) par celui de position \(p+20\) par celui de position \(p+40\) par celui de position \(p+60\). Ce produit n'est possible que si \(p < 340\) dans l'ensemble de la grille.
• le premier produit en diagonal (celle du haut à gauche au bas à droite) correspond au produit du nombre de position \(p\) par celui de position \(p+21\) par celui de position \(p+42\) par celui de position \(p+63\). Ce produit n'est possible que si \(p<17\) dans chaque ligne et \(p<340\) dans l'ensemble de la grille.
• le second produit en diagonal (du haut à droite au bas à gauche) correspond au produit du nombre de position \(p\) par celui de position \(p+19\) par celui de position \(p+38\) par celui de position \(p+57\). Ce produit n'est possible que si \(p>3\) dans chaque ligne et \(p<340\) dans l'ensemble de la grille.

Le programme

Voici le programme Python que l'on peut utiliser pour résoudre ce problème :

#Transformation de la chaine de caractère en tableau de nombres
grid = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 \
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 \
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 \
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 \
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 \
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 \
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 \
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 \
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 \
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 \
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 \
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 \
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 \
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 \
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 \
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 \
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 \
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 \
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 \
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"
grid = [int(i) for i in grid.split()]
produits = []
#Calcul des produits horizontaux, verticaux
#et en diagonales pour chacun des nombres
for i in range(400):
    if i%20 < 17:
        produits.append(grid[i]*grid[i+1]*grid[i+2]*grid[i+3])
    if i < 340:
        produits.append(grid[i]*grid[i+20]*grid[i+40]*grid[i+60])
    if i%20 < 17 and i < 340:
        produits.append(grid[i]*grid[i+21]*grid[i+42]*grid[i+63])
    if i%20 > 3 and i < 340:
        produits.append(grid[i]*grid[i+19]*grid[i+38]*grid[i+57])
print(max(produits))

Le résultat

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