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

Question

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];
 }
 }
 }
 //Our answer
 std::cout << grid[0][0];
}

Answer 1

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

Answer 2

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.

Answer 3

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) {}