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

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 <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>

//function by jesyspa
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;
}
int main(){

std::vector<std::vector<int>> 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 <= a; b++){
if(grid[a][b] > grid[a][b+1]){
grid[a-1][b] += grid[a][b];
}
else{
grid[a-1][b] += grid[a][b+1];
}
}
}
std::cout << grid[0][0];
}

-

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

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

• 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<int> split(const std::string& line){
std::stringstream ss(line);
return {
std::istream_iterator<int>{ss},
std::istream_iterator<int>{}
};
}


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<int>) 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<int> instances:

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

-

Not a really fancy comment but :

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


can easily be rewritten

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


Also, your function and algorithm deserve more documentation.

-

One thing I see is that split()'s parameter should be passed by const& as it's not being modified within the function. This is how objects should be passed if they're not to be modified, preventing an unnecessary copy of read-only data.

split(std::string const& line) {}

-