# Project Euler 18/67: Maximum Path Sum Solution

I wrote my solution to Project Euler #18 and #67 in C++ (which I'm relatively new to), and was just wondering what everyone else thinks of it. It executes in 3-4ms and works flawlessly (even for triangles not given by the website). But I'm not a professional programmer or anything, so I wouldn't know if it's necessarily good or not. Anyone have any potential improvements?

The website's instructions:

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

   3
7 4
2 4 6
8 5 9 3


That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one hundred rows.

My code:

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

int main()
{
using namespace std;

clock_t starttim = clock();
//prog
vector<vector<int>> lines;

ifstream istrm("triangle.txt");
string line;
while (getline(istrm, line))
{
int num;
stringstream ss(line);
vector<int> curvec;
while (ss >> num)
{
curvec.push_back(num);
}
lines.push_back(curvec);
}

for (int currow = lines.size() - 1; currow >= 0; currow--)
{
if (currow != 0)
{
for (int curidx = 0; curidx <= lines[currow].size() - 2; curidx++)
{
int num1 = lines[currow][curidx];
int num2 = lines[currow][curidx + 1];
int greater = (num1 > num2 ? num1 : num2);
lines[currow - 1][curidx] += greater;
}
}
else cout << lines[0][0] << endl;
}

//endprog
cout << "Execution time - " << (((clock() - starttim) / (double)CLOCKS_PER_SEC) * 1000) << "ms." << endl;
system("PAUSE");
return 0;
}

• @Agawa001 it is a simple dynamic programming problem - not NP complete at all. And it's not a Hamiltonian path problem - you just need to find a path from the bottom of the triangle to the top. There is no requirement to visit all of the edges or all of the nodes. – ErikR Sep 4 '15 at 6:09
• @Agawa001 Please write all critiques in answers, no matter how trivial. – 200_success Sep 4 '15 at 6:27

This is pretty good code for a C++ beginner. I believe you got the right algorithm. Its running time is linear in the number of entries. You visit every element once; I don't believe it is possible to do better than that. Its memory usage is also linear in the number of entries. The memory usage, however, can be improved. Instead of processing the rows bottom-up, if you do it top-down, you can process the rows as you read them, keeping just two rows' worth of data at any given time.

It would be slightly more elegant to implement a simple abstraction layer for parsing the input. I would also avoid hard-coding the filename.

Writing using namespace std; is considered bad practice.

The if-else inside the for-loop is pointless. It just means that currow >= 0 was a poor termination condition.

I find the "cur…" prefixes on your variable names annoying. What's "curve c"? What's "currow" — does it rhyme with "furrow"? As for "curidx", how about just i?

The timing printout should go to standard error to avoid contaminating the output. You can avoid the (double) cast by writing 1000.0 to trigger floating-point arithmetic.

#include <ctime>

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

template<typename T>
class Input {
public:
Input<T>(std::istream &in) : in(in) {}

bool next_row(std::vector<T> &entries) {
entries.clear();
std::string line;
if (!std::getline(this->in, line)) {
return false;
}
std::stringstream ss(line);
for (T n; ss >> n; ) {
entries.push_back(n);
}
return true;
}

private:
std::istream &in;
};

int main(int argc, char *argv[]) {
std::clock_t start_time = clock();

// Input from either a file or STDIN
// http://stackoverflow.com/a/2159469/1157100
std::shared_ptr<std::istream> input(&std::cin, [](...) -> void {});
if (argc >= 2 && std::string("-") != argv[1]) {
input.reset(new std::ifstream(argv[1]));
}
Input<int> triangle(*input);

// For each entry in each row "b", add the greater of the two entries in
// row "a" above.  Row "b" then contains the maximum path sum from the
// top up to that point.
std::vector<int> a, b;
for (triangle.next_row(a); triangle.next_row(b); a = b) {
b[0] += a[0];
for (std::vector<int>::size_type i = 1; i < a.size(); i++) {
b[i] += std::max(a[i - 1], a[i]);
}
b[b.size() - 1] += a[a.size() - 1];
}
std::cout << *std::max_element(a.begin(), a.end()) << std::endl;

std::cerr << "Execution time - "
<< ((std::clock() - start_time) * 1000.0 / CLOCKS_PER_SEC)
<< "ms." << std::endl;
}

• I normally wouldn't do "Using namespace std;" if this were a big project. But for something this small i don't think its that bad. And when i was writing this i just meant cur means current. (Curvec means current vector, currow means current row, curidx means current index, etc. i put curidx instead of i because it seems more readable). Also, since im new to c++ i have no idea how to write templates(or even use them) or i would implement that. Thanks for the feedback.. ill keep it in mind as i continue to learn (Reading c++ primer 5th edition.. seems good so far) – Potato Sep 4 '15 at 8:03
• Your code is great, formatted well, and perfect-functioning. Except that, there is no need to do insider loops, and the memory issue can be parried without saturating it with horrible amounts of data.

• What do I understand from the least informations I received: the XML structure of the triangle is unique, meaning two digit numbers intermediated by one character space like this example with two lines:

<digit> <digit> <CR> <LF>

<digit> <digit> <space> <digit> <digit>


So, if the file size is $n$, $k$th (last) line length should be a triangular number of an arithmetic series of distance $3$ (two digits number+space+two digits linefeed) starting from 4 until $k$.

1. Calculating $k$:

For a regular standard arithmetic series of distance 1, last line length is

$k=\sqrt{2(n+1)}$

For our case:

• $square=\sqrt{\frac{2(n+1)}{3}}$

• If $square$ is perfect square $k=3*square$.

• If $square$ is not perect square

• $k=3*(square)+\frac{2(n+1)-3*square(square+1)}{square+1}$

This last number $k$ should be perfect integer except if there is some XML misformatting.

ifstream istrm("triangle.txt");


use

FILE*istrm=fopen("triangle.txt","r");


The library stdio.h must be included in the header.

3. Position the file cursor to the last but one line:

fseek(istrm, 0, SEEK_END);
int n=ftell(istrm),k;
double square=pow(2*(n+1)/3,0.5);
fseek(istrm, -(k= (square==(int)square) ?3*square: (int) 3*(int)square-2+ ( 2*(n+1)-3*((int)square*((int)square+1)) )/((int)square+1) ), SEEK_END);

4. Subtract 3 from the value of $k$ regularily until you come accross $k=4$ then stop! Meanwhile, just use a two-dimensional array and add it to the next (upper) line values until you finish calculating.

for(int curidx=0;k>3;curidx++)
{
int num1;
if(curidx>k/3)
fseek(istrmm, -(k=k-3)-k-5+(curidx=0), SEEK_CUR);
fscanf(istrmm,"%d",&num1);
lines[0][curidx] = num1+lines[1][curidx];

if(curidx>0)
{
int greater = (lines[0][curidx] > lines[0][curidx-1] ? lines[0][curidx] : lines[0][curidx-1]);
lines[1][curidx-1] = greater;
}
}

5. About variable declaration: don't declare the same variables repeatedly, just initialize it once:

int num1

int greater

for(int num1,greater,curidx=0;k>3;curidx++)


The overall code should look like:

using namespace std;

clock_t starttim = clock();

//lines is two dimensional
int* lines[2];

//open a file located in C:

FILE*istrmm=fopen("c:\\triangle.txt","r");

fseek(istrmm, 0, SEEK_END);
int n=ftell(istrmm),k;
double square=pow(2*(n+1)/3,0.5);
fseek(istrmm, -(k= (square==(int)square) ?3*square: (int) 3*(int)square-2+ ( 2*(n+1)-3*((int)square*((int)square+1)) )/((int)square+1) ), SEEK_END);

//initialize
lines[0]=(int*)malloc(sizeof(int)*k);
lines[1]=(int*)malloc(sizeof(int)*(k-1));
memset(*lines,0,4*k);
memset(*(lines+1),0,4*(k-1));

// one pass loop
for(int num1,greater,curidx=0;k>3;curidx++)
{
// no need to num2, and greater should be declared once.
if(curidx>k/3)
fseek(istrmm, -(k=k-3)-k-5+(curidx=0), SEEK_CUR);
//printf("%d   \n",ftell(istrmm));
fscanf(istrmm,"%d",&num1);
//printf("%d    %d   \n\n",num1,ftell(istrmm));
lines[0][curidx] = num1+lines[1][curidx];

if(curidx>0)
{
greater = (lines[0][curidx] > lines[0][curidx-1] ? lines[0][curidx] : lines[0][curidx-1]);
lines[1][curidx-1] = greater;
}
}

printf("%d ",(lines[0][1] > lines[0][0] ? lines[0][1] : lines[0][0]));
cout << "Execution time - " << (((clock() - starttim) / (double)CLOCKS_PER_SEC) * 1000) << "ms." << endl;
system("PAUSE");
return 0;

• I suggest you submit this code for code review and see what the community has to say. – ErikR Sep 4 '15 at 14:13
• @ErikR i v just misplaced fseek command, which didnt match my second note before, no serious problem to review there. – Abr001am Sep 4 '15 at 14:34
• I'm not saying that you code doesn't work - I'm saying that I think you would get some valuable feedback on to write it better. Unfortunately these comment boxes are not suitable for making code review comments on code review answers. – ErikR Sep 4 '15 at 15:36
• I dont think memory is much of an issue though. I just ran a 1000 line triangle and it used only 4mb at most. – Potato Sep 4 '15 at 17:11
• This could be a much better post if 1. you formatted your examples nicer; 2. included an explanation why X is better than Y (for example, in your 2nd point) – janos Sep 6 '15 at 8:45