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

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