4 Replies - 973 Views - Last Post: 14 January 2013 - 10:27 AM Rate Topic: -----

#1 ZacCarlson  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 146
  • Joined: 08-October 12

Greatest product of four adjacent numbers in a 20x20 grid question

Posted 13 January 2013 - 05:06 PM

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;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Greatest product of four adjacent numbers in a 20x20 grid question

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3549
  • View blog
  • Posts: 10,989
  • Joined: 05-May 12

Re: Greatest product of four adjacent numbers in a 20x20 grid question

Posted 13 January 2013 - 06:44 PM

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.
Was This Post Helpful? 0
  • +
  • -

#3 ZacCarlson  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 146
  • Joined: 08-October 12

Re: Greatest product of four adjacent numbers in a 20x20 grid question

Posted 13 January 2013 - 07:00 PM

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?
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3549
  • View blog
  • Posts: 10,989
  • Joined: 05-May 12

Re: Greatest product of four adjacent numbers in a 20x20 grid question

Posted 14 January 2013 - 06:01 AM

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.
Was This Post Helpful? 0
  • +
  • -

#5 ZacCarlson  Icon User is offline

  • D.I.C Head

Reputation: -7
  • View blog
  • Posts: 146
  • Joined: 08-October 12

Re: Greatest product of four adjacent numbers in a 20x20 grid question

Posted 14 January 2013 - 10:27 AM

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1