notes.html

problem 82 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
We must find the cheapest path through an 80x80 grid of integers, beginning at any cell in the leftmost column and ending at any cell in the rightmost column, where each move steps right, up, or down (but never left). This generalises Problem 81, where movement was restricted to right and down only. The freedom to move both up and down within a column changes the structure of the problem: while in a column we may detour vertically by any number of cells before stepping right, paying for every cell we traverse on the way. That vertical freedom defeats a naive two-direction sweep, because the optimal route into a given cell may arrive from far above or far below it.
</p>
<p>
The right tool here is <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a> (DP) - a method that solves a problem by breaking it into overlapping sub-problems, solving each once, and reusing the stored results. The sub-problem I define is: "given a cell, what is the minimum total cost to reach the right edge starting from that cell?" The observation that makes the problem tractable is that a vertical detour within a single column is just a <a class="reference-source" href="https://en.wikipedia.org/wiki/Prefix_sum" rel="noopener noreferrer" target="_blank">range sum</a> over consecutive cells of that column. This converts the 2-D, three-direction path problem into a sequence of independent 1-D minimisations, one per column. Processing columns from right to left, each column-reduction step costs O(n^2) (for every destination row, scan every target row with the range sum folded in), and there are n columns, giving an overall time complexity of O(n^3). For n=80 that is roughly 512,000 operations - trivially fast.
</p>
<h3>Solution Approach</h3>
<h4>Column-Reduction Dynamic Programming (Solution 0)</h4>
<p>
Both the C and Python files implement the same algorithm, which I call "column reduction." The matrix begins holding raw cell values. After I process column <code>c</code>, every entry in column <code>c</code> holds the minimum total cost to travel from that cell rightward to any cell on the right edge. I sweep columns from right to left, so by the time I reach a column, the column immediately to its right is already fully solved.
</p>
<p>
The core routine is <code>reduce_column(col)</code>, which reads the already-solved column <code>col</code> and writes results into column <code>col - 1</code>. For each destination row <code>row</code> in the left column, I consider every possible target row <code>target</code> in the right column. To travel from <code>(row, col-1)</code> to <code>(target, col)</code>, I must traverse vertically through every cell between <code>row</code> and <code>target</code> within column <code>col-1</code>, then step right. The cost is therefore the <a class="reference-source" href="https://en.wikipedia.org/wiki/Prefix_sum" rel="noopener noreferrer" target="_blank">range sum</a> of the cells in <code>col-1</code> from <code>min(row, target)</code> to <code>max(row, target)</code> inclusive, plus the already-stored best cost at <code>(target, col)</code>. I take the minimum of that cost over all target rows and store it as the new value at <code>(row, col-1)</code>.
</p>
<p>
A subtlety worth noting: the range sum always includes the cell <code>(row, col-1)</code> itself, so the starting cell is counted exactly once, and a self-target (<code>row == target</code>) correctly contributes just that single cell. Once all columns have been reduced down to column 0, the answer is simply the minimum value over column 0, because each entry there already encodes the full optimal cost from that starting cell to the right edge.
</p>
<p>
The C version stores the grid in a static <code>matrix[MAX_N][MAX_N]</code> and recomputes the range sum with an inner loop over the cell indices, accumulating into <code>range_sum</code>. The Python version expresses the same logic with nested generator expressions inside <code>min()</code> and <code>sum()</code>. Both compute every new column value into a temporary buffer (<code>new_entries</code> in both) and only then write them back into the matrix - this avoids corrupting values still needed within the same pass. The two implementations are algorithmically identical; they differ only in language idiom and runtime.
</p>
</article>