Problem Analysis
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 commutative. So I only need to examine horizontal, vertical, and the two diagonal orientations. This immediately halves the work.
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 num_adjacent cells fits both rightward and
downward, then all four runs stay inside the grid. This turns the whole problem into a
brute-force search:
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.
Solution Approach
Single-Pass Anchor Scan (Python and C)
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 dim - num_adjacent
inclusive. That bound is the crucial correctness detail: it guarantees that a run of length
num_adjacent never walks off the right or bottom edge in any of the four directions.
For each anchor I maintain four running products, all initialised to 1, and update all of them inside
a single loop over the offset i from 0 to num_adjacent - 1:
- Horizontal:
grid[x][y + i]- fixed row, advancing column. - Vertical:
grid[x + i][y]- fixed column, advancing row. - Main diagonal:
grid[x + i][y + i]- top-left to bottom-right. - Anti-diagonal:
grid[x + num_adjacent - 1 - i][y + i]- starts at the bottom row of the run and walks upward as the column advances, covering the bottom-left to top-right direction.
The anti-diagonal needs the starting row offset of num_adjacent - 1, which is still in
bounds precisely because x itself was capped at dim - num_adjacent. 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 if (... > best) comparisons and four long long
accumulators; the Python version expresses the same logic as a
generator expression
fed to the built-in max().
The most interesting language-specific difference is how Python handles the four accumulators inside a
generator expression.
Because a
generator expression
cannot contain assignment statements, I "reset" the four products by iterating once over a
single-element tuple for horizontal, vertical, diagonal_1, diagonal_2 in ((1, 1, 1, 1),),
and then re-bind those same names on each step of i 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.