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