document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /************************************************
  2. Programmer : Muhammad Azri bin Jasni @ Abdul Rani
  3. Program    : project euler problem 11_2.cpp
  4. Link       : http://projecteuler.net/problem=11
  5. Description: Finally got the answer
  6. Note       : Diagonally, means both left-to-right and right-to-left.
  7. *************************************************
  8. In the 20×20 grid below, four numbers along a diagonal line have been marked in red.
  9.  
  10. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
  11. 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
  12. 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
  13. 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
  14. 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
  15. 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
  16. 32 98 81 28 64 23 67 10 [26] 38 40 67 59 54 70 66 18 38 64 70
  17. 67 26 20 68 02 62 12 20 95 [63] 94 39 63 08 40 91 66 49 94 21
  18. 24 55 58 05 66 73 99 26 97 17 [78] 78 96 83 14 88 34 89 63 72
  19. 21 36 23 09 75 00 76 44 20 45 35 [14] 00 61 33 97 34 31 33 95
  20. 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
  21. 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
  22. 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
  23. 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
  24. 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
  25. 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
  26. 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
  27. 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
  28. 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
  29. 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
  30.  
  31. The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
  32.  
  33. What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
  34. ************************************************/
  35. /*
  36. Draft
  37. 1. put in 2-dimensional array
  38. 2. get max product of 4 adjacent numbers for diogonally, horizontaly and vertically (three for-loop)
  39. 3. test with small sample:
  40. 08 02 22 97        
  41. 49 49 99 40
  42. 81 49 31 73
  43. 52 70 95 23
  44.  
  45. 08 09 are octal form, cant be used for int?? huh?
  46.  
  47. horizontal and vertical was done using trial and error... so I don\'t remember
  48.  
  49. diagonal test
  50. [0][0] [1][1] [2][2] [3][3] , [0][1] [1][2] [2][3] [3][4]
  51. [1][0] [2][1] [3][2] [4][3] , [1][1] [2][2] [3][3] [4][4]
  52. for (int i=0;i<max-3;i++)
  53.     for (int j=0;j<max-3;j++)
  54.         [i][j]*[i+1][j+1]*[i+2][j+2]*[i+3][j+3]
  55.        
  56. we may reduce process by identify 0. bcoz 0 will result in zero, so can skip instantly if want
  57. */
  58.  
  59. /*
  60. Thanks to this page: http://blog.functionalfun.net/2008/05/project-euler-problem-11.html
  61. Although, there is C++ solution, that person calculate diagonal 2 times more than needed.
  62. ***************
  63. diagonal test [right to left]
  64. [0][3] [1][2] [2][1] [3][0] , [0][4] [1][3] [2][2] [3][1]
  65. [1][3] [2][2] [3][1] [4][0] , [1][4] [2][3] [3][2] [4][1]
  66. for (int i=0;i<max-3;i++)
  67.     for (int j=3;j<max;j++)
  68.         [i][j]*[i+1][j-1]*[i+2][j-2]*[i+3][j-3]
  69. */
  70.  
  71. #include <iostream>
  72. using namespace std;
  73. bool checkZero(int);
  74. int main ()
  75. {
  76.     const int max = 20;
  77.     long maxProduct = 0;//greatest product
  78.     long product = 1;
  79.     //initialize array
  80.     int numbers [max][max] =
  81.     {
  82.         { 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8},
  83.         {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
  84.         {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
  85.         {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
  86.         {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
  87.         {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
  88.         {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
  89.         {67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
  90.         {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
  91.         {21,36,23, 9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
  92.         {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14, 9,53,56,92},
  93.         {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
  94.         {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
  95.         {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
  96.         {04,52, 8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
  97.         {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
  98.         {04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36},
  99.         {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
  100.         {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
  101.         {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}
  102.     };
  103.     //horizontal
  104.     for (int i=0; i<(max); i++)
  105.     {
  106.         for (int j=0; j<(max-3); j++)
  107.         {
  108.             if (checkZero(numbers[i][j]))
  109.                continue;
  110.            
  111.             product = numbers[i][j] * numbers[i][j+1] * numbers[i][j+2]  * numbers[i][j+3];
  112.             //cout << numbers[i][j] << "*" << numbers[i][j+1] << "*" << numbers[i][j+2]<< "*" << numbers[i][j+3] << "=" << product <<endl;//test
  113.             if (product > maxProduct)
  114.                maxProduct = product;
  115.         }
  116.     }
  117.     //cout << "===========" << endl; //test
  118.     //vertical
  119.     for (int j=0; j<(max); j++)
  120.     {
  121.         for (int i=0; i<(max-3); i++)
  122.         {
  123.             if (checkZero(numbers[i][j]))
  124.                continue;
  125.             product = numbers[i][j] * numbers[i+1][j] * numbers[i+2][j]  * numbers[i+3][j];
  126.             //cout << numbers[i][j] << "*" << numbers[i+1][j] << "*" << numbers[i+2][j] << "*" << numbers[i+3][j] << "=" << product <<endl;//test
  127.             if (product > maxProduct)
  128.                maxProduct = product;
  129.         }
  130.     }
  131.     //cout << "===========" << endl; //test
  132.     //diagonal left to right
  133.     for (int i=0; i<(max-3); i++)
  134.     {
  135.         for (int j=0; j<(max-3); j++)
  136.         {
  137.             if (checkZero(numbers[i][j]))
  138.                continue;
  139.             product = numbers[i][j] * numbers[i+1][j+1] * numbers[i+2][j+2]  * numbers[i+3][j+3];
  140.             //cout << numbers[i][j] << "*" << numbers[i+1][j+1] << "*" << numbers[i+2][j+2] << "*" << numbers[i+3][j+3] << "=" << product <<endl;//test
  141.             if (product > maxProduct)
  142.                maxProduct = product;
  143.         }
  144.     }
  145.         //diagonal right to left
  146.     for (int i=0; i<(max-3); i++)
  147.     {
  148.         for (int j=3; j<(max); j++)
  149.         {
  150.             if (checkZero(numbers[i][j]))
  151.                continue;
  152.             product = numbers[i][j] * numbers[i+1][j-1] * numbers[i+2][j-2]  * numbers[i+3][j-3];
  153.             //cout << numbers[i][j] << "*" << numbers[i+1][j+1] << "*" << numbers[i+2][j+2] << "*" << numbers[i+3][j+3] << "=" << product <<endl;//test
  154.             if (product > maxProduct)
  155.                maxProduct = product;
  156.         }
  157.     }
  158.    // cout << "===========" << endl; //test
  159.     cout << "maxProduct = " << maxProduct << endl;
  160.     //system("pause");
  161.     return 0;
  162. }
  163.  
  164. bool checkZero(int a)
  165. {
  166.      if (a==0)
  167.         return true;
  168.      else
  169.          return false;
  170. }
');