Problem 215: Crack-free Walls

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

A wall of width $w$ and height $h$ consists of $h$ layers of height $1$, each a row of bricks of size $2\times1$ and $3\times1$, horizontal times vertical: the bricks of a layer have the lengths $2$ and $3$ and fill the width exactly. Two horizontally adjacent bricks leave a gap between them, and the wall is crack-free if gaps never line up in consecutive layers: no gap may lie at the same position as a gap of the next layer, which would form a running crack. With $W(w,h)$ the number of crack-free walls, the statement gives $W(9,3)=8$ and asks for $W(32,10)$. ^[1] Bricklayers follow the same rule: the vertical joints between bricks, the perpends, should not continue from one course into the next. ^[2]

The whole solution in one sentence: describe every layer by the positions of its gaps, note that a wall is crack-free exactly when every two consecutive layers have no gap position in common, and count the walls layer by layer, giving each possible top layer the sum of the counts of all layers that may lie directly below it.

Mathematical Approach

We describe layers and the rule for neighbouring layers, count walls layer by layer, check this by hand on the widths $8$ and $9$, and then study which layers fit together.

1. One layer

Reading a layer from left to right gives the lengths of its bricks, an ordered sum of $2$s and $3$s equal to $w$. Width $8$ has four layers: $2+2+2+2$, $2+3+3$, $3+2+3$ and $3+3+2$. Let $R(w)$ be the number of layers of width $w$. The first brick has length $2$ or $3$, and the bricks after it form a layer of width $w-2$ or $w-3$, so

$$R(w)=R(w-2)+R(w-3)\quad(w\ge3),$$

with $R(0)=1$ for the empty layer that ends the recursion, $R(1)=0$ and $R(2)=1$. For $w=0,1,\dots,12$ this gives $1,0,1,1,1,2,2,3,4,5,7,9,12$, and $R(32)=3329$. For $w\ge2$ these are the Padovan numbers, $R(w)=P(w-2)$, where $P(n)$ counts the ordered sums of $2$s and $3$s equal to $n+2$; the ratio of consecutive terms tends to the plastic number $\rho\approx1.3247$, the real root of $x^3=x+1$, so $R(w)$ grows roughly like $\rho^{w}$. ^[3]

2. Gaps

Measure positions from the left end of the wall. A layer with the brick lengths $b_1,\dots,b_k$ has its gaps at the partial sums $b_1$, $b_1+b_2$, …, $b_1+\dots+b_{k-1}$, its gap set $C$; the ends $0$ and $w$ of the wall are not gaps. The five layers of width $9$ are $2+2+2+3$, $2+2+3+2$, $2+3+2+2$, $3+2+2+2$ and $3+3+3$, with the gap sets $\{2,4,6\}$, $\{2,4,7\}$, $\{2,5,7\}$, $\{3,5,7\}$ and $\{3,6\}$. A layer can be read back from its gap set, since its bricks are the distances between neighbouring elements of $\{0\}\cup C\cup\{w\}$. As every brick is at least $2$ long, the gaps lie between $2$ and $w-2$, and two gaps of one layer are at least $2$ apart.

3. Only neighbouring layers matter

A running crack is a gap of one layer together with a gap of the next layer at the same position. Hence a wall with the layers $L_1,\dots,L_h$, from bottom to top, is crack-free exactly when

$$C(L_i)\cap C(L_{i+1})=\varnothing\qquad(1\le i\lt h).$$

We call two layers compatible, and write $K\sim L$, when their gap sets are disjoint. The relation is symmetric and says nothing about layers further apart: gaps of $L_i$ and $L_{i+2}$ may line up, since that position lies inside a brick of $L_{i+1}$. For example, $2+2+2+3\sim3+2+2+2$, while $2+2+2+3$ and $3+3+3$ share the gap $6$.

4. Counting layer by layer

Let $F_t(L)$ be the number of crack-free walls of height $t$ with the top layer $L$, so $F_1(L)=1$. For $t\ge2$, removing the top layer $L$ of such a wall leaves a crack-free wall of height $t-1$ whose top layer $M$ satisfies $M\sim L$, and putting $L$ back on top undoes this, because $M$, $L$ is the only new pair of neighbouring layers. Hence

$$F_t(L)=\sum_{M\sim L}F_{t-1}(M),\qquad W(w,h)=\sum_{L}F_h(L).$$

Computing all values $F_t$ from the stored values $F_{t-1}$, instead of building the walls one by one, is dynamic programming. ^[4] In the language of graphs, join two layers by a line when they are compatible; a crack-free wall of height $h$ is then a walk with $h-1$ steps along lines, in which layers may repeat: the wall $2+2+2+3$, $3+2+2+2$, $2+2+2+3$ of width $9$ goes along one line and back. If $A$ is the adjacency matrix, with $A_{KL}=1$ for $K\sim L$ and $A_{KL}=0$ otherwise, the entry $(K,L)$ of $A^{n}$ counts the walks with $n$ steps from $K$ to $L$, ^[5] so with the column $\mathbf 1$ of ones

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

and each round of the recurrence multiplies the column of the values $F_{t-1}$ by $A$. Counting with powers of a matrix of allowed transitions is the transfer-matrix method of enumerative combinatorics. ^[6]

5. Width 8

The four layers of width $8$ have the gap sets $\{2,4,6\}$, $\{2,5\}$, $\{3,5\}$ and $\{3,6\}$, and only two pairs of them are disjoint: $2+2+2+2\sim3+2+3$ and $2+3+3\sim3+3+2$. Every layer has exactly one partner, so a crack-free wall of width $8$ is fixed by its bottom layer and alternates between that layer and its partner. The recurrence agrees: $F_t(L)=1$ for all $L$ and $t$, and $W(8,h)=4$ for every height.

6. Worked example: $W(9,3)=8$

Among the five layers of width $9$, exactly three pairs are compatible:

$$\begin{aligned}2+2+2+3&\sim3+2+2+2,\\2+2+3+2&\sim3+3+3,\\2+3+2+2&\sim3+3+3.\end{aligned}$$

Take the layers in the order of Section 2. Then $F_1=(1,1,1,1,1)$, and $F_2(L)$ is the number of partners of $L$, so $F_2=(1,1,1,1,2)$. One more round gives $F_3=(1,2,2,1,2)$: for example $F_3(2+2+3+2)=F_2(3+3+3)=2$, and the last entry is $F_2(2+2+3+2)$${}+F_2(2+3+2+2)=2$. The sum is $8$, the value given in the statement.

Here the walls can be counted for every height. The lines form two separate parts: the pair $2+2+2+3\sim3+2+2+2$, which gives $2$ walls of every height, and the path $2+2+3+2\sim3+3+3$${}\sim2+3+2+2$. In a wall from the path every second layer is $3+3+3$, and each other layer is one of the two ends of the path, chosen freely. A wall that starts with $3+3+3$ has $\lfloor h/2\rfloor$ free layers, a wall that starts at an end has $\lceil h/2\rceil$, so

$$W(9,h)=2+2^{\lfloor h/2\rfloor}+2^{\lceil h/2\rceil},$$

which gives $5,6,8,10,14,18$ for $h=1,\dots,6$.

7. What compatible layers look like

From now on let $w\ge4$, so that every layer has at least two bricks.

Claim. Let $K\sim L$. (a) One of the two layers starts with a brick of length $2$ and the other with one of length $3$, and the same holds at the right end. (b) Strictly between two neighbouring gaps of $L$ lies exactly one gap of $K$, and vice versa, so the gaps of $K$ and $L$ alternate from left to right.

Proof. (a) Equal first bricks of length $b$ would give both layers a gap at $b$, and equal last bricks a gap at $w-b$. (b) Let $a\lt a'$ be neighbouring gaps of $L$, so $a'-a$ is $2$ or $3$. The brick of $K$ that covers the unit segment from $a$ to $a+1$ cannot begin at $a$, a gap of $L$, so it begins at $a-1$ or further left and, being at most $3$ long, ends at $a+1$ or $a+2$. This end is at most $a'\le w-2$, so it is a gap of $K$, and it is not $a'$, so it lies strictly between $a$ and $a'$. No second gap of $K$ fits there, because only $a+1$ and $a+2$ lie in between and gaps of $K$ are at least $2$ apart. Exchanging $K$ and $L$ gives the converse. $\square$

By (a) no layer is its own partner, and every line of the graph joins a layer that starts with a $2$ to one that starts with a $3$: the graph is bipartite, and in every crack-free wall the first bricks alternate between the lengths $2$ and $3$, and so do the last bricks.

8. Pieces, and a number shared by the whole wall

Cut the width at the gaps of two layers $K\sim L$. By the claim the pieces have the lengths $1$ and $2$; the first and the last have length $2$, since one layer has its first gap at $2$ and the other at $3$. Two neighbouring pieces form one brick, of the layer that does not own the cut between them, so no two pieces of length $2$ are neighbours: for $2+2+3+2\sim3+3+3$ the cuts $2,3,4,6,7$ give the pieces $2,1,1,2,1,2$. Conversely, handing the cuts of such a sequence alternately to two layers makes every brick an end piece of length $2$ or two neighbouring pieces of total length $2$ or $3$, so the compatible pairs, taken without order, correspond exactly to these sequences. For $w\ge6$ a sequence is $2,1$, then a middle part of sum $w-6$, possibly empty, made of $1$s and $2$s without neighbouring $2$s, then $1,2$. If $N(n)$ counts the middle parts of sum $n$, then $N(0)=N(1)=1$, $N(2)=2$ and $N(n)=N(n-1)+N(n-3)$ for $n\ge3$, as a middle part ends with $1$ or with $1,2$; these are Narayana's cows numbers, shifted by one place. ^[7] Width $9$ has $N(3)=3$ compatible pairs, width $32$ has $N(26)=18560$.

Claim. Call all bricks of a layer except the first and the last its inner bricks, and let $\varphi(L)$ be the number of inner bricks of length $3$. If $K\sim L$, then $\varphi(K)=\varphi(L)$.

Proof. An inner brick of $K$ lies between two neighbouring gaps of $K$, so by Section 7 it consists of exactly two pieces, and it has length $3$ exactly when one of them has length $2$. The first brick of $K$ is the first piece, possibly followed by a piece of length $1$, and the same holds at the right end. So every piece of length $2$ except the first and the last lies in exactly one inner brick of $K$, and $\varphi(K)$ is the number of pieces of length $2$ minus $2$; the same count gives $\varphi(L)$. $\square$

In the example both layers have $\varphi=1$; all layers of a crack-free wall share $\varphi$. At width $32$ a layer with $j$ bricks of length $3$ has $(32-3j)/2$ of length $2$, so $j$ is even and at most $10$, and $\varphi$ is one of $0,1,\dots,9$, since $\varphi=10$ would need two end bricks of length $2$ besides ten of length $3$. A computation shows that the ten classes, of $2$, $26$, $144$, $440$, $825$, $924$, $672$, $240$, $54$ and $2$ layers, are exactly the connected components of the graph. The class $\varphi=0$ consists of $2+2+\dots+2$ and $3+2+\dots+2+3$, which alternate in the stretcher bond of bricklayers, each course offset by half a brick; ^[2] it gives $2$ walls of every height.

9. Width 32 in numbers

Width $32$ has $3329$ layers and $18560$ compatible pairs, so each round of the recurrence makes one addition for each of the $37120$ ordered compatible pairs, and $W(32,2)=37120$. A layer has between $1$ and $48$ partners, $11.15$ on average: $36$ layers, among them $2+2+\dots+2$, have a single partner, and $5$ layers have $48$. Since $F_t(L)$ is a sum of at most $48$ values $F_{t-1}(M)$, induction gives $F_t(L)\le48^{t-1}$, and therefore

$$W(32,10)\le3329\cdot48^{9}\approx4.50\cdot10^{18}\lt2^{63}.$$

Every count and every partial sum of the computation fits into a signed or an unsigned 64-bit integer.

How the Code Works

The C++ program ^[8] starts in main: parse_arguments reads --width= and --height=, with the defaults $32$ and $10$, and --skip-checkpoints, and rejects a width below $2$ or a height below $1$; unless --skip-checkpoints is given, run_checkpoints then verifies that solve(9, 3) returns $8$, and the program prints solve(width, height).

generate_rows stores each layer as a std::uint32_t mask whose bit $x$ is set when the layer has a gap at $x$. Its recursive lambda dfs receives the position pos reached so far and the mask of the gaps; it tries a brick of length $2$, then one of length $3$, skips a brick that would stick out, sets the bit of the brick's right end unless that end is the end of the wall, and stores the mask when pos equals the width. This is the recursion of Section 1: at width $9$ it yields the layers in the order of Section 2, and at width $32$ the lambda runs $13580$ times for the $3329$ masks. At width $33$ the recursion already evaluates 1U << next with next equal to $32$, for instance for the unfinished layer of sixteen bricks of length $2$; such a shift is undefined in C++, ^[9] so --width= is reliable only up to $32$.

solve implements Sections 3 and 4. Two masks belong to compatible layers exactly when their bitwise AND is $0$: ^[10] at width $9$ the masks of $2+2+2+3$ and $3+3+3$ are $84=2^2+2^4+2^6$ and $72=2^3+2^6$, and their AND $64=2^6$ is the shared gap $6$. solve tests all ordered pairs $(i,j)$, $i=j$ included, and appends $j$ to compatible[i] when the AND is $0$; at the widths $2$ and $3$ the single layer has no gap and is its own partner, correctly giving $W(2,h)=W(3,h)=1$. The vector dp of u64 counts starts with the values $F_1$, all ones; each of the height - 1 rounds fills next[i] with the sum of dp[j] over the partners $j$ of layer $i$ and swaps the vectors, and the result is the sum of the last vector. The additions are not checked for overflow: Section 9 covers the requested size, but very tall walls wrap modulo $2^{64}$, and $W(9,128)=2+2^{65}$ comes out as $2$.

The Python and Java programs do the same for the fixed width $32$ and height $10$, without options or checkpoint, with the recursions gen and genRows. Python's integers have no size limit; Java keeps the masks in a List<Integer>, the partners in int[][] and the counts in long, which suffices by Section 9.

Complexity and Verification

With $R=R(w)$ and $E$ ordered compatible pairs, the generator makes one call per partial layer, $\sum_{p\le w}R(p)=O(R)$ calls, the compatibility test makes $R^2$ AND operations, and each of the $h-1$ rounds fills $R$ counts using $E$ additions. The time is therefore $O(R^2+h(R+E))$, and the memory is $O(R+E)$ plus a recursion depth of at most $w/2$. At width $32$ the generator makes $13580$ calls, the test $11\,082\,241$ AND operations, which dominate, and the nine rounds $9\cdot37120=334\,080$ additions. Measured on a desktop computer, start-up included and with the C++ program compiled with -O2, C++ takes about $0.01$ seconds, Java $0.06$ and Python $0.34$. Generating the partners directly from Section 7 would avoid the quadratic test, while repeated squaring of $A$ would not pay off: nine sparse rounds are far cheaper than one product of two dense $3329\times3329$ matrices.

Unless --skip-checkpoints is given, the C++ program checks $W(9,3)=8$ before the main computation. For this article we also checked, outside the published solutions:

the three programs print the same number, and so does $\mathbf 1^{\top}A^{9}\,\mathbf 1$ computed with 64-bit matrix–vector products;
a brute force that fills a grid brick by brick agrees with the recurrence for all widths from $2$ to $12$ with heights up to $6$ and from $13$ to $20$ with heights up to $3$, $90$ cases;
the values $R(w)$ for $w\le33$, $W(8,h)=4$ for $h\le12$ and the formula for $W(9,h)$ for $h\le10$, and the C++ outputs $34$ and $37120$ for $W(9,8)$ and $W(32,2)$;
both claims of Sections 7 and 8 for all compatible pairs of the widths $4$ to $26$ and $32$, the counts $N(w-6)$, the ten components and the bound $F_t(L)\le48^{t-1}$.

Footnotes and References

The references supply background facts; the claims of Sections 7 and 8 and all numbers for the widths $8$, $9$ and $32$ are derived or computed in this article.

Project Euler 215 — Crack-free Walls. The official statement considers walls of 2×1 and 3×1 bricks, horizontal × vertical, whose gaps between horizontally adjacent bricks never line up in consecutive layers; it gives W(9, 3) = 8 and asks for W(32, 10).
Wikipedia — Brickwork. A perpend is a vertical joint between two bricks, and almost every bond keeps the perpends of successive courses apart; in the stretcher bond each course is staggered by half a brick.
Wikipedia — Padovan sequence. P(0) = P(1) = P(2) = 1 and P(n) = P(n − 2) + P(n − 3); P(n) counts the ordered sums of 2s and 3s equal to n + 2, and the ratio of successive terms tends to the plastic number, about 1.324718, the real root of x³ = x + 1.
Wikipedia — Dynamic programming. The method breaks a problem down into simpler subproblems in a recursive manner and solves overlapping subproblems only once by storing their results.
Wikipedia — Adjacency matrix. The (i, j) entry of the n-th power of the adjacency matrix counts the walks of length n from vertex i to vertex j.
R. P. Stanley — Enumerative Combinatorics, Volume 1, contents. Chapter 4, Rational generating functions, contains Section 4.7, The transfer-matrix method.
OEIS A000930 — Narayana's cows sequence. a(0) = a(1) = a(2) = 1 and a(n) = a(n − 1) + a(n − 3); a(n) also counts the compositions of n − 1 into parts 1 and 2 with no two adjacent 2s, so N(n) = a(n + 1).
C++ — Euler215.cpp. The linked immutable revision contains generate_rows, solve and run_checkpoints; it is the implementation record for this article.
cppreference — Arithmetic operators. For the built-in shift operators the behaviour is undefined if the right operand is negative or not less than the number of bits of the promoted left operand.
Wikipedia — Bitwise operation. A bit of the bitwise AND of two numbers is 1 exactly when both numbers have a 1 in that position.

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);
        }
    }
}