notes.html

problem 18 · 62 lines

<article>
<h3>Problem Analysis</h3>
<p>
    The task is to find, among all top-to-bottom paths through a number triangle, the one whose sum
    of visited values is largest. At each step we descend from a cell to one of the two cells
    immediately below it. A triangle with N rows therefore has 2^(N-1) distinct paths - 16,384 for
    the 15-row triangle here, and an astronomical 2^99 for the 100-row variant in Problem 67. A
    brute-force enumeration of every path quickly becomes intractable, so I needed a smarter method.
  </p>
<p>
    The unlocking observation is that this 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 from any cell down to the base is that cell's value plus the better of the two best
    paths starting from its two children. Because the best overall path must also be the best path
    through every sub-triangle it crosses, I can solve the problem with
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> -
    a technique that builds up an answer from solutions to smaller, overlapping sub-problems instead
    of recomputing them. By computing "the maximum sum reachable from this cell down to the base" for
    every cell, starting at the bottom and working upward, the apex eventually holds the global
    answer. Each cell is visited exactly once, so the algorithm runs in
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity" rel="noopener noreferrer" target="_blank">O(N^2)</a>
    time (proportional to the number of cells) - a dramatic improvement over the exponential
    enumeration, and one that scales effortlessly to the 100-row case.
  </p>
<h3>Solution Approach</h3>
<h4>Bottom-Up Reduction of the Triangle (Python and C)</h4>
<p>
    Both <code>p0018_s0.py</code> and <code>p0018_s0.c</code> implement the same algorithm. I first
    parse the triangle from a multiline string into a two-dimensional array of integers, then
    collapse it row by row from the bottom up.
  </p>
<p>
    The collapse works as follows. I look at the last two rows. For each position <code>i</code> in
    the second-to-last row, I add the larger of its two children - the cells at indices
    <code>i</code> and <code>i+1</code> in the last row - to the value already stored there. After
    this, every cell in the second-to-last row holds "the maximum sum reachable from here to the
    base". I then discard the last row and repeat. When only the single apex cell remains, it holds
    the global maximum. This is the direct expression of the
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Optimal_substructure" rel="noopener noreferrer" target="_blank">optimal-substructure</a>
    recurrence: <code>best(cell) = value(cell) + max(best(left child), best(right child))</code>,
    evaluated bottom-up so that each child's answer is already known when its parent is processed.
    The whole reduction touches each of the N(N+1)/2 cells once, which is why it runs in
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Time_complexity" rel="noopener noreferrer" target="_blank">O(N^2)</a>
    time.
  </p>
<p>
    In Python the inner step is a single
    <a class="reference-source" href="https://en.wikipedia.org/wiki/List_comprehension" rel="noopener noreferrer" target="_blank">list comprehension</a>:
    <code>triangle[-2] = [v + max(triangle[-1][i], triangle[-1][i + 1]) for i, v in enumerate(triangle[-2])]</code>,
    followed by <code>del triangle[-1]</code> to shrink the structure. I call
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Object_copying#Deep_copy" rel="noopener noreferrer" target="_blank">deep copy</a>
    (<code>copy.deepcopy</code>) first so that the caller's triangle is never mutated - important
    because the benchmark harness calls <code>solve</code> repeatedly with the same data. In C I
    perform the update in place on <code>triangle[current_rows - 2]</code> and simply decrement
    <code>current_rows</code> rather than freeing rows mid-loop; this is cache-friendly and avoids
    repeated allocation. The C parser counts rows by scanning for newlines, makes a mutable copy of
    the input (<a class="reference-source" href="https://en.wikipedia.org/wiki/C_string_handling#strtok" rel="noopener noreferrer" target="_blank">strtok</a>
    modifies its argument), and allocates each row to its exact length via a count-then-fill pass.
    All allocations are freed after the result is computed.
  </p>
</article>