Project Euler 114: Count the ways a row measuring fifty units in length could be filled with blocks three units long

Problem Description

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 black 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), black (1), and red (4).

Analysis

For the purpose of this discussion, the unit size of the space into which blocks (red) are placed is identified as n and the unit size of the red blocks, with a range in size from 3 to n, is identified as m. Also, an empty space void of any red blocks is counted.

This is a counting problem, so dynamic programming and its hand maiden linear programming come immediately to mind and usurp the notion of trying a brute-force solution.

And as far as examples go, 7 wasn’t the best choice as the problem admits, but it will suffice to answer the problem.

My first analogy was shifting groups of bits in a computer’s register, but here’s a more festive idea. I looked at this problem like a game of Tetris (Play a game online here). This is a much simpler version as there is only one dropping shape, a “line” with a minimum size of 3 units. Let’s look at the example graphic twisted slightly to show my thought process:

The only constraint is that no falling shapes can ever touch; they must be separated by at least one empty space.

As the red blocks fall the only variable is the length of the block, m; between 3 and 7. When we move to n = 8, this same configuration for n = 7 will be a subset of it. Just like n = 6 is a subset of n = 7.

In fact, to demonstrate this concept, lets try to calculate the number of ways we can fill 6 spaces:

1. First, lets remove, in our minds, the last cell from every column in the graphic.
2. OK, that gives us 6 instead of 7 spaces. Go ahead and scroll or move your window to clip the image for a visual.
3. From the first row we will have to remove the third and last columns because:
   • The third will have an invalid 2-length red tile at the bottom.
   • The last one is a repeat of the second-to-last column.
4. In the second row, the last one is a duplicate, so it goes.
5. Same for the last one in the third, fourth and last rows

How many survived the butchery? Change the variable n in the program to 6 and run it. Did it match your count?

By now, you could add a tile to our graphic and learn the count for 8 spaces. Soon a pattern would become obvious and a dynamic solution is born.

It’s just adding a series of numbers for each n as it increase from 3 through 50. Yes, a function (with binomial tendencies) exists out there that would always put to rest a dynamic programming solution for counting, but why spoil the fun.

Project Euler 114 Solution

Afterthoughts

• See also, Project Euler 115 Solution:
  
• Hey, in your copious free time, create some other graphics in the same order as presented here for larger n and check out the curves the black spaces produce in the top set.
  
• If F() is the counting function, then F(3,{3 .. 12}) = 2, 4, 7, 11, 17, 27, 44, 72, 117, 189
  
• This is the sequence:
  Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A005252: Sum_{k=0..floor(n/4)} binomial(n-2k,2k).
  
• Which means that it could be solved as:
  

from Euler import binomial as C

n = 50 + 1
print sum(C(n - 2*k, 2*k) for k in range(int(n/4)+1))