Counting Block Combinations I

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one grey square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?
NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), grey (1), and red (4).

To solve this problem, we can define a function f(n) as the number of ways to place blocks in a row of length n”. We know beforehand that f(1) = 1 (since we can have a row of only one grey square), f(2) = 2 (you could have a row of two greys, or a row of one red and one grey), and f(3) = 4 (you could have a row of three greys, one red + two greys, two greys + one red, or one red + one grey + one red).

We know from the statement of the problem that a block of red can be either 3, 4, 5, 6, … units in length. Hence, we define red(i) as a block of red of length i units, for i>=3.

Now, the key idea here is that for a row of length n >= 4, we could either leave the last unit grey and fill the rest or leave the last unit as the end of a red block. The number of ways to do this is: f(n-1) + red(3)*f(n-4) + red(4)*f(n-5) + red(5)*f(n-6) + …, until we reach a negative index for f(), in which case the term becomes zero.

To translate this idea into code, we can define our function recursively:

“`
def f(n):
if n < 3: return 2 ** n if n == 3: return 4 else: total = 0 total += f(n-1) for i in range(3, n+1): total += f(n-i-1) return total ``` Now, to find out the number of ways to fill a row measuring fifty units in length, we simply call the function with n=50: `print(f(50))`. It might be a little resource-intensive to calculate f(50) using this method. If so, a dynamic programming approach (with tabulation, or "bottom-up" method) can be used to reduce the computation time. ``` def f(n): f_values = [0]*(n+1) f_values[0], f_values[1], f_values[2] = 1, 2, 4 for i in range(3, n+1): for j in range(i): f_values[i] += f_values[j] return f_values[n] print(f(50)) ``` This second method fills up an array of f(n) values in increasing order, reducing the number of times each f(n) value is computed.

More Answers: