Comment on page
Largest Sum of a Path in a Triangle

Given a file consisting a pascals-like triangle of integers separated by spaces, return the sum of the path with the largest sum, as well as the final column index in the triangle. A path can only iterate down to the next level below to its child. Each parent shares 2 adjacent children in the level below. e.g. in the second row parent 2 shares children 2 and 3 and parent 3 shares shares children 3 and 4.
Note: integers can be >9 and <0.
Visually:
     1
    2 3 
   2 3 4 
  2 3 5 7  
 2 3 4 2 1 
6 6 4 8 3 2
Actually:
1
2 3
2 3 4
2 3 5 7
2 3 4 2 1
6 6 4 8 3 2
output:
25 3
Explanation: The sum of the max path is 25, and the column it end with is @index 3, which contains integer 8. The reason why we want to return the column index is because we can use it as information to backtrace back up the tree and return the actual path. Observe:
1
      3 
       4 
        7  
       2 
      8
This is done by taking the number at said column and then selecting the maximum of one of its two parents.
The Idea:
We can structure the information into a binary tree then do a path traversal to the leaf node, but in my opinion this would be a lot more difficult to parse, we can just use BFS iteratively.
First I parse the information into an indexable 2 dimensional vector. Then I begin the BFS procedure using an object of type Node that will carries information about the particular index. cur_sum is preferably important because it allows be to dynamically refer back to the previous sum. This works because the associative property of addition tells us that 2 + 3 + 5 = 3 + 2 + 5, i.e. permutations don't matter. The row and col information is used to refer to the next index in the 2d array. I know for a fact that it will be in the next row down, same col and an additional column forward.
vector<int> parse_line(const string &line, const char delimitor = ' ')
{
    vector<int> line_ints;
    stringstream ss(line);
    string cur_int;
​
    while (getline(ss, cur_int, delimitor)) {
        int to_int = stoi(cur_int.c_str());
        line_ints.push_back(to_int);
    }
    return line_ints;
}
​
vector<vector<int>> parse_file(const string &f_path)
{
    vector<vector<int>> triangle;
    vector<int> temp;
​
    ifstream infile(f_path);
    if (infile.good()) {
        string cur_line;
        while (getline(infile, cur_line)) {
            triangle.push_back(parse_line(cur_line));
        }
    }
    return triangle;
}
​
struct Node
{
    int num, row, col, cur_sum;;
};
​
pair<int, int> max_tri_sum(const string &f_path)
{
    vector<vector<int>> all_data = parse_file(f_path);
​
    int cur_max = INT_MIN;
    int cur_max_col_i = 0;
    queue<Node> q;
​
    int cur_data = all_data[0][0];
    int cur_row = 0;
    int cur_col = 0;
    int cur_sum = cur_data;
​
    q.push(Node{ cur_data, cur_row, cur_col, cur_sum });
​
    while (!q.empty()) {
        Node cur_front = q.front();
        q.pop();
​
        if (cur_max < cur_front.cur_sum) {
            cur_max = cur_front.cur_sum;
            cur_max_col_i = cur_front.col;
        }
​
        if (cur_front.row + 1 < all_data.size()) {
            cur_data = all_data[cur_front.row + 1][cur_front.col];
            cur_row = cur_front.row + 1;
            cur_col = cur_front.col;
            cur_sum = cur_data + cur_front.cur_sum;
​
            q.push(Node{ cur_data, cur_row, cur_col, cur_sum });
​
            cur_data = all_data[cur_front.row + 1][cur_front.col + 1];
            cur_row = cur_front.row + 1;
            cur_col = cur_front.col + 1;
            cur_sum = cur_data + cur_front.cur_sum;
​
            q.push(Node{ cur_data, cur_row, cur_col, cur_sum });
        }
    }
​
    return {cur_max, cur_max_col_i};
}
​
int main()
{
    pair<int, int> sum_col = max_tri_sum("../infile/triangle.txt");
    cout << sum_col.first << " "  << sum_col.second << endl;
}
Maximum Product in Matrix
Linked List Tree
Last modified 4yr ago