# Project Euler Problem 11: Largest product in a grid

Here is my implementation to project Euler Problem 11. I did this problem a bit later, when I learned how to input from a txt file. The problem context can be seen here. I did add "\n" to the end of each line, after copying the numbers into a txt file, I'm not sure of any other way to do that. Any other improvements anyone can think of?

#include <fstream>
#include <iostream>
#include <vector>
#include <sstream>
#include <string>

//splitting stream into ints.
std::vector<int> split(std::string line){
std::stringstream ss (line);
std::vector<int> result;
std::string num;
while(std::getline(ss, num, ' '))
result.push_back(std::stoi(num));
return result;
}
//comparing all int's that are horizontally next to each other
unsigned long long Horizontal(int a, int b, std::vector<std::vector<int>> grid){
if(b < grid[a].size()-3){
return (grid[a][b] * grid[a][b+1] * grid[a][b+2] * grid[a][b+3]);
}
}
//comparing all int's that are vertically next to each other
unsigned long long Vertical(int a, int  b, std::vector<std::vector<int>> grid){
if(a < grid.size()-3){
return (grid[a][b] * grid[a+1][b] * grid[a+2][b] * grid[a+3][b]);
}
}
//all int's that are diagonally(forward) next to each other
unsigned long long ForDiag(int a, int b, std::vector<std::vector<int>>grid){
if (a < grid.size()-3 && b < grid[a].size()-3){
return (grid[a][b] * grid[a+1][b+1] * grid[a+2][b+2] * grid[a+3][b+3]);
}
}
//all int's that are diagonally(backward) next to each outher
unsigned long long BackDiag(int a, int b, std::vector<std::vector<int>>grid){
b+=3; // b needs to be 3 larger for this function
if(a < grid.size()-3 && b < grid[a].size()){
return (grid[a][b] * grid[a+1][b-1] * grid[a+2][b-2] * grid[a+3][b-3]);
}
}

//Calls the calculation functions, and compares them for the largest.
unsigned long long Largest(std::vector<std::vector<int>> grid ){
int gwidth = grid.size();
int glength = grid.size();
unsigned long long largest = 0;

for(int a = 0; a < gwidth; ++a){
for(int b = 0; b < glength; ++b){
largest = std::max(largest,Horizontal(a,b,grid));
largest = std::max(largest,Vertical(a,b,grid));
largest = std::max(largest,ForDiag(a,b,grid));
largest = std::max(largest,BackDiag(a,b,grid));

}
}
return largest;
}

int main(){
std::vector<std::vector<int>> grid;

//opening file.
std::ifstream nums;
nums.open("grid.txt");
std::string row;

//Calling function, and pushing back into the vector
while(std::getline(nums, row, '\n')){
grid.push_back(split(row));
}

std::cout << Largest(grid);

}

• My answer to your previous question about const& still applies to your std::vector parameters. – Jamal Apr 16 '14 at 16:19
• I suggest activating warning -Wreturn-type . – SylvainD Apr 16 '14 at 16:37

Your functions returning a unsigned long long are missing a return which leads to undefined behavior (more details on this question). You could throw an exception to handle this or you could just return 0.

Not a real issue and mostly a matter of personal preference but the way you check that you are not going out of the bounds of the array could be written in a more natural way.

To check that index b + 3 is in the array, I'd rather read b + 3 < a.size() than b < a.size() - 3.

Even more unusual is the pre-increment in the case of BackDiag() : you add 3 to b and then you consider b - 3.

Once your code re-written to take into account these comments, it looks like :

unsigned long long Horizontal(int a, int b, std::vector<std::vector<int>> grid){
return (b + 3 < grid[a].size()) ?
(grid[a][b] * grid[a][b+1] * grid[a][b+2] * grid[a][b+3]) :
0;
}
//comparing all int's that are vertically next to each other
unsigned long long Vertical(int a, int  b, std::vector<std::vector<int>> grid){
return (a + 3 < grid.size()) ?
(grid[a][b] * grid[a+1][b] * grid[a+2][b] * grid[a+3][b]) :
0;
}
unsigned long long ForDiag(int a, int b, std::vector<std::vector<int>>grid){
return (a + 3 < grid.size() && b + 3 < grid[a].size()) ?
(grid[a][b] * grid[a+1][b+1] * grid[a+2][b+2] * grid[a+3][b+3]) :
0;
}
unsigned long long BackDiag(int a, int b, std::vector<std::vector<int>>grid){
return (a + 3 < grid.size() && b + 3 < grid[a].size()) ?
(grid[a][b+3] * grid[a+1][b+2] * grid[a+2][b+1] * grid[a+3][b]) :
0;
}


Now, one thing to notice is that this good is basically always the same. You should try to write a generic function that you can reuse.

The signature would be something like :

unsigned long long computeProduct(int a, int b, int incrA, int incrB, std::vector<std::vector<int>>grid)


One improvement you can make is to flatten the matrix to 1D and just use larger offsets. This will speed your code up quite a bit.

//Create 1D vector
std::ifstream infile("grid.txt");
std::vector<int> flatmatrix;
while(!infile.eof())
{
double numtemp = 0;
infile >> numtemp;
flatmatrix.push_back(numtemp);
}

//Function to return the largest product as per problem description
//This is hardcoded for 20 X 20, but it shouldn't be too hard to adapt to take different sizes.
int MaxProduct(const std::vector<int>& matrix2)
{
long temp = 0;
long result2 = 0;
size_t size = matrix2.size();
for(int i = 0; i < size; i++)
{
temp = matrix2[i];
//right
if(i % 20 < 17)
{
temp = matrix2[i] * matrix2[i + 1] * matrix2[i + 2] * matrix2[i + 3];
result2 = (temp > result2 ? temp : result2);
}
//down
if((i + 60) < 400 && ((int)(i / 20)) % 20 < 17)
{
temp = matrix2[i] * matrix2[i + 20] * matrix2[i + 40] * matrix2[i + 60];
result2 = (temp > result2 ? temp : result2);
}
//left
if(i % 20 > 2)
{
temp = matrix2[i] * matrix2[i - 1] * matrix2[i - 2] * matrix2[i - 3];
result2 = (temp > result2 ? temp : result2);
}
//up
if((i - 60) >= 0 && ((int)(i / 20)) % 20 > 2)
{
temp = matrix2[i] * matrix2[i - 20] * matrix2[i - 40] * matrix2[i - 60];
result2 = (temp > result2 ? temp : result2);
}
//down,right
if(i % 20 < 17 && (i + 60) < 400 && ((int)(i / 20)) % 20 < 17)
{
temp = matrix2[i] * matrix2[(i + 20) + 1] * matrix2[(i + 40) + 2] * matrix2[(i + 60) + 3];
result2 = (temp > result2 ? temp : result2);
}
//down,left
if(i % 20 > 2 && (i + 60) < 400 && ((int)(i / 20)) % 20 < 17)
{
temp = matrix2[i] * matrix2[(i + 20) - 1] * matrix2[(i + 40) - 2] * matrix2[(i + 60) - 3];
result2 = (temp > result2 ? temp : result2);
}
//up,right
if(i % 20 < 17 && (i - 60) > -1 && ((int)(i / 20)) % 20 > 2)
{
temp = matrix2[i] * matrix2[(i - 20) + 1] * matrix2[(i - 40) + 2] * matrix2[(i - 60) + 3];
result2 = (temp > result2 ? temp : result2);
}
//up,left
if(i % 20 > 2 && (i - 60) > -1 && ((int)(i / 20)) % 20 > 2)
{
temp = matrix2[i] * matrix2[(i - 20) - 1] * matrix2[(i - 40) - 2] * matrix2[(i - 60) - 3];
result2 = (temp > result2 ? temp : result2);
}
}
return result2;
}


For future reference your split function can be simplified quite a bit:

std::vector<int> split(std::string line)
{
std::stringstream ss (line);
std::vector<int> result;
int num;
while(ss >> num)
result.push_back(num);
return result;
}

• I already provided a simpler split in the previous question, but they simply didn't keep it for some reason :/ – Morwenn Apr 16 '14 at 20:12