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 
#include 
#include 
#include 
#include 
#include 

int main()
{
    using namespace std;

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

    ifstream istrm("triangle.txt");
    string line;
    while (getline(istrm, line))
    {
        int num;
        stringstream ss(line);
        vector 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  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;
}

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 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

template
class Input {
  public:
    Input(std::istream &in) : in(in) {}

    bool next_row(std::vector &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 ∈
};

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 input(&std::cin, [](...) -> void {});
    if (argc >= 2 && std::string("-") != argv[1]) {
        input.reset(new std::ifstream(argv[1]));
    }
    Input 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 a, b;
    for (triangle.next_row(a); triangle.next_row(b); a = b) {
        b[0] += a[0];
        for (std::vector::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;
}

StackExchange Code Review Q#103739, answer score: 3