Project Euler 114: Investigating the number of ways to fill a row with separated blocks that are at least three units long.

I wont brag that I have ever been good at spotting a problem which should be solved by using recursion. But problem 114 of Project Euler is so obvious a case that even I can see it. It reads

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).

Making the recursion

I have been looking at problem 115 as well, so I have defined the function F(m,n) which is the way you can fill a row of m unit with a blocksize of minimum n. This is the function we want to make recursive.

For the example I will use m =7 and n = 3. The first thing we get is F(7,3). Obviously we leave the rest of it empty and we have a solution.

Alternatively we can fill it up with blocks of size 3 starting at position 1, to 5. Once we have placed a red block we reserve a black block after it and calls the function again. So for the example where we have

we can call the F(3,3) since removing 1 black block we have 3 blocks left. There we can either leave the rest empty, or put in a block 3 starting at position 0.

Once we have checked for all starting positions of blocks of length 3 we have to check for lengths of 4,5,6 and 7 for all possible starting positions.

All this can be compiled in the function

private long F(int m, int n) {

    //The rest is empty
    long solutions = 1;

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

    for (int startpos = 0; startpos <= m-n; startpos++) {
        for (int blocklength = n; blocklength <= m-startpos; blocklength++) {
            solutions += F(m - startpos - blocklength-1, n);
        }
    }

    return solutions;
}

All we have to do now is to call F and print the result. Unfortunately this will take around 70 seconds on my rather fast computer for m=50. Therefore we need to think of a way to cut down on the computations. This is possible since we are calculating the thing over and over again, and therefore we can cache the result

Memoization

Until recently I would have called this method caching. But for a recursive program this technique is also called memoization. At first I thought I would have to save values of all m and n, until I looked a bit more at the code and realized that n is never changing, so all we need is to store the result for different values of m and such that we don’t have to calculate it all again.

This can be done by adding two lines of code to F, such that it becomes

private long F(int m, int n) {

    //The rest is empty
    long solutions = 1;

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

    if (cache[m] != 0) return cache[m];

    for (int startpos = 0; startpos <= m-n; startpos++) {
        for (int blocklength = n; blocklength <= m-startpos; blocklength++) {
            solutions += F(m - startpos - blocklength-1, n);
        }
    }

    cache[m] = solutions;
    return solutions;
}

where cache is just a global long of length n+1. Running the code again, gets me the result in 0.2761ms

The row can be filled in 16475640049 ways

Wrapping up

A recursive solution was a possible approach for this problem. However, as we saw we could add some cache and thereby avoid calculating the same thing over and over again and reduce the computation time to something which was really fast.

As usually you can find the source code here.