Lego Blocks - Dynamic Programming

Question

I'm trying to solve following DP problem:

You have 4 types of lego blocks, of sizes 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 and 1 * 1 * 4. Assume you have infinite number of blocks of each type.

You want to make a wall of height H and width M out of these blocks. The wall should not have any holes in it. The wall you build should be one solid structure. A solid structure means that it should not be possible to separate the wall along any vertical line without cutting any lego block used to build the wall. The blocks can only be placed horizontally. In how many ways can the wall be built?

Here is how I'm attempting it: Representing 1 * 1 * 1, 1 * 1 * 2, 1 * 1 * 3 and 1 * 1 * 4 blocks with a b c d . Valid patterns are indicated in bold. Invalid patterns are which can be broken by vertical line.

H=1 & W=3 #valid pattern=1
aa ab ba c

H=2 & W=3 #valid pattern=9

I'm trying to find recurrence pattern either to extend this by height or width.i.e to find values for H=3 & W=3 or H=2&W=4.

Any inputs on how to formula-ize growth for this by height or weight?
P.S. The wall be always H*W*1.

Answer 1

First, let's see how many M*N walls can we build if we neglect the need to keep them connected:

We can treat each row separately, and then multiply the counts since they are independent.

There is only one way to tile a 0*1 or a 1*1 wall, and the number of ways to tile an n*1 is the total of the number of ways to tile {n-1}*1...{n-4}*1-sized walls, the reason being these walls can be obtained by removing the last tile of the n*1 wall.

This gives rise to a tetranacci sequence, OEIS A000078. The number of all W*H walls is a(w,h)=T(w)^h.

Now, to count the number of solid walls. MBo's answer already contains the basic premise:

Branch on the leftmost place where the wall is not connected. The number of All W*H walls is the number of Solid X*H walls times the number of All {W-X}*H walls, summed across all possible values of X, plus the number of Solid W*H walls:

A(W,H) = sum{X=1..{W-1}}(S(X,H)*A(W-X,H)) + S(W,H)

As a last step, we separate S(M,H) term, which is the value we want to calculate, and repeat the previous formulas:

S(W,H) = A(W,H) - sum_x( S(X,H)*A(W-X,H) ) //implicitly, S(1,H)=1

A(W,H) = T(W)^H

T(X)   = X > 0: T(X-1)+T(X-2)+T(X-3)+T(X-4)
         X = 0: 1
         X < 0: 0

(proving MBo's formula correct).

This also provides an O(W^2) algorithm to compute S (assuming proper memoization and constant-time arithmetic operations)

Answer 2

It is not hard to find a number of 1xW stripes (let it is N(1,W)). Then you can find a number of all (including non-solid) HxW walls - it is A(H,W) = N(1,W)^H Any non-solid wall consists of left H*L wall and right H*(W-L) wall. It seems that number of solid walls is

S(H,W) = A(H,W) - Sum(S(H, L) * A(H, W-L)) [L=1..W-1]

S(H, L) * A(H, W-L) is number of non-solid walls with the leftmost break at L vertical position. First factor is the number of solid walls - to eliminate counting of repetitive variants.

Answer 3

My Python 3 implementation

def tetranacci(n): 
    arr = [1, 2, 4, 8]
    if n <= 4: 
        return arr[:n]
    else: 
        for i in range(4, n):
            arr.append(sum(arr[i-4:i])%(10**9 + 7))
    return arr

def legoBlocks(n, m):
    MOD = (10**9 +7)
    a, s = [(v**n)%MOD for v in tetranacci(m)], [1]

    for i in range(1, len(a)):
        sums = sum([x*y for x,y in zip(a[:i], s[::-1])])
        s.append( (a[i]-sums)%MOD)
    return s[-1]