/************************************************
Programmer : Muhammad Azri bin Jasni @ Abdul Rani
Program : project euler problem 11_2.cpp
Link : http://projecteuler.net/problem=11
Description: Finally got the answer
Note : Diagonally, means both left-to-right and right-to-left.
*************************************************
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
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 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
************************************************/
/*
Draft
1. put in 2-dimensional array
2. get max product of 4 adjacent numbers for diogonally, horizontaly and vertically (three for-loop)
3. test with small sample:
08 02 22 97
49 49 99 40
81 49 31 73
52 70 95 23
08 09 are octal form, cant be used for int?? huh?
horizontal and vertical was done using trial and error... so I don\'t remember
diagonal test
[0][0] [1][1] [2][2] [3][3] , [0][1] [1][2] [2][3] [3][4]
[1][0] [2][1] [3][2] [4][3] , [1][1] [2][2] [3][3] [4][4]
for (int i=0;i<max-3;i++)
for (int j=0;j<max-3;j++)
[i][j]*[i+1][j+1]*[i+2][j+2]*[i+3][j+3]
we may reduce process by identify 0. bcoz 0 will result in zero, so can skip instantly if want
*/
/*
Thanks to this page: http://blog.functionalfun.net/2008/05/project-euler-problem-11.html
Although, there is C++ solution, that person calculate diagonal 2 times more than needed.
***************
diagonal test [right to left]
[0][3] [1][2] [2][1] [3][0] , [0][4] [1][3] [2][2] [3][1]
[1][3] [2][2] [3][1] [4][0] , [1][4] [2][3] [3][2] [4][1]
for (int i=0;i<max-3;i++)
for (int j=3;j<max;j++)
[i][j]*[i+1][j-1]*[i+2][j-2]*[i+3][j-3]
*/
#include <iostream>
using namespace std;
bool checkZero(int);
int main ()
{
const int max = 20;
long maxProduct = 0;//greatest product
long product = 1;
//initialize array
int numbers [max][max] =
{
{ 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8},
{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, 8,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, 9,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, 9,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, 8,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, 8,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}
};
//horizontal
for (int i=0; i<(max); i++)
{
for (int j=0; j<(max-3); j++)
{
if (checkZero(numbers[i][j]))
continue;
product = numbers[i][j] * numbers[i][j+1] * numbers[i][j+2] * numbers[i][j+3];
//cout << numbers[i][j] << "*" << numbers[i][j+1] << "*" << numbers[i][j+2]<< "*" << numbers[i][j+3] << "=" << product <<endl;//test
if (product > maxProduct)
maxProduct = product;
}
}
//cout << "===========" << endl; //test
//vertical
for (int j=0; j<(max); j++)
{
for (int i=0; i<(max-3); i++)
{
if (checkZero(numbers[i][j]))
continue;
product = numbers[i][j] * numbers[i+1][j] * numbers[i+2][j] * numbers[i+3][j];
//cout << numbers[i][j] << "*" << numbers[i+1][j] << "*" << numbers[i+2][j] << "*" << numbers[i+3][j] << "=" << product <<endl;//test
if (product > maxProduct)
maxProduct = product;
}
}
//cout << "===========" << endl; //test
//diagonal left to right
for (int i=0; i<(max-3); i++)
{
for (int j=0; j<(max-3); j++)
{
if (checkZero(numbers[i][j]))
continue;
product = numbers[i][j] * numbers[i+1][j+1] * numbers[i+2][j+2] * numbers[i+3][j+3];
//cout << numbers[i][j] << "*" << numbers[i+1][j+1] << "*" << numbers[i+2][j+2] << "*" << numbers[i+3][j+3] << "=" << product <<endl;//test
if (product > maxProduct)
maxProduct = product;
}
}
//diagonal right to left
for (int i=0; i<(max-3); i++)
{
for (int j=3; j<(max); j++)
{
if (checkZero(numbers[i][j]))
continue;
product = numbers[i][j] * numbers[i+1][j-1] * numbers[i+2][j-2] * numbers[i+3][j-3];
//cout << numbers[i][j] << "*" << numbers[i+1][j+1] << "*" << numbers[i+2][j+2] << "*" << numbers[i+3][j+3] << "=" << product <<endl;//test
if (product > maxProduct)
maxProduct = product;
}
}
// cout << "===========" << endl; //test
cout << "maxProduct = " << maxProduct << endl;
//system("pause");
return 0;
}
bool checkZero(int a)
{
if (a==0)
return true;
else
return false;
}