Max path sum algorithm

Question

This is for Project Euler question 18 and I'm looking for feedback on whether my algorithm is incorrect or whether I've just implemented it wrong (which I don't think is the case after some testing).

The question is to traverse the maximum path in a triangle from top to bottom.

                            75
                          95  64
                        17  47  82
                      18  35  87  10
                    20  04  82  47  65
                  19  01  23  75  03  34
                88  02  77  73  07  63  67
              99  65  04  28  06  16  70  92
            41  41  26  56  83  40  80  70  33
          41  48  72  33  47  32  37  16  94  29
        53  71  44  65  25  43  91  52  97  51  14
      70  11  33  28  77  73  17  78  39  68  17  57
    91  71  52  38  17  14  91  43  58  50  27  29  48
  63  66  04  68  89  53  67  30  73  16  69  87  40  31
04  62  98  27  23  09  70  98  73  93  38  53  60  04  23

Starting from the second bottom row, each value is its current value + max(left child, right child), which transforms each position in the tree to be its max path sum from that point.

#include <iostream>
#include <fstream>
#include <iterator>
#include <sstream>
#include <vector>

using namespace std;
using Tree = vector<vector<int>>;

void transform_mps(Tree& tree) {
    // start from bottom up, each node's value is node.val + max(left child, right child)
    // transforms tree such that each node is that node's max path sum
    for (int layer = tree.size() - 2; layer >= 0; --layer) {
        for (size_t pos = 0; pos < tree[layer].size(); ++pos) {
            tree[layer][pos] = tree[layer][pos] + max(tree[layer+1][pos], tree[layer+1][pos+1]);
        }
    }
}

int main(int argc, char* argv[]) {
    if (argc < 2) { cout << "Need to pass in file to read from\n"; return 1; }

    ifstream f {argv[1]};
    if (!f.is_open()) { cout << "Could not open file\n"; return 1; }

    Tree tree;
    string line;
    while (getline(f, line)) {
        istringstream is {line};
        tree.push_back(vector<int>(istream_iterator<int>(is), istream_iterator<int>()));
    }
    transform_mps(tree);
    int mps {tree[0][0]};
    cout << "Max path sum: " << mps << endl;
}

/********** leftovers from previous implementation, ignore
constexpr bool LEFT {false};
constexpr bool RIGHT {true};

int pathsum(Tree& tree, size_t layer, size_t pos, bool right) {
    int sum {};
    ++layer;    // next level
    for (; layer < tree.size(); ++layer) 
        if (right) sum += tree[layer][++pos];
        else sum += tree[layer][pos];
    return sum;
}
***********/

Answer 1

Looks good to me, algorithmically and syntactically. What makes you think it's wrong?

Stylistically, there are a few things you could improve:

• Don't using namespace std. It's more idiomatic and readable to explicitly qualify std::max, std::cout, etc., and it's not much more typing.

• Don't comment out dead code; delete it instead. ;)

• tree[layer][pos] = tree[layer][pos] + ...; should be simply
  tree[layer][pos] += ...;

And algorithmically, notice that if you start at the top of the tree and work downward, you don't need to store O(Rows²) numbers; you just need to store the previous row's sums, for a total space cost of O(Rows). (And then at the end you have Rows possible answers, and you pick the std::max_element of all of them.)

• This might be a Project Euler constraint; but in the Unix/Linux world, it's more traditional to get your input from stdin rather than reading a filename off the command line. (Most utility programs support both, of course. The only one I know of that doesn't is tr.) Combine that with the top-down approach, and you get a nice Unixy stream filter that makes just one single pass over the data.

Answer 2

That the tree is modified is not an issue for me. Your function takes the tree by non-const reference, and if you want to keep the original you can always "store" the original.

That you read from a file is not an issue either. The algorithm has been separated from the way that data was read in.

I would probably have gone around creating some nice OO DAG and then use depth-first or breadth-first search. But then mine would be more generic for DAGs in general.

Either way, in my solution I would return the path itself as well as the result, something yours does not do.