Can't understand the requirement of the problem. (ProjectEuler problem: 11)

user_14725633 0
Viewed 94

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?

math c algorithm c++
2 Answers

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.

user_4365600

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

user_186008330
Related