Case Study: Building a Layout Counter — From a Recurrence to a Reusable Engine

"First make it correct, then make it fast, then make it general. Skip a step and you will pay for it twice."

Executive Summary

A front-end team needs to know how many valid layouts exist for a configurable widget strip: a row of $n$ cells, where each "tile" placed is either a single cell (a small widget) or a pair of adjacent cells (a wide widget). Product wants the count to drive a "you have $X$ possible arrangements" hint, and QA wants it to validate an exhaustive-layout test generator. In this build-heavy case study you will construct the counter in four passes: (1) derive the recurrence from the layout structure (§18.2), (2) write a correct-but-slow recursive counter, (3) rebuild it as a fast bottom-up (iterative) solver, and (4) generalize it so it handles new tile rules without rewriting the engine — ending at the chapter's Toolkit function solve_linear. Unlike the forensics of Case Study 1 (where you analyzed given code), here you build the artifact and watch a recurrence turn into production code.

Skills applied

  • Modeling a layout-counting problem as a recurrence by "conditioning on the last tile" (§18.2).
  • Pinning down the correct initial conditions, including the easily-missed $n = 0$ base case (§18.1).
  • Converting a recursive definition into an iterative bottom-up computation (the value-recurrence engine, §18.6 and the Project Checkpoint).
  • Generalizing a specific recurrence into the parameterized solve_linear(coeffs, inits, n).
  • Sanity-checking a counter against small hand-enumerated cases (computation ↔ proof, theme four).

Background

The scenario

A "widget strip" is a horizontal row of $n$ equal-width cells. The layout engine fills the strip completely with tiles, where each tile is one of:

  • a single tile, occupying 1 cell, or
  • a wide tile, occupying 2 adjacent cells.

A layout is an ordered arrangement of tiles that exactly fills the $n$ cells with no gaps and no overlaps. Two layouts are different if the sequence of tile widths differs. Let $L_n$ be the number of distinct layouts of a strip of length $n$.

For example, a strip of length 3 has these layouts (writing 1 for a single and 2 for a wide): 1 1 1, 1 2, 2 1 — so $L_3 = 3$.

🧩 Productive Struggle. Before reading on, enumerate the layouts for $n = 4$ by hand. Then guess $L_n$ in terms of earlier values by asking the §18.2 question: what can the last tile be? You have seen this recurrence before in this chapter, in three different costumes — see if you recognize it.

Why this matters

This is the domino-tiling problem of §18.2 wearing a UI hat (a $1 \times n$ strip with 1- and 2-cell tiles is the same combinatorial object as ordered sums of 1s and 2s, which §18.2 showed equals the $2 \times n$ domino count). Building the counter teaches the full life cycle of a recurrence in software: derive it, implement it naively, make it efficient, generalize it. The same four passes apply whenever a "how many configurations?" question shows up — feature flags, schedules, valid token sequences — so the engine you build here is worth keeping.

Phase 1: Derive the recurrence

Apply the "condition on the last tile" move from §18.2. A valid layout of length $n$ ends in exactly one tile, and that last tile is either single or wide:

  • If the last tile is single (1 cell), the first $n-1$ cells form any valid layout of length $n-1$. There are $L_{n-1}$ of these.
  • If the last tile is wide (2 cells), the first $n-2$ cells form any valid layout of length $n-2$. There are $L_{n-2}$ of these.

These two cases are disjoint (a layout's last tile has one definite width) and exhaustive (the last tile must be single or wide). By the sum rule (Chapter 15):

$$L_n = L_{n-1} + L_{n-2}.$$

That is the Fibonacci recurrence — the third disguise in this chapter, after $2 \times n$ tilings and binary strings avoiding "00" (§18.2).

Now the initial conditions — get these exactly right, because the whole engine rests on them. The recurrence is second-order, so it needs two (§18.1). The cleanest choice anchors at $n = 0$:

  • $L_0 = 1$: there is exactly one way to fill an empty strip — place no tiles. (The empty layout is a layout. This $n=0$ base case is the one beginners drop.)
  • $L_1 = 1$: a single-cell strip admits only 1 (one single tile; a wide tile would not fit).

⚠️ Common Pitfall: Forgetting $L_0 = 1$. It is tempting to start at $L_1 = 1, L_2 = 2$ and never define $L_0$. That works if you never call the engine on small inputs, but the recurrence $L_2 = L_1 + L_0$ silently uses $L_0$, and a bottom-up solver indexes from 0. Defining $L_0 = 1$ (the empty layout) makes every downstream formula uniform. With it, $L_2 = L_1 + L_0 = 1 + 1 = 2$ (1 1, 2), which matches direct enumeration. ✓

🔄 Check Your Understanding With $L_0 = 1, L_1 = 1$, compute $L_2, L_3, L_4$ from the recurrence and check $L_3$ against the three layouts listed in the Background.

Answer

$L_2 = L_1 + L_0 = 2$; $L_3 = L_2 + L_1 = 3$; $L_4 = L_3 + L_2 = 5$. $L_3 = 3$ matches 1 1 1, 1 2, 2 1. (These are the Fibonacci numbers shifted: $L_n = F_{n+1}$ with $F_0 = 0, F_1 = 1$.)

Phase 2: A correct (but slow) recursive counter

Build the most direct thing that could possibly be correct — a literal transcription of the recurrence and its initial conditions. Correctness first.

def layouts_naive(n):
    """Number of ways to fill a length-n widget strip with 1- and 2-cell tiles."""
    if n == 0:           # empty strip: the empty layout
        return 1
    if n == 1:           # one cell: only a single tile fits
        return 1
    return layouts_naive(n - 1) + layouts_naive(n - 2)   # last tile single, or wide

print([layouts_naive(n) for n in range(0, 9)])
# Expected output:
# [1, 1, 2, 3, 5, 8, 13, 21, 34]

We hand-verify the start against Phase 1: $L_0=1, L_1=1, L_2=2, L_3=3, L_4=5$, then the recurrence extends to $8, 13, 21, 34$. The list is the Fibonacci sequence shifted by one ($L_n = F_{n+1}$), exactly as the chapter promised for this family.

This is correct. It is also exponential — and we already know why from §18.6: two recursive calls on nearly-full inputs give the cost recurrence $T(n) = T(n-1) + T(n-2) + c$, which grows like $\phi^n$. layouts_naive(40) would make on the order of $10^8$ calls. Correct, but unusable for a strip of any real length. On to speed.

💡 Intuition: The naive version recomputes layouts_naive(k) for the same k an exponential number of times — the left subtree and the right subtree overlap massively. Every efficient solver for a recurrence is, at heart, a scheme for computing each subproblem once. The bottom-up rebuild below is the simplest such scheme.

Phase 3: Rebuild it bottom-up (fast and iterative)

Instead of recursing down from $n$ (and re-solving overlaps), compute up from the base cases, keeping only what we need. The recurrence reaches back two terms, so we only ever need the last two values — a sliding window of size 2. This is precisely the engine behind the Toolkit's solve_linear (Project Checkpoint), specialized to this recurrence.

def layouts(n):
    """Same count as layouts_naive, computed bottom-up in O(n) time, O(1) extra space."""
    if n == 0 or n == 1:
        return 1
    prev2, prev1 = 1, 1          # L_0, L_1
    for _ in range(2, n + 1):    # build L_2, L_3, ..., L_n in order
        prev2, prev1 = prev1, prev1 + prev2   # slide the window: (L_{i-2}, L_{i-1}) -> (L_{i-1}, L_i)
    return prev1

print([layouts(n) for n in range(0, 9)])
print(layouts(40))
# Expected output:
# [1, 1, 2, 3, 5, 8, 13, 21, 34]
# 165580141

Two things to verify by hand. First, the small list must match Phase 2 — it does, the same $1,1,2,3,5,8,13,21,34$. Second, layouts(40) $= L_{40} = F_{41}$. We can state this landmark value: $F_{41} = 165{,}580{,}141$. The bottom-up version computes it in 40 cheap iterations; the naive version would not finish in any reasonable time. Same answer, completely different cost — the §18.6 lesson made concrete by construction.

🔄 Check Your Understanding Trace the window (prev2, prev1) through the loop for layouts(4): write its value before the loop and after each of the iterations $i = 2, 3, 4$.

Answer

Before: $(1, 1)$ = $(L_0, L_1)$. After $i=2$: $(1, 2)$ = $(L_1, L_2)$. After $i=3$: $(2, 3)$ = $(L_2, L_3)$. After $i=4$: $(3, 5)$ = $(L_3, L_4)$. Return prev1 $= 5 = L_4$. ✓

🔗 Connection: This sliding-window loop is the loop inside solve_linear from the Project Checkpoint, hard-coded for window size 2 and coefficients $[1, 1]$. We built the specific case to understand it; next we hand the work to the general engine.

Phase 4: Generalize — one engine, many tile rules

Product now wants variations: What if a strip also allows a 3-cell "extra-wide" tile? Or what if wide tiles can be one of two colors (so a wide tile contributes 2 layouts, not 1)? Rewriting a new bespoke function each time is exactly the duplication the Toolkit exists to prevent. The fix: express each variant as coefficients + initial conditions and feed them to one general solver — solve_linear from this chapter's Project Checkpoint.

Recall the contract (§ Project Checkpoint): solve_linear(coeffs, inits, n) returns $a_n$ for $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$, with coeffs = [c1, ..., ck] (so c1 multiplies the most recent term) and inits = [a0, ..., a_{k-1}].

Variant A: the original strip (1- and 2-cell tiles). $L_n = L_{n-1} + L_{n-2}$, so $c_1 = 1, c_2 = 1$; initial conditions $L_0 = 1, L_1 = 1$.

Variant B: add a 3-cell tile. Conditioning on the last tile (single / wide / extra-wide): $$L_n = L_{n-1} + L_{n-2} + L_{n-3}.$$ This is the Tribonacci recurrence (the same shape as §18.2's "1-, 2-, or 3-step stairs"). It is third-order, so it needs three initial conditions: $L_0 = 1$ (empty), $L_1 = 1$ (1), $L_2 = 2$ (1 1, 2). Coefficients $[1, 1, 1]$.

Variant C: wide tiles come in 2 colors. A wide tile now has 2 choices, so the "last tile is wide" case contributes $2L_{n-2}$, not $L_{n-2}$: $$L_n = L_{n-1} + 2L_{n-2}.$$ Coefficients $[1, 2]$; initial conditions $L_0 = 1$, $L_1 = 1$.

Now every variant is one call to the same engine — no new function bodies:

from dmtoolkit.recurrences import solve_linear

# Variant A: 1- and 2-cell tiles            (Fibonacci-shaped)
print(solve_linear([1, 1],    [1, 1],     8))     # L_8
# Variant B: add a 3-cell tile              (Tribonacci)
print(solve_linear([1, 1, 1], [1, 1, 2],   8))     # L_8 with 3-cell tiles
# Variant C: wide tiles in 2 colors         (a_n = a_{n-1} + 2 a_{n-2})
print(solve_linear([1, 2],    [1, 1],       8))    # L_8 with 2-color wide
# Expected output:
# 34
# 81
# 171

Hand-derivation of each expected value, so we trust the engine rather than run it:

  • Variant A is just $L_n = F_{n+1}$: $L_8 = F_9 = 34$. ✓ (matches layouts(8) from Phase 3).
  • Variant B (Tribonacci), building from $T_0=1, T_1=1, T_2=2$: $T_3 = 2+1+1 = 4$, $T_4 = 4+2+1 = 7$, $T_5 = 7+4+2 = 13$, $T_6 = 13+7+4 = 24$, $T_7 = 24+13+7 = 44$, $T_8 = 44+24+13 = 81$. ✓
  • Variant C, $a_n = a_{n-1} + 2a_{n-2}$ from $a_0=1, a_1=1$: $a_2 = 1 + 2\cdot1 = 3$, $a_3 = 3 + 2\cdot1 = 5$, $a_4 = 5 + 2\cdot3 = 11$, $a_5 = 11 + 2\cdot5 = 21$, $a_6 = 21 + 2\cdot11 = 43$, $a_7 = 43 + 2\cdot21 = 85$, $a_8 = 85 + 2\cdot43 = 171$. ✓

💡 Intuition: Notice what generalization bought us. The modeling work (Phase 1's "condition on the last tile") is the only part that changes per variant, and it changes in a tiny, mechanical way: a new tile size adds a term (raising the order), and a tile with $c$ variants multiplies its term by $c$ (changing a coefficient). The solving work is now zero — solve_linear does it. That separation of "model it" from "solve it" is the entire arc of this chapter, captured in one function call.

🚪 Threshold Concept: A recurrence is not just an answer to one counting question — it is a parameterized family of answers. Once your engine takes the coefficients and initial conditions as data, you have stopped writing a counter and started writing a counter-generator. Every "how many configurations of this self-similar thing?" question collapses to "what are the coefficients and the base cases?" — and the §18.2 setup moves answer exactly that.

Discussion Questions

  1. Variant C multiplied the $L_{n-2}$ term by 2 because a wide tile had 2 colors. Suppose single tiles came in 3 colors and wide tiles in 2. Write the new recurrence and its initial conditions, and give the solve_linear call. (Be careful with $L_1$: how many length-1 layouts are there now?)
  2. The bottom-up layouts keeps only two variables (prev2, prev1) and runs in $O(1)$ extra space, while solve_linear keeps a list window of size $k$. For the second-order case, are they doing the same work? When would you reach for the specialized two-variable version over the general engine?
  3. We were careful to define $L_0 = 1$ (the empty layout). Trace what layouts_naive would return for $n = 2$ if a programmer "simplified" the base cases to just if n <= 2: return n. Which value breaks, and why does the empty-layout convention $L_0 = 1$ matter even though no user ever asks for a length-0 strip?
  4. All three variants are correct by construction (each is a faithful transcription of a sum-rule case analysis). How would you test them as well — what small hand-enumerated cases would you check, and what would agreement (or solve_linear matching a brute-force enumerator) establish versus not establish? (Connect to theme four: computation tests, proof settles.)

Your Turn: Extensions

  • Option A (closed form, looking ahead). Variant A's count is $L_n = F_{n+1}$, and Chapter 19 will give Fibonacci a closed form via the golden ratio. Before that chapter, set up Variant C's characteristic equation ($r^2 - r - 2 = 0$) using §18.4, find its (nice integer) roots, and write the closed form $L_n = \alpha r_1^n + \beta r_2^n$ fitted to $L_0 = 1, L_1 = 1$. You will have solved a variant in closed form by hand — a capability the Phase-4 numeric engine does not provide.
  • Option B (a 2-D strip). Generalize to a $2 \times n$ board tiled by $1 \times 2$ dominoes — the original §18.2 problem. Argue that its count is also governed by $[1, 1]$ but with initial conditions $t_1 = 1, t_2 = 2$, and reconcile this with the $1 \times n$ strip's $L_0 = 1, L_1 = 1$ (they are the same sequence, indexed differently — $t_n = L_n$). Use solve_linear for both and confirm.
  • Option C (brute-force oracle). Write a recursive enumerator that yields every layout (as a tuple of tile widths) for length $n$, then a one-liner that counts them. Use it as an oracle: compare its count to layouts(n) for $n = 0, \dots, 6$ (hand-trace both). This is the "test, then trust" pattern — the enumerator is slow but obviously correct, so agreement gives strong evidence for the fast solver.

Key Takeaways

  1. Derive, then implement, then optimize, then generalize. The recurrence (Phase 1) drives a naive counter (Phase 2), a fast bottom-up counter (Phase 3), and finally a parameterized engine (Phase 4) — each pass reusing the last pass's understanding.
  2. The initial conditions are part of the model. Defining $L_0 = 1$ (the empty layout) is what makes every downstream formula and the bottom-up index uniform; dropping it is the classic bug.
  3. Variants are coefficient changes, not rewrites. A new tile size raises the order; a tile with $c$ variants scales its coefficient. The §18.2 setup move yields the coefficients; solve_linear does the rest.
  4. A solved recurrence becomes reusable infrastructure. solve_linear(coeffs, inits, n) turns "how many configurations of this self-similar thing?" into a single call — the Toolkit payoff this chapter adds, and the bridge to Chapter 19's faster solvers.