Project Euler 18/67: Maximum Path Sum Solution

Question

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;
}

Answer 1

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;
}

Answer 2

• 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.

2. instead of:

   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;