patterncppMinor
Project Euler 18/67: Maximum Sum from Top to Bottom of the Triangle
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.
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:
-
You should open your file directly from the constructor, and check whether there was a problem when you tried to open the file:
-
You can replace this condition:
You can use
-
I don't know why you chosed
The braces after the
-
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.