Project Euler #11 - Largest product in a grid C++

Question

https://projecteuler.net/problem=11

Any thoughts? Also, when measuring with chrono it takes supposedly 4 ms to compute, is this reliable value? Previous problems took little longer to compute so I'm suspicious, and I'm still a beginner so I'm not sure how long it "should" take or if chrono is good for measuring computing time.

#include <fstream>
#include <vector>
#include <string>

int main()
{
    std::ifstream input("grid.txt");
    std::vector<std::vector<int>> numbers(20, std::vector<int>(20));

    char c;
    std::string str;

    int row{ 0 };
    int column{ 0 };
    //convert from ascii to decimal
    while (input.get(c))
    {
        str += c;
        if (((int)c - 48 == -16) || ((int)c - 48 == -38)) //space or new line
        {
            numbers[row][column] = std::stoi(str);
            column++;
            str.clear();
        }
        if (column == 20)
        {
            row++;
            column = 0;
        }
    }
    int product;
    int maxProduct{ 0 };
    for (int i = 0; i < 20; i++)
    {
        product = 0;
        for (int j = 0; j < 20; j++)
        {
            // horizontal
            if (j >= 3)
            {
                product = numbers[i][j] * numbers[i][j - 1] * numbers[i][j - 2] * numbers[i][j - 3];
                if (product > maxProduct)
                    maxProduct = product;
            }

            if (j <= 16)
            {
                product = numbers[i][j] * numbers[i][j + 1] * numbers[i][j + 2] * numbers[i][j + 3];
                if (product > maxProduct)
                    maxProduct = product;
            }
            // vertical
            if (i >= 3)
            {
                product = numbers[i][j] * numbers[i - 1][j] * numbers[i - 2][j] * numbers[i - 3][j];
                if (product > maxProduct)
                    maxProduct = product;
            }

            if (i <= 16)
            {
                product = numbers[i][j] * numbers[i + 1][j] * numbers[i + 2][j] * numbers[i + 3][j];
                if (product > maxProduct)
                    maxProduct = product;
            }
            // diagonal
            if (i >= 3 && j >= 3)
            {
                product = numbers[i][j] * numbers[i - 1][j - 1] * numbers[i - 2][j - 2] * numbers[i - 3][j - 3];
                if (product > maxProduct)
                    maxProduct = product;
            }
            if (i <= 16 && j <= 16)
            {
                product = numbers[i][j] * numbers[i + 1][j + 1] * numbers[i + 2][j + 2] * numbers[i + 3][j + 3];
                if (product > maxProduct)
                    maxProduct = product;
            }
            if (i >= 3 && j <= 16)
            {
                product = numbers[i][j] * numbers[i - 1][j + 1] * numbers[i - 2][j + 2] * numbers[i - 3][j + 3];
                if (product > maxProduct)
                    maxProduct = product;
            }
            if (i <= 16 && j >= 3)
            {
                product = numbers[i][j] * numbers[i + 1][j - 1] * numbers[i + 2][j - 2] * numbers[i + 3][j - 3];
                if (product > maxProduct)
                    maxProduct = product;
            }
        }
    }

    return 0;
}

Answer 1

Input

Using magic numbers like 48 and -16 makes your code very cryptic and hard to understand. Consider comparing with the characters instead.

Algorithm / Logic

I think two things that could really simplify your code are:

1. Limit the loops iterations from [0, 0] to [16, 16]. This will make you avoid some unnecessary checks.

2. Only try to get the 4 numbers in the forward direction. There is no need to check in the backward direction as well since it's already checked in the forward direction.

Answer 2

I have some general observations about problem solving that don't directly relate to the algorithm:

• You have a lot of constants in the code, this means that it would be difficult to test with, say, a smaller input to verify that your algorithm is working correctly. A better solution would be to generalize the input to arbitrarily sized matrices and subsequence lengths. It doesn't take much more code to do, and it is way easier to test with. I also find that generalizing the problem often yields a better understanding of the concrete problem as well.

• In the same vane, you place both your input parsing and calculation in main. This makes separating the input method from the algorithm impossible so it makes testing difficult. Split these into 1 or 2 separate functions.

• To empirically determine how efficient your algorithm is, it is helps to be able to vary the input size and see how the time varies as a result. This is because there are potentially many factors at play, such as the (fixed) cost of parsing the input, any cache misses that may (or may not occur), and times where the operating system may preempt the execution of your program in favor of another one. To get an accurate picture, you will need a fairly large sample size, so repeat the calculation a few million times and take the average.