notes.html
problem 67 · 15 lines
<article>
<h3>Problem Analysis</h3>
<p>This problem asks for the maximum-sum path from the apex of a triangle of integers down to its base, where at each step I may step only to one of the two numbers directly below. With 100 rows there are 2<sup>99</sup> distinct top-to-bottom paths, so trying every route - brute force - is hopeless. The problem statement makes the point explicitly: even at a trillion paths per second, exhaustive search would take longer than the age of the universe. The exercise is really about recognising that a far smarter method exists.</p>
<p>The crucial observation is that the problem has <a class="reference-source" href="https://en.wikipedia.org/wiki/Optimal_substructure" rel="noopener noreferrer" target="_blank">optimal substructure</a>: the best path passing through any given cell equals that cell's value plus the better of the two best paths through its two children below. Because the answer for the whole is built from optimal answers to smaller, overlapping sub-problems, this is exactly the setting where <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> (DP) applies - solving each sub-problem once, storing its result, and reusing it instead of recomputing. The triangle can also be viewed as a <a class="reference-source" href="https://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noopener noreferrer" target="_blank">directed acyclic graph</a> - a network of nodes connected by one-way edges that never loop back - and finding a maximum-weight path through such a graph is a textbook <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> problem. Since each of the roughly n(n+1)/2 cells is visited exactly once, the algorithm runs in <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity" rel="noopener noreferrer" target="_blank">O(n<sup>2</sup>)</a> time - about 5,000 operations for n = 100, which is effectively instantaneous.</p>
<h3>Solution Approach</h3>
<h4>Bottom-Up Triangle Fold (Python and C)</h4>
<p>The Python and C solutions implement one and the same algorithm; they differ only in syntax and in how they manage memory. I chose a <em>bottom-up</em> formulation - starting from the base cases (the last row) and working upward to the answer - rather than recursing from the top down. This sidesteps recursion overhead and removes any need for an explicit cache, because the base cases are simply the cells themselves and the merged values accumulate naturally as I climb.</p>
<p><strong>Step 1 - Parse the input.</strong> The triangle is a text file, one row per line, with space-separated integers; row <code>i</code> holds <code>i+1</code> numbers. I read the file and split it into a list of lists of integers (Python's <code>text2triangle</code>) or a heap-allocated array of arrays (C's <code>text2triangle</code>), indexed as <code>triangle[row][col]</code>. The C parser walks the buffer twice in spirit - first counting rows, then allocating each row to its exact length and filling it with <code>atoi</code>.</p>
<p><strong>Step 2 - Deep copy.</strong> The fold mutates the triangle, so I copy it first to leave the parsed data intact and keep <code>max_path_sum_triangle</code> free of side effects on its input. Python uses <code>copy.deepcopy</code>; C allocates fresh rows and copies them with <code>memcpy</code>.</p>
<p><strong>Step 3 - Fold from the bottom.</strong> While more than one row remains, I update the second-to-last row by adding to each entry the larger of its two children in the last row, then discard the last row. In Python this is a single expressive line:<br/>
<code>triangle[-2] = [v + max(triangle[-1][i], triangle[-1][i + 1]) for i, v in enumerate(triangle[-2])]</code><br/>
followed by <code>del triangle[-1]</code>. In C I write the explicit loop, choose the larger child with a ternary expression (<code>left > right ? left : right</code>), and <code>free</code> the discarded row immediately after it is merged.</p>
<p><strong>Step 4 - Read off the answer.</strong> When the loop ends, exactly one cell remains: <code>triangle[0][0]</code> holds the maximum path sum, 7273.</p>
</article>