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;

}

Answer 1

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.