Counting Sturdy Brick Walls

Reported in interviews at Squarepoint Capital

Problem statement

You are building a wall that is height rows tall, and every row must be exactly width units wide. Each brick is $1$ unit tall; the available brick widths are given in the list bricks (distinct positive integers), and you may use any width any number of times. A row is a left-to-right sequence of bricks whose widths add up to exactly width.

The wall is sturdy if no two vertically adjacent rows have a brick boundary at the same horizontal position -- the two ends of the wall (positions $0$ and width) do not count as boundaries.

Write count_sturdy_walls(height, width, bricks) returning the number of sturdy walls, modulo $10^9 + 7$.

Constraints: $1 \le$ height $\le 100$, $1 \le$ width $\le 10$, $1 \le$ len(bricks) $\le 10$, brick widths distinct and in $[1, 10]$.

Examples:

  • count_sturdy_walls(2, 3, [1, 2]) $\to 2$. The row layouts are $[1,2]$ (boundary at $1$), $[2,1]$ (boundary at $2$) and $[1,1,1]$ (boundaries at $1, 2$). Only $[1,2]$ over $[2,1]$ and $[2,1]$ over $[1,2]$ avoid a shared boundary.
  • count_sturdy_walls(1, 1, [5]) $\to 0$: no row of width $1$ can be built.
Show hint

How could you represent where a single row's cracks fall so that comparing two rows is a single cheap operation?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems