Adjacent products in a grid

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 le开发者_运维问答ft 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;

}

---

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.

---

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.

---

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>

---

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