Detailed mathematical approach

Problem Summary

Let \(R(a,b)\) denote the number of rectangles that can be placed in an \(a \times b\) cross-hatched grid, where every unit square contains both diagonals. The implementations solve the cumulative quantity

$S(W,H)=\sum_{a=1}^{\min(W,H)}\sum_{b=1}^{\max(W,H)} R(a,b),$

so for the target instance we need \(S(47,43)\). The total is symmetric in the two dimensions, so the code immediately normalizes them to \(N=\min(W,H)\) and \(M=\max(W,H)\).

The count naturally splits into two families. Ordinary axis-aligned rectangles admit a direct combinatorial sum. Slanted rectangles, whose sides lie on the diagonal hatch lines, are handled by a 45-degree change of coordinates that turns the geometry into a box-counting problem on an integer lattice.

Mathematical Approach

Everything below is written for \(N \le M\). The crucial point is that the program is not solving a single-grid counting problem in isolation; it is summing rectangle counts over every smaller cross-hatched grid up to the target size.

What the total actually counts

The cumulative form matters because a rectangle that first appears in a small grid also appears in every larger grid that can contain it. The implementation exploits that viewpoint throughout: once it knows the smallest grid dimensions required by a rectangle, it can count all larger grids containing it in one multiplication instead of re-enumerating the rectangle for every grid size.

Axis-aligned rectangles

An ordinary \(a \times b\) grid contains

$\binom{a+1}{2}\binom{b+1}{2}$

axis-aligned rectangles, because we choose two horizontal grid lines and two vertical grid lines. Summing over all admissible sizes gives

$A(N,M)=\sum_{a=1}^{N}\sum_{b=1}^{M}\binom{a+1}{2}\binom{b+1}{2} =\left(\sum_{a=1}^{N}\binom{a+1}{2}\right)\left(\sum_{b=1}^{M}\binom{b+1}{2}\right) =\binom{N+2}{3}\binom{M+2}{3}.$

This is exactly the closed form that the implementations add to the answer before doing any geometric work on slanted rectangles.

Turning slanted rectangles into axis-aligned boxes

The slanted rectangles have sides parallel to the two diagonal directions of the hatching. The implementation parameterizes the relevant diagonal-intersection lattice by integers \(0 \le i \le 2N\) and \(0 \le j \le 2M\) with \(i+j\) even, then applies the linear map

$x=\frac{i+j}{2},\qquad y=\frac{i+2\sigma-j}{2},\qquad \sigma=M+3.$

The translation by \(\sigma\) only keeps the array indices positive; it does not alter the combinatorics. Under this map, the valid intersection points become the integer lattice points in the diamond-shaped region

$P_{N,M}=\{(x,y)\in\mathbb{Z}^2: 0\le x+y-\sigma\le 2N,\ 0\le x-y+\sigma\le 2M\}.$

In these new coordinates, every slanted rectangle in the original cross-hatched grid becomes an ordinary axis-aligned rectangle. That is the central mathematical reduction behind the code.

Detecting valid boxes with a 2D prefix sum

The implementations mark every point of \(P_{N,M}\) in a padded array and build a 2D prefix sum \(Q\). For a candidate box \(B=[l_x,r_x]\times[l_y,r_y]\), the number of marked lattice points inside is

$\operatorname{pts}(B)=Q(r_x,r_y)-Q(r_x,l_y-1)-Q(l_x-1,r_y)+Q(l_x-1,l_y-1).$

If the box lies completely inside the diamond, then every lattice point in the box is valid, so

$\operatorname{pts}(B)=(r_x-l_x+1)(r_y-l_y+1).$

This equality is the key invariant tested in the four nested loops. A candidate box contributes exactly when it is completely filled with marked points, which is equivalent to saying that the corresponding slanted rectangle is geometrically valid.

Recovering the smallest grid that can contain a slanted rectangle

Each valid transformed box corresponds to one slanted rectangle prototype. The implementation converts its extreme transformed coordinates back into the smallest ordinary grid dimensions that can contain it. If \(B=[l_x,r_x]\times[l_y,r_y]\), those minimal dimensions are

$h_{\min}=\left\lfloor\frac{r_x+r_y-\sigma-1}{2}\right\rfloor,\qquad w_{\min}=\left\lfloor\frac{r_x-l_y+\sigma+1}{2}\right\rfloor.$

The factor \(1/2\) appears because the transformed lattice measures diagonal half-steps while the grid dimensions are counted in unit squares. Once \(h_{\min}\) and \(w_{\min}\) are known, the same slanted rectangle appears in every cross-hatched grid with height at least \(h_{\min}\) and width at least \(w_{\min}\). Therefore its multiplicity in the cumulative sum is

$\bigl(N-h_{\min}+1\bigr)\bigl(M-w_{\min}+1\bigr).$

Worked example: the \(3\times 2\) checkpoint

After normalization, the checkpoint case uses \(N=2\) and \(M=3\). The axis-aligned subtotal is

$A(2,3)=\binom{4}{3}\binom{5}{3}=40.$

In the transformed plane, one of the smallest valid boxes corresponds to a slanted rectangle whose minimal container is \(1\times 2\). It is therefore counted in exactly four grid sizes: \(1\times 2\), \(1\times 3\), \(2\times 2\), and \(2\times 3\). That is precisely the multiplicity

$\bigl(2-1+1\bigr)\bigl(3-2+1\bigr)=4.$

When all valid boxes are swept, their multiplicities sum to 32. Adding the ordinary rectangles gives

$40+32=72,$

which is the checkpoint value used by the C++ and Python implementations.

How the Code Works

Normalize the dimensions and add the easy part

The C++, Python, and Java implementations first reorder the dimensions so the smaller one comes first. They then add the closed-form axis-aligned subtotal \(\binom{N+2}{3}\binom{M+2}{3}\) immediately.

Build the transformed lattice

Next, the implementation allocates a square integer array large enough to hold the translated diamond \(P_{N,M}\). Every admissible parity-matched pair \((i,j)\) is mapped to an integer lattice point, and a 2D prefix sum is computed over that marker array.

Sweep boxes and accumulate multiplicities

The remaining work is an exhaustive scan over all axis-aligned boxes in the transformed plane. For each box, the prefix sum determines in constant time whether the box is fully inside the valid diamond. If it is, the implementation recovers the minimal containing grid dimensions \((h_{\min},w_{\min})\), discards impossible cases, and adds the multiplicity \((N-h_{\min}+1)(M-w_{\min}+1)\) to the running total.

All three languages implement the same mathematics. The C++ and Python versions also expose the small \(3\times 2\) checkpoint, while the Java version directly evaluates the target instance.

Complexity Analysis

The closed-form axis-aligned part is \(O(1)\). Building the transformed marker array and its prefix sums costs \(O(M^2)\) time and \(O(M^2)\) space, because the array side length is \(2M+8\).

The dominant phase is the four-loop sweep over candidate boxes in the transformed plane, which is \(O(M^4)\). For the target instance \(M=47\), this is still easily practical. The overall algorithm is therefore \(O(M^4)\) time and \(O(M^2)\) space after normalization.

Footnotes and References

1. Problem page: Project Euler 147 - Rectangles in Cross-Hatched Grids
2. Rectangle: Wikipedia - Rectangle
3. Lattice point: Wikipedia - Lattice point
4. Prefix sum: Wikipedia - Prefix sum
5. Affine transformation: Wikipedia - Affine transformation
6. Binomial coefficient: Wikipedia - Binomial coefficient