5
\$\begingroup\$

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

}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ My answer to your previous question about const& still applies to your std::vector parameters. \$\endgroup\$
    – Jamal
    Commented Apr 16, 2014 at 16:19
  • \$\begingroup\$ I suggest activating warning -Wreturn-type . \$\endgroup\$
    – SylvainD
    Commented Apr 16, 2014 at 16:37

2 Answers 2

5
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ I already provided a simpler split in the previous question, but they simply didn't keep it for some reason :/ \$\endgroup\$
    – Morwenn
    Commented Apr 16, 2014 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.