How Many Ways Can You Build A Staircase?

Riddler Express

Four four-digit numbers fill the rows of a CrossProduct table. The products of each row’s digits are $1458, 128, 2688, 125$, and the products down the thousands, hundreds, tens and ones columns are $960, 384, 630, 270$. Find the four numbers.

Solution

Factor each row product into four digits and let the column products pick the right factorisation, pruning whenever a running column product overshoots. The search returns a unique table: $$\boxed{3699,\ 8821,\ 8876,\ 5155.}$$ Down the columns: $3\cdot8\cdot8\cdot5 = 960$, $6\cdot8\cdot8\cdot1 = 384$, $9\cdot2\cdot7\cdot5 = 630$, $9\cdot1\cdot6\cdot5 = 270$.

The computation

List each row’s digit quadruples, then search for the combination whose four columns multiply to the targets.

from itertools import product
rows = [1458, 128, 2688, 125]; cols = (960, 384, 630, 270)
opts = [[t for t in product(range(1, 10), repeat=4)
         if t[0]*t[1]*t[2]*t[3] == p] for p in rows]
sols = []
def search(i, prod, acc):
    if any(prod[k] > cols[k] for k in range(4)): return
    if i == 4:
        if prod == list(cols): sols.append(acc)
        return
    for t in opts[i]:
        search(i + 1, [prod[k]*t[k] for k in range(4)], acc + [t])
search(0, [1, 1, 1, 1], [])
print(sols[0])     # [(3,6,9,9),(8,8,2,1),(8,8,7,6),(5,1,5,5)]

Riddler Classic

Build a four-step staircase from $10$ blocks (rows of $4, 3, 2, 1$ from the ground up). Each block slides to the wall, so a block can only rest where the one below it and the one wall-ward of it are already placed. How many distinct build orders are there? Extra credit: for an $N$-step staircase?

Solution

A build order places the blocks one at a time, and a block may go into a row only if the row below already has a block directly beneath it. So a legal order is a way to fill the staircase cell by cell, always keeping each row no further along than the row below: exactly the linear extensions of the staircase, equivalently the standard Young tableaux of the staircase shape $(4,3,2,1)$. Counting them gives $$\boxed{768}$$ ways for the four-step staircase. The same count for $N$ steps grows ferociously: $2, 16, 768, 292864, 1100742656, \dots$ for $N = 2, 3, 4, 5, 6$, the number of standard Young tableaux of the $N$-step staircase.

The computation

Count build orders directly with a memoised recursion over how many blocks sit in each row, adding a block to a row only when the row below supports it.

from functools import lru_cache
def build_orders(N):
    caps = tuple(range(N, 0, -1))               # row capacities, ground up
    @lru_cache(None)
    def count(fill):
        if fill == caps: return 1
        total = 0
        for i in range(N):
            below = fill[i - 1] if i > 0 else N   # ground supports anything
            if fill[i] < caps[i] and below > fill[i]:
                nf = list(fill); nf[i] += 1
                total += count(tuple(nf))
        return total
    return count((0,) * N)
print(build_orders(4))                          # 768