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?
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:
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:
if conditional that checks whether the product is higher than the best product so farcolDir and 0 rowDircolDir and 1 rowDircolDir and -1 rowDirI 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.
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