Eric Daniels - Home  Blog  About

Problem 11

In the $20 x 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 $20x20$ grid?

All brute force... But it works fairly quickly. I assume one could do some math by parsing the array and finding out which corners cannot be used.

long long P11 ()
{
        long long grid[] = {    8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 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, 0,
                                        81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65,
                                        52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21,
                                        24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
                                        21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95,
                                        78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92,
                                        16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57,
                                        86, 56, 0, 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,
                                        4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
                                        88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
                                        4, 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, 4, 36, 16,
                                        20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54,
                                        1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48};

        int maxPos = sizeof(grid)/sizeof(long long);

        long long maxProd = 0;

        long long tempProd;

        int a;

        for ( int i = 0; i < maxPos; i++)    {               tempProd = 0;           a = grid[i];            //Up            if ( (i-60) >= 0)
                {
                        tempProd = a*grid[i-20]*grid[i-40]*grid[i-60];

                        if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Down
                if ( (i+60) < maxPos)                {                       tempProd = a*grid[i+20]*grid[i+40]*grid[i+60];                  if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Left
                if ( (i-3) % 20 == 0)
                {
                        tempProd = a*grid[i-1]*grid[i-2]*grid[i-3];

                        if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Right
                if ( (i+3) % 19 == 0)
                {
                        tempProd = a*grid[i+1]*grid[i+2]*grid[i+3];

                        if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Diagonally Up-Left
                if ( i - 63 >= 0 )
                {
                        tempProd = a*grid[i-21]*grid[i-42]*grid[i-63];

                        if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Diagonally Up-Right
                if ( i - 57 >= 0 )
                {
                        tempProd = a*grid[i-19]*grid[i-38]*grid[i-57];

                        if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Diagonally Down-Left
                if ( i + 63 < maxPos )               {                       tempProd = a*grid[i+21]*grid[i+42]*grid[i+63];                  if (tempProd > maxProd)
                                maxProd = tempProd;
                }
                //Diagonally Down-Right
                if ( i + 57 < maxPos )               {                       tempProd = a*grid[i+19]*grid[i+38]*grid[i+57];                  if (tempProd > maxProd)
                                maxProd = tempProd;
                }

        }

        return maxProd;
}