C++ ProjectEuler #11
c++
Solution
your problem are your range checks:
example:
// DOWN
if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0))
should be:
// DOWN
//if ((row+1 < 20 ) && (row+2 < 20 ) && (row+3 < 20 ))
//which still contains redundant comparisons (as pointed out by Blastfurnace),
//and thus can be can be simplified to :
if( row + 3 < 20 )
If you have random results on each run for a program, and you dont use concurrency, random number generators or something like that, most likely that randomness i caused by undefined behaviour like reading unallocated memory or reading using unintialised variables.
Problem
I'm trying to solve the 11th problem on ProjectEuler.net. The goal for this problem is to find the largest product in a 20x20 grid of 4 adjacent numbers in any direction (up, down, right, left, diagonal). I'm using the BigInteger library because I don't know how large will the numbers be and I don't want an overflow - but I think this might be the problem. Every time I restart the program I get a different answer. :/ I also tried to use an unsigned long long int just to see what will happen - the answer remained the same. This is the code (Nothing complicated; I just test every element in the grid to see if it has 3 adjacent numbers in any direction, compute the product and set it as the new largest if it is larger than the previous one. On the end I print the largest product.): ``` //NO.11 #include <iostream> #include <BigIntegerLibrary.hh> #include <windows.h> int main() { int grid[20][20] = { { 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8}, {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0}, {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65}, {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 2, 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, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21}, {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72}, {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95}, {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92}, {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57}, {86, 56, 0, 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, 4, 89, 55, 40}, { 4, 52, 8, 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, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69}, { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 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, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54}, { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48} }; BigInteger biggestProduct = 0; //unsigned long long int biggestProduct = 0; for (int row = 0; row < 20; row++) { for (int col = 0; col < 20; col++) { BigInteger product; //unsigned long long int product; //std::cout << grid[row][col] << ":" << std::endl; system("pause>nul"); //UP if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0)) { product = grid[row][col] * grid[row-1][col] * grid[row-2][col] * grid[row-3][col]; //std::cout << " U: " << grid[row][col] << "*" << grid[row-1][col] << "*" << grid[row-2][col] << "*" << grid[row-3][col] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //DOWN if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0)) { product = grid[row][col] * grid[row+1][col] * grid[row+2][col] * grid[row+3][col]; //std::cout << " D: " << grid[row][col] << "*" << grid[row+1][col] << "*" << grid[row+2][col] << "*" << grid[row+3][col] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //RIGHT if ((col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) { product = grid[row][col] * grid[row][col+1] * grid[row][col+2] * grid[row][col+3]; //std::cout << " R: " << grid[row][col] << "*" << grid[row][col+1] << "*" << grid[row][col+2] << "*" << grid[row][col+3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //LEFT if ((col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) { product = grid[row][col] * grid[row][col-1] * grid[row][col-2] * grid[row][col-3]; //std::cout << " L: " << grid[row][col] << "*" << grid[row][col-1] << "*" << grid[row][col-2] << "*" << grid[row][col-3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //UP-RIGHT if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0) && (col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) { product = grid[row][col] * grid[row-1][col+1] * grid[row-2][col+2] * grid[row-3][col+3]; //std::cout << " U-R: " << grid[row][col] << "*" << grid[row-1][col+1] << "*" << grid[row-2][col+2] << "*" << grid[row-3][col+3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //DOWN-RIGHT if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0) && (col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) { product = grid[row][col] * grid[row+1][col+1] * grid[row+2][col+2] * grid[row+3][col+3]; //std::cout << " D-R: " << grid[row][col] << "*" << grid[row+1][col+1] << "*" << grid[row+2][col+2] << "*" << grid[row+3][col+3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //DOWN-LEFT if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0) && (col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) { product = grid[row][col] * grid[row+1][col-1] * grid[row+2][col-2] * grid[row+3][col-3]; //std::cout << " D-L: " << grid[row][col] << "*" << grid[row+1][col-1] << "*" << grid[row+2][col-2] << "*" << grid[row+3][col-3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } //UP-LEFT if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0) && (col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) { product = grid[row][col] * grid[row-1][col-1] * grid[row-2][col-2] * grid[row-3][col-3]; //std::cout << " U-L: " << grid[row][col] << "*" << grid[row-1][col-1] << "*" << grid[row-2][col-2] << "*" << grid[row-3][col-3] << "= \t" << product << std::endl; system("pause>nul"); if (product > biggestProduct) biggestProduct = product; } } } std::cout << biggestProduct; return 0; } ``` Does anyone know what's wrong?