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

Page 1 of 1

## 4 Replies - 1960 Views - Last Post: 14 January 2013 - 10:27 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=307102&amp;s=c8bc77df53d6404a9daf49d79b9c1688&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ZacCarlson

Reputation: -7
• 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

• Code herder

Reputation: 4026
• Posts: 12,848
• 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.

### #3 ZacCarlson

Reputation: -7
• 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?

### #4 Skydiver

• Code herder

Reputation: 4026
• Posts: 12,848
• 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.

### #5 ZacCarlson

Reputation: -7
• 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.