Euler Problem 11

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?

Looks like I need to develop a tricky algorithm.

Copy the strings, parse into 2D integer array. Then use 4 different calculation methods.

1) Up/Down

2) Left/Right

3) Diagonal Left to Right

4) Diagonal Right to Left

My first attempt failed because I was trying to put too much out-of-bounds error avoidance, which ended up missing the answer.

So instead I flipped my thinking and checked every cell for all eight possibilities and used a try{} block to ignore errors. It worked.

public class Euler11
{
    public static void main(String[] args)
    {
        System.out.print(“Problem 11:\n”);
        Euler11 e = new Euler11();
        System.out.print(“Answer = ” + e.Problem()+ “\n”);
    }
    public String Problem ()
    {
        String Grid = “08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 “;
        Grid += “49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 “;
        Grid += “81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 “;
        Grid += “52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 “;
        Grid += “22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 “;
        Grid += “24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 “;
        Grid += “32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 “;
        Grid += “67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 “;
        Grid += “24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 “;
        Grid += “21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 “;
        Grid += “78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 “;
        Grid += “16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 “;
        Grid += “86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 “;
        Grid += “19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 “;
        Grid += “04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 “;
        Grid += “88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 “;
        Grid += “04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 “;
        Grid += “20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 “;
        Grid += “20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 “;
        Grid += “01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48”;
        String [] big = Grid.split(” “);
        int [] [] g = new int [21][21];
        int location = 0;
        for (int x = 1; x <= 20; x++)
        {
            for (int y = 1; y <= 20; y++)
            {
                g[x][y]= Integer.parseInt(big[location++]);
            }
        }
        int biggest = 0;
        for (int x = 1; x <= 20; x++)
        {
            for (int y = 1; y <= 20; y++)
            {
                int t[] = {0,0,0,0,0,0,0,0};
                try
                {
                    t[0]= g[x][y]*g[x+1][y]*g[x+2][y]*g[x+3][y];
                    t[1]= g[x][y]*g[x-1][y]*g[x-2][y]*g[x-3][y];
                    t[2]= g[x][y]*g[x][y+1]*g[x][y+2]*g[x][y+3];
                    t[3]= g[x][y]*g[x][y-1]*g[x][y-2]*g[x][y-3];
                    t[4]= g[x][y]*g[x+1][y+1]*g[x+2][y+2]*g[x+3][y+3];
                    t[5]= g[x][y]*g[x+1][y-1]*g[x+2][y-2]*g[x+3][y-3];
                    t[6]= g[x][y]*g[x-1][y-1]*g[x-2][y-2]*g[x-3][y-3];
                    t[7]= g[x][y]*g[x-1][y+1]*g[x-2][y+2]*g[x-3][y+3];
                }
                catch (java.lang.ArrayIndexOutOfBoundsException e)
                {
                }
                for (int i = 0; i <=7; i++)
                {
                    if (t[i] > biggest)
                    {
                        biggest = t[i];
                    }
                }
            }
        }
        return String.valueOf(biggest);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s