I am trying to solve this problem: https://projecteuler.net/problem=11 However, this part confuses me:

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

what does in the same direction and up, down, left, right or diagonally mean? Is it just me or is the language vague here?

this is what I have tried so far:

long int prod{0}, n{20};

for(int i{0}; i <= n; i  ) {
    for(int j{0}; j <= n; j  ) {
        long int a{grid[i][j]}, b{grid[i 1][j 1]}, c{grid[i 2][j 2]}, d{grid[i 3][j 3]};
        if(prod < (a * b * c * d))
            prod = a * b * c * d;
    }
}

return prod;

With this function I satisfy the first demand but up down left right or diagonally? what does or mean there?

CodePudding user response：

A direction in the context of a grid is the geometrical space whose all points are on the same line.

If we take a point, then we can cross it with 4 different lines:

\   |   /
 \  |  /
  \ | /
   \|/
----*----
   /|\
  / | \
 /  |  \
/   |   \

So, how could we define these directions? There is a very simple way to do so:

• you loop the rows
  • you loop the columns
    • at the current point, you try to get 4 values, including the current point
      • downwards
      • rightwards
      • right-downwards
      • right-upwards

I say "try", which means that you will have to ignore quite a few possibilities due to the boundaries of your grid. Yet, it is a neat way to get all four directions:

int bestProduct = -1; //Assuming you have positives
for (int row = 0; row < n; row  ) {
    for (int column = 0; column < n; column  ) {
        int ignore = 0;
        int rowDir = 0;
        int colDir = 1;
        int product = grid[row][column];
        for (int index = 0; (!ignore) && (index < 3); index  ) {
            if (
                   (row   rowDir < 0) ||
                   (row   rowDir >= n) ||
                   (column   colDir < 0) ||
                   (column   colDir >= m)
               ) {
                ignore = 1;
            }
            else product *= grid[row   rowDir][column   colDir];
        }
        if ((!ignore) && (bestProduct < product)) bestProduct = product;
    }
}

This is not a full implementation, since you also need to do some work. You will need to continue with:

• converting the inner part of the second loop into a function except the if conditional that checks whether the product is higher than the best product so far
• remove that inner code and replace it with the function call
• call the function three more times, once for each other direction
• the other directions are:
  • 1: having a 1 colDir and 0 rowDir
  • 2: having a 1 colDir and 1 rowDir
  • 3: having a 1 colDir and -1 rowDir

I know it is more difficult to consider this partial solution, but it will help you a lot in the long run if you do the rest for yourself, as the ideas are all laid down here.

CodePudding user response：

You need to check each row, column, and diagonal of 4. This means you need to check:

from grid[i-4][j] to grid[i][j]  
from grid[i][j-4] to grid[i][j]  
from grid[i-4][j-4] to grid[i][j] (diagonal) 
from grid[i 4][j-4] to grid[i][j] (other diagonal)

Make sure to watch for the grid sides too as if you're on the very left, you'll need to look to the right