notes.html
problem 11 · 64 lines
<article>
<h3>Problem Analysis</h3>
<p>
This problem has essentially no number theory in it - it is a search problem over a small, fixed
two-dimensional array. The task is to find the largest product of four consecutive values along any
of the eight compass directions in a 20x20 grid. The first key observation is that of those eight
directions, only four are genuinely distinct: a run going left is the same set of numbers as the
matching run going right, just multiplied in the opposite order, and multiplication is
<a class="reference-source" href="https://en.wikipedia.org/wiki/Commutative_property" rel="noopener noreferrer" target="_blank">commutative</a>.
So I only need to examine horizontal, vertical, and the two diagonal orientations. This immediately
halves the work.
</p>
<p>
The second observation is what keeps the code clean: every one of those four orientations can be
anchored at a single cell and walked in a single forward direction. If I pick an anchor cell and
restrict it to positions where a run of <code>num_adjacent</code> cells fits both rightward and
downward, then all four runs stay inside the grid. This turns the whole problem into a
<a class="reference-source" href="https://en.wikipedia.org/wiki/Brute-force_search" rel="noopener noreferrer" target="_blank">brute-force search</a>:
enumerate every valid anchor, compute four products, take the maximum. For a grid of side N and a
run length k there are (N - k + 1)^2 valid anchors, and at each anchor I do O(k) multiplications,
giving an overall complexity of O((N - k + 1)^2 * k), which simplifies to roughly O(N^2 * k). For
N = 20 and k = 4 that is only a few thousand operations - trivially fast, so there is no incentive
to look for anything cleverer.
</p>
<h3>Solution Approach</h3>
<h4>Single-Pass Anchor Scan (Python and C)</h4>
<p>
Both files implement the identical algorithm; only the language differs. I iterate over every valid
anchor cell (x, y), where "valid" means x and y each range from 0 to <code>dim - num_adjacent</code>
inclusive. That bound is the crucial correctness detail: it guarantees that a run of length
<code>num_adjacent</code> never walks off the right or bottom edge in any of the four directions.
</p>
<p>
For each anchor I maintain four running products, all initialised to 1, and update all of them inside
a single loop over the offset <code>i</code> from 0 to <code>num_adjacent - 1</code>:
</p>
<ul>
<li><strong>Horizontal:</strong> <code>grid[x][y + i]</code> - fixed row, advancing column.</li>
<li><strong>Vertical:</strong> <code>grid[x + i][y]</code> - fixed column, advancing row.</li>
<li><strong>Main diagonal:</strong> <code>grid[x + i][y + i]</code> - top-left to bottom-right.</li>
<li><strong>Anti-diagonal:</strong> <code>grid[x + num_adjacent - 1 - i][y + i]</code> - starts at the bottom row of the run and walks upward as the column advances, covering the bottom-left to top-right direction.</li>
</ul>
<p>
The anti-diagonal needs the starting row offset of <code>num_adjacent - 1</code>, which is still in
bounds precisely because x itself was capped at <code>dim - num_adjacent</code>. After the inner loop
finishes, I compare all four products against the running best and keep the largest. The C version
does this with explicit <code>if (... > best)</code> comparisons and four <code>long long</code>
accumulators; the Python version expresses the same logic as a
<a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#generator-expressions" rel="noopener noreferrer" target="_blank">generator expression</a>
fed to the built-in <code>max()</code>.
</p>
<p>
The most interesting language-specific difference is how Python handles the four accumulators inside a
<a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#generator-expressions" rel="noopener noreferrer" target="_blank">generator expression</a>.
Because a
<a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#generator-expressions" rel="noopener noreferrer" target="_blank">generator expression</a>
cannot contain assignment statements, I "reset" the four products by iterating once over a
single-element tuple <code>for horizontal, vertical, diagonal_1, diagonal_2 in ((1, 1, 1, 1),)</code>,
and then re-bind those same names on each step of <code>i</code> by iterating over another
single-element tuple holding the updated products. The C version simply declares four local variables
and multiplies them in place - the more natural form in an imperative language.
</p>
</article>