HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Project Euler 18/67: Maximum Sum from Top to Bottom of the Triangle

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
themaximumtopbottomtriangleprojecteulersumfrom

Problem

This is my attempt at Project 18/67 of Project Euler. You can see the problem information, and obtain the needed txt file from here.

I had some help with the split function, and help on how to use an vector to do this. I would love any other feedback on this code.

#include 
#include 
#include 
#include 
#include 

//function by jesyspa
std::vector split(std::string line){
    std::stringstream ss (line);
    std::vector result;
    std::string num;
    while(std::getline(ss, num, ','))
        result.push_back(std::stoi(num));
    return result;
}
int main(){

    std::vector> grid;

    //inputing triangle fule
    std::ifstream nums;
    nums.open("triangle.txt");
    std::string row;
    //Calling function, and pushing back into the vector
    while(std::getline(nums, row, '\n')){
        grid.push_back(split(row));
    }
    //term is one shorter then grid
    int term = grid.back().size() - 1;

    //This loop add's the larger of two bottom numbers, with the number above the first of the two.
    for(int a = term; a >= 1; a--){
        for(int b = 0; b  grid[a][b+1]){
                grid[a-1][b] += grid[a][b];
            }
            else{
                grid[a-1][b] += grid[a][b+1];
            }
        }
    }
    //Our answer
    std::cout << grid[0][0];
}

Solution

Generally speaking, I find that your code is clear. I just have a few remarks:

-
You should order your headers in alhabetical order. It will help you to quickly check whether some header is already included or not in you plan to add some:

#include 
#include 
#include 
#include 
#include 


-
You should open your file directly from the constructor, and check whether there was a problem when you tried to open the file:

std::ifstream nums.open("triangle.txt");
if (not nums.good())
{
    throw std::runtime_error("Could not open the file.");
}


-
You can replace this condition:

if(grid[a][b] > grid[a][b+1]){
    grid[a-1][b] += grid[a][b];
}
else{
    grid[a-1][b] += grid[a][b+1];
}


You can use std::max instead:

grid[a-1][b] += std::max(grid[a][b], grid[a][b+1]);


-
I don't know why you chosed , as a separator since the original file uses a space as separator. Had you kept the space as a separator in your file, you vould have rewritten the function split with std::istream_iterator, with an int template parameter:

std::vector split(const std::string& line){
    std::stringstream ss(line);
    return {
        std::istream_iterator{ss},
        std::istream_iterator{}
    };
}


The braces after the return correspond to list initialization. The rules for list initialization are pretty complex; the curly braces after return mean that an instance of the anounced return type (std::vector) should be created with the arguments between the braces. In our case, the chosen constructor is the one that matches the best two istream_iterator instances:

template
vector(InputIt first, InputIt last,
       const Allocator& alloc=Allocator());

Code Snippets

#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
std::ifstream nums.open("triangle.txt");
if (not nums.good())
{
    throw std::runtime_error("Could not open the file.");
}
if(grid[a][b] > grid[a][b+1]){
    grid[a-1][b] += grid[a][b];
}
else{
    grid[a-1][b] += grid[a][b+1];
}
grid[a-1][b] += std::max(grid[a][b], grid[a][b+1]);
std::vector<int> split(const std::string& line){
    std::stringstream ss(line);
    return {
        std::istream_iterator<int>{ss},
        std::istream_iterator<int>{}
    };
}

Context

StackExchange Code Review Q#47272, answer score: 6

Revisions (0)

No revisions yet.