Skip to main content
Code Review

Return to Question

Reformatted tree and clarified the challenge
Source Link
200_success
200_success
  • 144.2k
  • 22
  • 188
  • 473

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

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

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

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
Renamed function to more accurately reflect its purpose, moved redundant function down
Source Link
LemonPi
LemonPi
  • 393
  • 2
  • 13
#include <iostream>
#include <fstream>
#include <iterator>
#include <sstream>
#include <vector>

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

constexpr bool LEFT {false};
constexpr bool RIGHT {true};

intvoid pathsumtransform_mps(Tree& tree, size_t layer, size_t pos, bool right) {
    int sum {};
    ++layer;    // next level
start from bottom up, foreach (;node's layervalue <is treenode.size(); ++layer) 
       val if+ max(right) sum += tree[layer][++pos];
        else sum += tree[layer][pos];
    returnleft sum;
}

intchild, max_pathsum(Tree&right treechild) {
    // starttransforms fromtree bottomsuch up,that each node's valuenode is node.valthat +node's max(left child, rightpath child)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]);
        }
    }
    return tree[0][0];
}

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 {max_pathsum(tree)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;
}
***********/

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

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

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

int max_pathsum(Tree& tree) {
    // start from bottom up, each node's value is node.val + max(left child, right child)
    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]);
        }
    }
    return tree[0][0];
}

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

    int mps {max_pathsum(tree)};
    cout << "Max path sum: " << mps << endl;
}

#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;
}
***********/
Post Reopened by Quaxton Hale, ChrisWue, Simon Forsberg, syb0rg, rolfl
make working code clear.
Source Link
rolfl
rolfl
  • 97.5k
  • 17
  • 218
  • 418

My idea is that going right or left reduces the triangle by one layer, and either shedsStarting from the leftmost column by going rightsecond bottom row, or the rightmost diagonal by going left. So the way to get the maximum sumeach value is to lose the least atits current value + max(left child, right child), which transforms each step. I do this by comparingposition in the tree to be its max path sum of the leftmost column and rightmost diagonal from the current position, then going whichever direction loses the leastthat point.

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

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

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

int max_pathsum(Tree& tree) {
    int sum {};
// start from bottom size_tup, poseach {};node's value //is posnode.val inside+ amax(left layerchild, 0 isright leftmostchild)
    for (size_tint layer = 0; layer < tree.size(); ++layer) {
    - 2; layer >= sum0; +=--layer) tree[layer][pos];{
        // going right would lose the straight left path, while going left would lose straight left
      for (size_t ifpos (pathsum(tree,= layer,0; pos, LEFT) < pathsumtree[layer].size(tree, layer, pos, RIGHT); ++pos) {
            ++pos;
 tree[layer][pos] = tree[layer][pos] + max(tree[layer+1][pos], tree[layer+1][pos+1]);
  // else don't need to change position}
    }
    return sum;tree[0][0];
}

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

    int mps {max_pathsum(tree)};
    cout << "Max path sum: " << mps << endl;
}

**EDIT**
Remade max_pathsum as I thought of a much better algorithm(which works). The hint from vnp pushed me in the right direction.
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.
int max_pathsum(Tree& tree) {
    // start from bottom up, each node's value is node.val + max(left child, right child)
    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]);
        }
    }
    return tree[0][0];
}

My idea is that going right or left reduces the triangle by one layer, and either sheds the leftmost column by going right, or the rightmost diagonal by going left. So the way to get the maximum sum is to lose the least at each step. I do this by comparing the sum of the leftmost column and rightmost diagonal from the current position, then going whichever direction loses the least.

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

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

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

int max_pathsum(Tree& tree) {
    int sum {};
    size_t pos {};  // pos inside a layer, 0 is leftmost
    for (size_t layer = 0; layer < tree.size(); ++layer) {
        sum += tree[layer][pos];
        // going right would lose the straight left path, while going left would lose straight left
        if (pathsum(tree, layer, pos, LEFT) < pathsum(tree, layer, pos, RIGHT)) 
            ++pos;
        // else don't need to change position
    }
    return sum;
}

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

    int mps {max_pathsum(tree)};
    cout << "Max path sum: " << mps << endl;
}

**EDIT**
Remade max_pathsum as I thought of a much better algorithm(which works). The hint from vnp pushed me in the right direction.
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.
int max_pathsum(Tree& tree) {
    // start from bottom up, each node's value is node.val + max(left child, right child)
    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]);
        }
    }
    return tree[0][0];
}

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

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

int max_pathsum(Tree& tree) {
    // start from bottom up, each node's value is node.val + max(left child, right child)
    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]);
        }
    }
    return tree[0][0];
}

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

    int mps {max_pathsum(tree)};
    cout << "Max path sum: " << mps << endl;
}
Edited to include working algorithm
Source Link
LemonPi
LemonPi
  • 393
  • 2
  • 13
Post Undeleted by LemonPi
Post Deleted by LemonPi
Post Closed as "Not suitable for this site" by vnp, Quaxton Hale, user52292, Heslacher, Martin R
added link to PE problem #18
Source Link
Martin R
Martin R
  • 23.5k
  • 2
  • 36
  • 92
edited tags
Link
Jamal
Jamal
  • 34.9k
  • 13
  • 133
  • 237
added 18 characters in body; edited title
Source Link
Jamal
Jamal
  • 34.9k
  • 13
  • 133
  • 237
Source Link
LemonPi
LemonPi
  • 393
  • 2
  • 13