Project Euler Problem 11: Largest product in a grid

Question

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[0].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);
}

• Jamal: My answer to your previous question about const& still applies to your std::vector parameters.
• SylvainD: I suggest activating warning -Wreturn-type .

Answer 1

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)

Answer 2

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;
}

• Morwenn: I already provided a simpler split in the previous question, but they simply didn't keep it for some reason :/