[ZacCarlson]

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 × 20 grid? Write a function that takes the above array as an argument and returns the max product.

The above is the question and the code below is the answer. I'm trying to understand the checking part where they checked to see where the max product is and discards the rest of the directional checks to come up with the answer. If somebody can, can somebody walk through each check. Thanks.

#include <iostream>

using std::cout;
using std::endl;

const int H = 20;
const int W = 20;
const int CONSECUTIVE = 4;
const int GRID[H][W] =
        {{8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 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, 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, 8, 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, 9, 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, 9, 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, 8, 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, 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, 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}};

int main()
{
        int max = 0, temp_max = 0, max_x = 0, max_y = 0;
        std::string direction = "";
        for (int i = 0; i < H; i++){
                for (int j = 0; j < W; j++){
                //Check right
                        if (j < (W - CONSECUTIVE)){
                                temp_max = 1;
                                for (int k = 0; k < CONSECUTIVE; k++){
                                        temp_max *= GRID[i][j+k];
                                }
                                if (temp_max > max){
                                        max = temp_max;
                                        max_x = j;
                                        max_y = i;
                                        direction = "right";
                                 }
                        }
                // Check down
                        if (i < (W - CONSECUTIVE)){
                                temp_max = 1;
                                for (int k = 0; k < CONSECUTIVE; k++){
                                        temp_max *= GRID[i+k][j];
                                }
                                if (temp_max > max){
                                        max = temp_max;
                                        max_x = j;
                                        max_y = i;
                                        direction = "down";
                                }
                        }
                //Check down-right
                        if ((i < (H - CONSECUTIVE)) && (j < (W - CONSECUTIVE))){
                                temp_max = 1;
                                for (int k = 0; k < CONSECUTIVE; k++){
                                        temp_max *= GRID[i+k][j+k];
                                }
			if (temp_max > max){
                                        max = temp_max;
                                        max_x = j;
                                        max_y = i;
                                        direction = "diagonal down right";
                                }
                        }
                //Check up-right
                        if ((i > CONSECUTIVE) && (j < (W - CONSECUTIVE))){
                                temp_max = 1;
                                for (int k = 0; k < CONSECUTIVE; k++){
                                        temp_max *= GRID[i-k][j+k];
                                }
                                if (temp_max > max){
                                        max = temp_max;
                                        max_x = j;
                                        max_y = i;
                                        direction = "diagonal up right";
                                }
                        }
                }
        }
        cout << "Max product was " << max << " at (" << max_x << "," << max_y << ") ";
        cout << "in direction " << direction << endl;
        return 0;
}

[Skydiver]

What don't you understand? The code is pretty straightforward.

BTW, the code is broken in terms of its use of the H and W constants. Sometimes H is used when looking at horizontal width, and other times W is used when looking at vertical height. Right now it works by luck because H == W, but the code will break if ever H != W.

[ZacCarlson]

OK, when it first checks right....lets say it is not right, how does it determine its not right and to check the other? How does it determine which one is the correct one?

[Skydiver]

It's not a matter of checking whether it's right or not. The way the code works is that it remembers the best answer that its seen so far. So by the time it finishes checking the entire matrix, the best answer that its seen so far is the right answer.

I am deliberately keeping my descriptions on a high level to encourage you to trying walking through the code line by line.

[ZacCarlson]

And I appreciate that as it makes me think and learn. And I think I understand it now as you just explained it. So the highest number it has produced will output as the result by default through all the checks is what you are saying.