Problem Analysis
The heart of this problem is a counting question: how many distinct sub-rectangles fit inside an
H x W grid? The naive mental model is to slide every possible smaller rectangle across
every position, but there is a far cleaner way to see it. A grid of height H and width
W is bounded by H + 1 horizontal lines and W + 1 vertical
lines. Any rectangle is uniquely determined by choosing two of the horizontal lines (its top and
bottom edges) and two of the vertical lines (its left and right edges). Because the choice along
each axis is completely independent of the other, the total count factors into a product. This is
the structural insight that turns a two-dimensional search into something far smaller.
The number of ways to choose 2 items from n is the
binomial coefficient
C(n, 2) = n*(n-1)/2. Choosing 2 lines from H + 1 lines therefore gives
(H+1)*H/2, which is exactly the
triangular number
T(H) = H*(H+1)/2 - the running sum 1 + 2 + ... + H. So the total rectangle
count for an H x W grid is T(H) * T(W). With 3 x 2 this gives
T(3) * T(2) = 6 * 3 = 18, matching the worked example. This factored form is the key
observation: instead of enumerating all rectangles, we only need to find the pair of triangular
numbers whose product is closest to two million. Since the triangular numbers form a strictly
increasing sequence, we can iterate over one axis and use a
binary search
on the other, giving an O(max_side * log(max_side)) algorithm. The brute-force
alternative that literally sums over every sub-rectangle position is O(max_side^2)
in the outer loop with an additional O(H*W) inner cost per pair - correct, but far
slower, and useful mainly for illustrating the definition.
Solution Approach
Algorithm 0 - Brute-Force Position Counting (s0)
This approach counts rectangles exactly as the definition suggests. In
num_rectangles(height, width) I sum (height - h + 1) * (width - w + 1)
over every sub-rectangle dimension (h, w). The term (height - h + 1) is
the number of vertical positions a sub-rectangle of height h can occupy, and likewise
for width; multiplying and summing over all (h, w) yields the total. I then iterate
over every grid shape (height, width) and track the count closest to the target.
The Python version (p0085_s0.py) uses itertools.product to generate the
grid shapes and stores every result in a dictionary keyed by count, then selects the global best
with a single min(..., key=delta) call. The C version (p0085_s0.c)
performs the same nested summation but keeps only a running best_area and
best_delta, avoiding the memory overhead of a dictionary. Both versions break out
early once a count falls within max_error of the target; in C this early exit uses
goto done to escape both loops cleanly. This algorithm is instructive but expensive -
the inner double loop recomputes the count from scratch for every grid shape.
Algorithm 1 - Triangular-Number Binary Search (s1)
This approach exploits the factored formula count(H, W) = T(H) * T(W). I precompute
an array numbers where numbers[i] = T(i+1) for lengths from 1 up to
max_side - 1. Because
triangular numbers
increase monotonically, this array is sorted and supports
binary search.
In the Python version num_rectangles_along_axis computes T(length) by the
explicit running sum, while the C version uses the closed form length*(length+1)/2;
both yield the same sequence.
For each width w I read off num_width = T(w) and ask: what height
H makes T(H) * num_width closest to the target? That ideal satisfies
T(H) ~= target / num_width. I locate the insertion point of target /
num_width in the sorted array using bisect.bisect_left in Python or a hand-rolled
bisect_left in C. The closest triangular number must be one of the two neighbours of
that insertion point, so I evaluate both candidates, compute their products with
num_width, and update the running best. The same early-exit on max_error
applies, but now it triggers far sooner because each inner step is O(log n) rather
than a linear scan. The C version frees its allocated array before returning, and uses integer
division for target / num_width - acceptable here because the array neighbours bracket
the true closest value regardless of the small rounding from truncation.