Project Euler Solution 11
Problem Statement#
What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?
In the 20 x 20 grid below, four numbers along a diagonal line have been marked in bold italics.
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
The product of these numbers is 26 x 63 x 78 x 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20x20 grid?
Solution#
This problem is similar to problem 8. In problem 8, input is a 1000 digit number and we are supposed to find the greatest product of 5 consecutive digits. That is we had to calculate the product of 5 adjacent numbers but in only one direction, left to right. Here in this problem we have to consider all directions.
When I read this problem I was wondering why I should consider both left to right and vice verse which gives the same result. But the thing is when I finished programming and wondering what is wrong with my program, I found out that when we consider diagonal numbers it gives different set of product for left to right and right to left.
Implementation#
#include <stdio.h>
int main(){ FILE * f_read; int grid[20][20]; int i, j, m, n, product, new_prod, a, b, c, d, num; new_prod = 1; product = 1; f_read = fopen("inputpe011.txt", "r"); int x = 0, y = 0; while (fscanf(f_read, "%d", &num) == 1) { grid[x][y] = num; y++; if (y == 20) { x++; y = 0; } } //Horizontally for (i = 0; i < 20; i++) { for (j = 0; j < 17; j++) { product = 1; for (m = j; m < (j + 4); m++) product = grid[i][m] *product; if (product >= new_prod) { new_prod = product; a = grid[i][j]; b = grid[i][j + 1]; c = grid[i][j + 2]; d = grid[i][j + 3]; } } } //Vertically for (j = 0; j < 20; j++) { for (i = 0; i < 17; i++) { product = 1; for (n = i; n < (i + 4); n++) product = product *grid[n][j]; if (product >= new_prod) { new_prod = product; a = grid[i][j]; b = grid[i + 1][j]; c = grid[i + 2][j]; d = grid[i + 3][j]; } } } //"Diagonal Left to Right"; for (i = 0; i < 17; i++) { for (j = 0; j < 17; j++) { m = i; n = j; product = 1; while (m <= (i + 3) && n <= (j + 3)) product = product *grid[m++][n++]; if (product >= new_prod) { new_prod = product; a = grid[i][j]; b = grid[i + 1][j + 1]; c = grid[i + 2][j + 2]; d = grid[i + 3][j + 3]; } } } //"Diagonal Right to Left"; for (i = 0; i <= 16; i++) { for (j = 19; j >= 3; j--) { m = i; n = j; product = 1; while (m <= (i + 3) && n >= (j - 3)) product = product *grid[m++][n--]; if (product >= new_prod) { new_prod = product; a = grid[i][j]; b = grid[i - 1][j - 1]; c = grid[i - 2][j - 2]; d = grid[i - 3][j - 3]; } } } printf("%d", new_prod); return 0;}Sample Output#
