Popular Posts

Tuesday, February 17, 2015

Largest Product of Four Numbers in Grid

The other day I came across Project Euler and find it interesting especially it's Problem 11

Problem Statement:

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 the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Solution:

Here is what I come up in two hours , this definitely can be improved more but I am now done, you are welcomed to improve it :-0)

1:  /**  
2:   * Created by Waqas on 1/14/2015.  
3:   */  
4:  public class Problem_Eleven {  
5:    
6:    public static void main(String [] args){  
7:    
8:      int numbersArray [][] = readNumberArray();  
9:      int largestProductOfFourAdjNumbers = 0;  
10:      int actualNumbers[] = new int[4];  
11:      boolean isDiagonal = false;  
12:    
13:      for(int i = 0; i < 20; i++){  
14:        for(int j = 0; j < 17; j++){  
15:          int product = getProductOfFourNumbers(numbersArray[i][j], numbersArray[i][j + 1], numbersArray[i][j + 2], numbersArray[i][j + 3]);  
16:    
17:          if(largestProduct(product, largestProductOfFourAdjNumbers))  
18:          {  
19:            largestProductOfFourAdjNumbers = product;  
20:    
21:            actualNumbers[0] = numbersArray[i][j];  
22:            actualNumbers[1] = numbersArray[i][j + 1];  
23:            actualNumbers[2] = numbersArray[i][j + 2];  
24:            actualNumbers[3] = numbersArray[i][j + 3];  
25:    
26:            isDiagonal = false;  
27:          }  
28:        }  
29:      }  
30:    
31:      for(int i = 0; i < 17; i ++){  
32:        for(int j = 0; j < 20; j++){  
33:          int product = getProductOfFourNumbers(numbersArray[i][j], numbersArray[i + 1][j], numbersArray[i + 2][j], numbersArray[i + 3][j]);  
34:    
35:          if(largestProduct(product, largestProductOfFourAdjNumbers))  
36:          {  
37:            largestProductOfFourAdjNumbers = product;  
38:    
39:            actualNumbers[0] = numbersArray[i][j];  
40:            actualNumbers[1] = numbersArray[i + 1][j];  
41:            actualNumbers[2] = numbersArray[i + 2][j];  
42:            actualNumbers[3] = numbersArray[i + 3][j];  
43:    
44:            isDiagonal = false;  
45:          }  
46:        }  
47:      }  
48:    
49:      for(int i = 0; i < 17; i++){  
50:        for(int j = 0; j < 17; j++){  
51:          int product = getProductOfFourNumbers(numbersArray[i][j],numbersArray[i + 1][j + 1],numbersArray[i + 2][j + 2], numbersArray[i + 3][i + 3]);  
52:    
53:          if(largestProduct(product, largestProductOfFourAdjNumbers))  
54:          {  
55:            largestProductOfFourAdjNumbers = product;  
56:    
57:            actualNumbers[0] = numbersArray[i][j];  
58:            actualNumbers[1] = numbersArray[i + 1][j + 1];  
59:            actualNumbers[2] = numbersArray[i + 2][j + 2];  
60:            actualNumbers[3] = numbersArray[i + 3][i + 3];  
61:    
62:            isDiagonal = true;  
63:          }  
64:        }  
65:      }  
66:    
67:      for(int i = 0; i < 17; i ++){  
68:        for(int j = 3; j < 20; j ++){  
69:          int product = getProductOfFourNumbers(numbersArray[i][j],numbersArray[i + 1][j - 1],numbersArray[i + 2][j - 2],numbersArray[i + 3][j - 3]);  
70:    
71:          if(largestProduct(product, largestProductOfFourAdjNumbers))  
72:          {  
73:            largestProductOfFourAdjNumbers = product;  
74:    
75:            actualNumbers[0] = numbersArray[i][j];  
76:            actualNumbers[1] = numbersArray[i + 1][j - 1];  
77:            actualNumbers[2] = numbersArray[i + 2][j - 2];  
78:            actualNumbers[3] = numbersArray[i + 3][j - 3];  
79:    
80:            isDiagonal = true;  
81:          }  
82:        }  
83:      }  
84:    
85:      System.out.format("Max Product of these %d * %d * %d * %d four Numbers = %d",actualNumbers[0],actualNumbers[1],actualNumbers[2],actualNumbers[3],largestProductOfFourAdjNumbers);  
86:    
87:      if (isDiagonal) {  
88:        System.out.print(". And these numbers are diagonal to each other");  
89:      } else {  
90:        System.out.print(". And these numbers are adjacent to each other");  
91:      }  
92:    }  
93:    
94:    private static int getProductOfFourNumbers(int one, int two, int three, int four){  
95:      return one * two * three * four;  
96:    }  
97:    
98:    private static boolean largestProduct(int product, int largestNumberProduct){  
99:      if(product > largestNumberProduct)  
100:        return true;  
101:      else  
102:        return false;  
103:    }  
104:    
105:    private static int[][] readNumberArray()  
106:    {  
107:      return new int [][] {  
108:          {8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,8},  
109:          {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},  
110:          {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},  
111:          {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},  
112:          {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},  
113:          {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},  
114:          {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},  
115:          {67,26,20,68,02,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},  
116:          {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},  
117:          {21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},  
118:          {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,9,53,56,92},  
119:          {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},  
120:          {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},  
121:          {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},  
122:          {04,52,8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},  
123:          {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},  
124:          {04,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36},  
125:          {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},  
126:          {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},  
127:          {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}  
128:      };  
129:    
130:    }  
131:  }  
132:    


Any Suggestion, Comments?

Post a Comment