Project Euler 117: Investigating the number of ways of tiling a row using different-sized tiles.

Problem 117 of Project Euler is a continuation of the problems given in Problem 114 to 116. The problem reads

Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.

 

How many ways can a row measuring fifty units in length be tiled?

This problem is actually more similar to Problem 114 than to Problem 116.  The only difference between this and Problem 114 is that we have an uppper limit on the size of block, which we didn’t in Problem 114. So we will just add that upper limit and remove the need for spaces between blocks to the recursive function and we are good to go.

The C# implementation of the recursive function looks like

private long F(int m, int nmin, int nmax) {

    //The rest is empty
     long solutions = 1;

    //we can't fill out more
     if (nmin > m) return solutions;

    if (cache[m] != 0) return cache[m];
    for (int bs = nmin; bs <= nmax; bs++) {
        for (int startpos = 0; startpos <= m - bs; startpos++) {
            solutions += F(m - startpos - bs, nmin, nmax);
        }
    }

    cache[m] = solutions;
    return solutions;
 }

So having solved the previous three problem this one was really easy. We get the following result in less than 0.3ms

You can fill a row of length 50 in 100808458960497 ways

Wrapping up

I am aware that there are other solutions out there, and I would love to get a full explanation to them. However, I think this approach works really well for this kind of problem, and I am really proud of myself to have implemented a recursive method successfully. So I will not go into more details with other solutions unless you bring it up.

The source code for this solution can be found here.

Posted by Kristian

1 comment

Interesting set of solutions and a fun set of four problems.

I started out similar to you, but by the time I got to problems 116 and 117 I had evolved to a pure dynamic programming solution. For the initial problem in the set I first viewed it as a tree that I would add blocks to. So at length 50 I can add a black tile or a red tile. That gave me two children. Recursively call the routine decrementing the size of the tree. Just pass the color of the last tile and the remaining length. The number of possibilities is the the number of leaves on the tree.

That approach was way to small. So with minor modifications I ended up fairly close to what you did.

For this problem just identify the base cases for strings of length 1,2,3 and 4. Then iterate from there. The Python code is as follows:


m = 50
a = [0] * (m + 1)

#base cases
a[1] = 1 # one black
a[2] = 2 # two black, one red
a[3] = 4 # black/red, red/black, green, 3black
a[4] = 8 # red/red, red/black/black, black/black/red, black/red/black,
# green/black, black/green, blue, 4 black
for i in range(5,m + 1):
a[i] = a[i - 1] + a[i - 2] + a[i - 3] + a[i - 4]
total = a[-1]
print total

Just pick off the last value in the list for the answer. I did not have to use a list as I only need to remember the last four values.

This was a trivial after solving problem 116 where I had to use basically the same code three time – once for each for red, green, and blue – and sum the results.

Leave a Reply