What is the greatest product of four adjacent numbers on the same straight line in the 20 by 20 grid?

Project Euler Problem 11: In the 2020 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 2020 grid?

Solution: This problems involves the following,

1. Reading the input string i.e. the numbers in 20×20 grid.
2. Calculate Product of four adjacent numbers Horizontally.
3. Calculate Product of four adjacent numbers Vertically.
4. Calculate Product of four adjacent numbers Diagonally From Left.
5. Calculate Product of four adjacent numbers Diagonally From Right.

To solve this problem we have created 3 classes that will divide the task of solving the problem. We first read the input numbers using a file reader. Then we parse the input string and save the numbers grid into a two dimensional array. Using the array obtained we calculate the greatest product going in each direction (up, down, left, right, or diagonally). Finally we display the result.


Java Program to parse the input string and generate grid array.


package reader;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class ReadInputFile {
public String readInputFile(){
File file = new File("C:/Input.txt");
StringBuffer contents = new StringBuffer();
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
String text = null;
// repeat until all lines is read
while ((text = reader.readLine()) != null) {
//Read file line by line
contents.append(text)
.append(System.getProperty("line.separator"));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (reader != null) {
reader.close();
}
} catch (IOException e) {
e.printStackTrace();
}
}
return (contents.toString());
}
public int[][] numArrayFromString(String content){
int numbers[][] = new int[20][20];
int i=0,j=0;
for(String line:content.split("n")){
line = line.trim();
for(String num:line.split(" ")){
numbers[i][j] = Integer.parseInt(num);
j++;
}
i++;
j=0;
}
return numbers;
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *