Detailed mathematical approach

Problem Summary

Let \(W(w,h)\) denote the number of walls of width \(w\) and height \(h\) built from horizontal bricks of lengths 2 and 3. Problem 215 asks for \(W(32,10)\). Every brick joint inside a row creates a vertical crack position somewhere in \(\{1,2,\dots,w-1\}\), and the wall is considered crack-free only when these interior joints never continue from one layer into the next.

The essential simplification is that the legality of a new row depends only on the crack pattern of the row immediately below it. Once each possible row is encoded, the two-dimensional wall becomes a finite-state counting problem on a compatibility graph.

Mathematical Approach

The implementations do not reason about individual bricks after the row-generation stage. They work with row states, compatibility between states, and a recurrence over the wall height.

Rows as compositions of the width

A single row is an ordered sum

$w=b_1+b_2+\cdots+b_t,\qquad b_i\in\{2,3\}.$

So a valid row is exactly a composition of \(w\) using parts 2 and 3. If \(R(w)\) is the number of such rows, then the first brick is either 2 or 3, which gives the recurrence

$R(0)=1,\qquad R(1)=0,\qquad R(2)=1,\qquad R(w)=R(w-2)+R(w-3)\quad (w\ge 3).$

For the target width \(32\), this yields \(R(32)=3329\) distinct row types. The code generates them by depth-first search rather than by evaluating the recurrence directly, but both viewpoints describe the same state space.

For a row \(b_1,\dots,b_t\), its internal crack set is

$C=\{b_1,\ b_1+b_2,\ \dots,\ b_1+\cdots+b_{t-1}\}\subseteq\{1,\dots,w-1\}.$

These partial sums are the only geometric information that matters once the row has been built.

Why adjacent rows control the crack condition

A crack can propagate upward only if the row above and the row below both have a joint at the same horizontal position. Therefore the standard crack-free condition is enforced by requiring every pair of neighboring rows to have disjoint internal crack sets. In symbols, rows \(r\) and \(s\) may be stacked only when

$C(r)\cap C(s)=\varnothing.$

This local rule is exactly what the implementations test. It replaces the geometry of the whole wall by a pairwise invariant on consecutive rows.

Bitmasks and the compatibility graph

The code stores a row by a bitmask rather than by an explicit set. If bit \(x\) is 1, then there is a crack at position \(x\). Equivalently,

$m(r)=\sum_{x\in C(r)}2^x.$

Two rows are compatible precisely when they have no common set bit:

$m(r)\mathbin{\&}m(s)=0.$

This turns the collection of rows into a graph: each row type is a vertex, and an edge joins two vertices exactly when the corresponding rows may appear consecutively in the wall.

The height recurrence

Let \(F_h(i)\) be the number of crack-free walls of height \(h\) whose top row is the \(i\)-th row state. The first row can be chosen freely, so

$F_1(i)=1.$

For each additional layer, the new top row must be compatible with the previous top row, hence

$F_h(i)=\sum_{j\sim i} F_{h-1}(j)\qquad (h\ge 2),$

where \(j\sim i\) means that row states \(j\) and \(i\) are compatible. The final count is

$W(w,h)=\sum_i F_h(i).$

Equivalently, if \(A\) is the adjacency matrix of the compatibility graph and \(\mathbf{1}\) is the all-ones vector, then

$W(w,h)=\mathbf{1}^T A^{h-1}\mathbf{1},$

but the implementations evaluate this by iterative dynamic programming, not by matrix exponentiation.

Worked example: \(W(9,3)=8\)

For width \(9\), the possible rows are

$2+2+2+3,\quad 2+2+3+2,\quad 2+3+2+2,\quad 3+2+2+2,\quad 3+3+3.$

Their crack sets are

$\{2,4,6\},\quad \{2,4,7\},\quad \{2,5,7\},\quad \{3,5,7\},\quad \{3,6\}.$

Checking intersections shows that the only compatible pairs are

$\{2,4,6\}\leftrightarrow\{3,5,7\},\qquad \{2,4,7\}\leftrightarrow\{3,6\},\qquad \{2,5,7\}\leftrightarrow\{3,6\}.$

At height 1, every row contributes 1. At height 2, the state counts are just the vertex degrees: \(1,1,1,1,2\). Applying the recurrence once more gives height-3 counts \(1,2,2,1,2\), whose sum is

$W(9,3)=8.$

This is exactly the checkpoint used in the implementations, and it shows concretely how the graph recurrence replaces brute-force wall construction.

How the Code Works

Generating the row states

The C++, Python, and Java implementations recursively advance a cursor from the left end of the row. Each recursive step adds either a length-2 brick or a length-3 brick. Whenever a brick ends before the right boundary, the corresponding crack bit is set in the row mask. Reaching position \(32\) emits one complete row state.

Precomputing compatible neighbors

Once all row masks have been generated, the implementation tests every pair of states. A pair is stored as compatible if their bitwise AND is zero. This produces an adjacency list for the compatibility graph, so the dynamic program does not need to repeat the crack test for every layer.

Rolling the dynamic program over height

The DP starts with one way to end at each row state when the wall has height 1. For each of the remaining 9 layers, a new array is filled by summing the counts of all compatible predecessor states. Only the previous layer and the next layer are kept, so the memory usage stays linear in the number of row states rather than growing with the height.

Complexity Analysis

Let \(N=R(w)\) be the number of row states and let \(E\) be the number of stored compatible transitions. Generating the rows visits each valid composition once, so it is \(O(N)\) up to small constant factors. Building the compatibility lists by testing every pair of row masks is \(O(N^2)\).

The height DP performs one sum over all compatible transitions for each extra layer, so its cost is \(O(hE)\). In the worst case this is \(O(hN^2)\), although the actual graph is much sparser than a complete graph. The memory footprint is \(O(N+E)\): the row masks, the adjacency structure, and two DP layers. For the target width \(32\), the main one-time burden is the compatibility graph on \(3329\) row states; the height \(10\) recurrence itself is then straightforward.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=215
2. Integer compositions: Wikipedia - Composition (combinatorics)
3. Dynamic programming: Wikipedia - Dynamic programming
4. Bitwise operations: Wikipedia - Bitwise operation
5. Transfer-matrix method: Wikipedia - Transfer-matrix method