Adjacent products in a grid

Question

I'm solving Problem 11 from Project Euler. I have figured out the algorithm and what I would need to do. The grid is saved in a file grid.txt and its contents are-

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 question is- What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20x20 grid?

I know the algorithm is working right because I've tried using cout to output the nums and they show up in the right sequence. It's giving me an incorrect answer though, what could be the fault?

   void problem11()
{
    vector<vector<int>> grid;

    ifstream stream("grid.txt");
    string line;

    char *tok;

    if (stream.is_open())
    {
        while(stream.good())
        {
            getline(stream, line);

            tok = strtok((char *)line.c_str(), " ");

            vector<int> row;

            while (tok != NULL)
            {
                int field;
                stringstream ss;
                ss << tok;
                ss >> field;
                row.push_back(field);

                tok = strtok(NULL, " ");
            }
            grid.push_back(row);
        }
        stream.close();
    }

    unsigned long highest = 0;

    /// LEFT TO RIGHT
    for (int i=0; i < 20; i++) // i'th row
    {
        vector<int> row = grid.at(i);

        for (int c=0; c < 20-3; c++) // -3 to accomodate for last
        {
            unsigned long prod = row.at(c) * row.at(c+1) * row.at(c+2) * row.at(c+3); // four consecutive
            //cout << row.at(c) << " " << row.at(c+1) << " " << row.at(c+2) << " " << row.at(c+3) << endl;
            if (prod > highest)
                highest = prod;
        }
    }

    /// TOP TO DOWN
    /// This moves from left to right, then top to botom
    ///
    for (int i=0; i < 20-3; i++) // subtract last 3
    {
        vector<int> row1, row2, row3, row4;

        row1 = grid.at(i);
        row2 = grid.at(i+1);
        row3 = grid.at(i+2);
        row4 = grid.at(i+3);

        for (int c=0; c < 20; c++)
        {
            unsigned long prod = row1.at(c) * row2.at(c) * row3.at(c) * row4.at(c);
            //cout << row1.at(c) << " " << row2.at(c) << " " << row3.at(c) << " " << row4.at(c) << endl;
            if (prod > highest)
                highest = prod;
        }
    }

    /// DOWN DIAGONAL
    /// This moves diagonally from left to right, top to bottom
    for (int i=0; i < 20-3; i++) // subtract last 3
    {
        vector<int> row1, row2, row3, row4;

        row1 = grid.at(i);
        row2 = grid.at(i+1);
        row3 = grid.at(i+2);
        row4 = grid.at(i+3);

        for (int c=0; c < 20-3; c++) // omit last 3
        {
            unsigned long prod = row1.at(c) * row2.at(c+1) * row3.at(c+2) * row4.at(c+3);
            //cout << row1.at(c) << " " << row2.at(c+1) << " " << row3.at(c+2) << " " << row4.at(c+3) << endl;
            if (prod > highest)
                highest = prod;
        }
    }

    /// UP DIAGONAL
    /// This moves diagonally from left to right, bottom to top
    for (int i=3; i < 20; i++) // start from 3, skipping first four
    {
        vector<int> row1, row2, row3, row4;

        row4 = grid.at(i);
        row3 = grid.at(i-1);
        row2 = grid.at(i-2);
        row1 = grid.at(i-3);

        for (int c=0; c < 20-3; c++) // omit last 3
        {
            unsigned long prod = row4.at(c) * row3.at(c+1) * row3.at(c+2) * row4.at(c+3);
            //cout << row4.at(c) << " " << row3.at(c+1) << " " << row2.at(c+2) << " " << row1.at(c+3) << endl;
            if (prod > highest)
                highest = prod;
        }
    }

    cout << "Required: " << highest;

}

Have you tried stepping through your program in a debugger? Or printing out intermediate variables? Or running on a simple data-set first? Have you determined which of the four loops (up-down, left-right, diagonal up, diagonal down) is incorrect? — Oliver Charlesworth, Jun 08 '11 at 10:50
How do you know the answer is incorrect ? what answer do you get instead of the correct one ? — Ricky Bobby, Jun 08 '11 at 11:05
I'm not going to answer this one (and spoil the fun) but I recommend splitting this into (at least) four separate functions and testing them in isolation. — johnsyweb, Jun 08 '11 at 11:16
I did try stepping through it in a debugger and it everything comes out as expected. In my code you can see comment cout lines which show I tried printing out stuff. As far as I know, all the loops turn out to be correct. I tried verifying a few values from each of the loop from the comment cout lines and they come out to what I expect. I didn't try running on a simple data-set. I know the answer is incorrect because Project Euler tells me so. The answer I get is 51267216. There is no way I can test in isolation as all I can do to verify my program is to try and enter the answer. — Ishbir, Jun 08 '11 at 12:29
"There is no way I can test in isolation"? I respectfully disagree, but you need to heed the first part of my sentence first! — johnsyweb, Jun 08 '11 at 13:52

xtofl · Accepted Answer · 2011-06-09T07:46:09.900

6

At the risk of spoiling the fun of finding the answer yourself...

Do print out the diagonals. Check visually whether they correspond to what you would expect.

As a side-note: and don't create copies of your table rows, but access them likewise: vector[rowindex][column].

EDIT --

OK now I'm going to spoil it. In a matrix of NxN, how many diagonal paths do you have? How many paths do you traverse? (Cross check this by taking a 2x2 matrix, that has 3 diagonal paths in each direction)

PS. If you take up programming seriously, when encountering a bug, validate your assumptions first.

edited Jun 09 '11 at 07:46

answered Jun 08 '11 at 10:56

xtofl

40,723
12
105
192

I tried printing out the diagonals and they come out to be correct as I mentioned. – Ishbir Jun 08 '11 at 12:27
Sorry, what exactly do you mean by "three diagonals in each direction for 2x2 grid"? I thought the problem was asking to consider only diagonally adjacent numbers. In my understanding, there can be only 4 set of diagonally adjacent numbers at any position in any NxN grid. That is at each (x,y): (x+d,y+d),(x-d,y-d),(x+d,y-d) and (x-d,y+d) where d ranges from 0 to 3. Am I misunderstanding the problem here? – rineez Nov 16 '14 at 08:10

score 4 · Answer 2 · answered Jun 08 '11 at 12:53

Try the following input:

0 0 0 1 0 0 ...
0 0 1 0 0 0 ...
0 1 0 0 0 0 ...
1 0 0 0 0 0 ...
0 0 0 0 0 0 ...
.....

and do again what xtofl recommends you.

In general, if you want to reverse the logic of some operation, do it once and only once. (Or, in general, odd number of times.) Beware of replacing a<=b by b>=a, or left to right and top to bottom by right to left and bottom to top, or whatever similar.

score 0 · Answer 3 · edited Jun 05 '16 at 11:38

I used Javascript to solve this problem. Please let me know if you have any doubts.

<html>
  <head>
  </head>
  <body>
    <input type="button" value="Click Me" onClick="onPress()"></input>                               
  </body>
  <script>
    function onPress()
    {
        var arr=[
          [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,4,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, 0, 17, 54,24,36,29,85,57], 
          [86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51, 54, 17, 58], 
          [19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,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]
        ];
        var i, j, product=0,  arr2=[], max;
        /* Horizontal 4 digit multiplication*/
        for(i=0; i<arr.length; i++)
        {
            for(j=0; j<17;j++)
            {
                product= arr[i][j]* arr[i][j+1] *arr[i][j+2] * arr[i][j+3]
                arr2.push(product);
            }
        }
        /* Vertical 4 digit multiplication*/
        for(var j=0; j<arr.length; j++)
        {
            for(var i=0; i<17; i++)
            {
                product= arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j];
                arr2.push(product);
            }
        }
        /* left to right diagonal*/
        for(var j=0 ; j<17; j++)
        {
            for(var i=0; i<17; i++)
            {
                product= arr[i][j]* arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3];
                arr2.push(product) 
            }
        }
        /* right to left diagonal*/
        for(var i=0; i<17; i++)
        {
            for(var j=19; j>=3; j--)
            {
                product= arr[i][j]*arr[i+1][j-1]*arr[i+2][j-2]*arr[i+3][j-3]
                arr2.push(product);
            }
        }
        max= Math.max.apply(Math, arr2);
        console.log(max)
    }
    </script>
</html>

score -2 · Answer 4 · answered Jul 10 '11 at 18:53

This is the code written by me. Gives the correct answer. I hope this helps....

#include <iostream>
#include <vector>
using namespace std;



void main() 
{

int num_container[20][20] = {
                            { 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 test = num_container[6][8] * num_container[7][9] * num_container[8][10] * num_container[9][11];
cout<<test<<endl;
system("pause");

int start = 0;
int end = 3;
long long mul_result = 1;

vector<long long>final_results;

/////////////////////UP/DOWN/////////////////////
for(int k=0; k<20; k++)
{
    for(int i=0; i<=16; i++)
    {
        for(int j=start; j<=end; j++)
        {
            mul_result = mul_result * num_container[k][j];
            if (j == end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;
    }
    start = 0;
    end = 3;

    for(int i=0; i<=16; i++)
    {
        for(int j=start; j<=end; j++)
        {
            mul_result = mul_result * num_container[j][k];
            if (j == end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;
    }
    start = 0;
    end = 3;

}
/////////////////////UP/DOWN Ends here//////////////////////



///////////////////Both Ways Diagonal Starts here//////////////////////
int current_row = 0;

for(int i=0; i<=16; i++)
{
    for(int j=0; j<=16; j++)
    {
        current_row = i;
        for(int k=start; k<=end; k++)
        {
            mul_result = mul_result * num_container[current_row][k];
            current_row++;
            if (k==end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;          
    }
    start = 0;
    end = 3;

    for(int j=0; j<=16; j++)
    {
        current_row = i+3;
        for(int k=start; k<=end; k++)
        {
            mul_result = mul_result * num_container[current_row][k];
            current_row--;
            if (k==end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;          
    }
    start = 0;
    end = 3;
}
/////////////////////Both Ways diagonal ends here///////////////////


////////////////////Compare Thning Starts here//////////////////////

long long the_big_one = 0;
for(int i=0; i<final_results.size(); i++)
{
    if (final_results[i] > the_big_one)
        the_big_one = final_results[i];
}





cout<<endl<<endl<<"The big one is: "<<the_big_one<<endl;

system("pause");
}

Posting solutions to Euler problems is discouraged on this website. — Konrad Rudolph, Aug 21 '11 at 11:21
Both that and [using system("pause") is _bad_](http://stackoverflow.com/questions/1107705/systempause-why-is-it-wrong) — Chiffa, Dec 19 '13 at 21:28
I have to agree with Konrad...it is in poor taste to post a complete answer to an active programming challenge. — Beska, Nov 05 '15 at 14:17

Adjacent products in a grid

4 Answers4