Problem 215: Crack-free Walls

View on Project Euler

Project Euler Problem 215 Solution

EulerSolve provides an optimized solution for Project Euler Problem 215, Crack-free Walls, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

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

Problem 215 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int width = 32;
    int height = 10;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }

    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--width=", options.width) ||
            parse_int_after_prefix(arg, "--height=", options.height)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.width >= 2 && options.height >= 1;
}

std::vector<std::uint32_t> generate_rows(const int width) {
    std::vector<std::uint32_t> rows;

    const auto dfs = [&](auto&& self, int pos, std::uint32_t mask) -> void {
        if (pos == width) {
            rows.push_back(mask);
            return;
        }

        for (int brick : {2, 3}) {
            const int next = pos + brick;
            if (next > width) {
                continue;
            }
            std::uint32_t next_mask = mask;
            if (next < width) {
                next_mask |= (1U << next);
            }
            self(self, next, next_mask);
        }
    };

    dfs(dfs, 0, 0U);
    return rows;
}

u64 solve(const int width, const int height) {
    const std::vector<std::uint32_t> rows = generate_rows(width);
    const int n = static_cast<int>(rows.size());

    std::vector<std::vector<int>> compatible(static_cast<std::size_t>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((rows[static_cast<std::size_t>(i)] & rows[static_cast<std::size_t>(j)]) == 0U) {
                compatible[static_cast<std::size_t>(i)].push_back(j);
            }
        }
    }

    std::vector<u64> dp(static_cast<std::size_t>(n), 1ULL);

    for (int h = 1; h < height; ++h) {
        std::vector<u64> next(static_cast<std::size_t>(n), 0ULL);
        for (int i = 0; i < n; ++i) {
            u64 ways = 0;
            for (int j : compatible[static_cast<std::size_t>(i)]) {
                ways += dp[static_cast<std::size_t>(j)];
            }
            next[static_cast<std::size_t>(i)] = ways;
        }
        dp.swap(next);
    }

    u64 total = 0;
    for (u64 v : dp) {
        total += v;
    }
    return total;
}

bool run_checkpoints() {
    if (solve(9, 3) != 8ULL) {
        std::cerr << "Checkpoint failed for width=9,height=3" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.width, options.height) << '\n';
    return 0;
}

Python

# Problem 215: Crack-free Walls
# Count ways to build a 32-wide, 10-high wall with 2x1 and 3x1 bricks
# such that no vertical crack extends through two consecutive rows.

def solve():
    width = 32
    height = 10

    # Generate all valid row layouts as bitmasks of internal crack positions
    rows = []
    def gen(pos, mask):
        if pos == width:
            rows.append(mask)
            return
        for brick in (2, 3):
            nxt = pos + brick
            if nxt > width:
                continue
            nmask = mask
            if nxt < width:
                nmask |= (1 << nxt)
            gen(nxt, nmask)
    gen(0, 0)

    n = len(rows)
    # Build compatibility: two rows are compatible if they share no internal cracks
    compatible = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if (rows[i] & rows[j]) == 0:
                compatible[i].append(j)

    # DP: dp[i] = number of ways to end with row pattern i
    dp = [1] * n
    for _ in range(1, height):
        nxt = [0] * n
        for i in range(n):
            s = 0
            for j in compatible[i]:
                s += dp[j]
            nxt[i] = s
        dp = nxt

    print(sum(dp))

solve()

Java

public class Euler215 {
    public static void main(String[] args) {
        int width = 32, height = 10;
        java.util.List<Integer> rows = new java.util.ArrayList<>();
        genRows(0, 0, width, rows);
        int n = rows.size();
        int[][] compatible = new int[n][];
        for (int i = 0; i < n; i++) {
            java.util.List<Integer> comp = new java.util.ArrayList<>();
            for (int j = 0; j < n; j++)
                if ((rows.get(i) & rows.get(j)) == 0)
                    comp.add(j);
            compatible[i] = comp.stream().mapToInt(Integer::intValue).toArray();
        }
        long[] dp = new long[n];
        java.util.Arrays.fill(dp, 1L);
        for (int h = 1; h < height; h++) {
            long[] next = new long[n];
            for (int i = 0; i < n; i++) {
                long s = 0;
                for (int j : compatible[i])
                    s += dp[j];
                next[i] = s;
            }
            dp = next;
        }
        long total = 0;
        for (long v : dp)
            total += v;
        System.out.println(total);
    }

    static void genRows(int pos, int mask, int width, java.util.List<Integer> rows) {
        if (pos == width) {
            rows.add(mask);
            return;
        }
        for (int brick : new int[] { 2, 3 }) {
            int nxt = pos + brick;
            if (nxt > width)
                continue;
            int nmask = mask;
            if (nxt < width)
                nmask |= (1 << nxt);
            genRows(nxt, nmask, width, rows);
        }
    }
}