Counting Sturdy Brick Walls
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
- Math with Lego BlocksMedium