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.

Posted by Kristian

5 comments

Jean-Marie Hachey

Thanks for this interesting article.
___

Symmetry and arrangements

What about the effects of symmetry factors on the number of arrangements of black and red blocks ?

http://imageshack.us/a/img195/1119/blackredblocks.jpg

In the Figure, one can observe the symmetry in the following cells :
C1R4 and C3R3
C1R6 and C3R5
C2R1 and C3R2
C2R2 and C3R1
C2R3 and C2R4
C2R5 and C3R4

I am sure you can use it in some way. I just haven’t been able to exploit it in my algorithms. Feel free to work it out and share with us though 🙂

Jean-Marie Hachey

Some results and comments on :
Project Euler 114: Investigating the number of ways to fill a row
with separated blocks that are at least three units long.
http://www.mathblog.dk/project-euler-114-fill-row-with-blocks/

___

Calculations done with and results obtained from an algorithm developed by Kristian
http://www.mathblog.dk/files/euler/Problem114.cs

______

Results and comments :

http://imageshack.us/a/img577/9762/p1de2pe114table1.jpg

http://imageshack.us/a/img801/1852/p2de2pe114table2.jpg

this is just the fibonacci sequence,
Let f(n) be the answer for n blocks.

Then f(n) = f(n-1) + f(n-4) + f(n-5) + f(n-6) + ……
Here
f(n-1) = #cases where first cell is empty
f(n-4) = #cases where first red block is of size 3
f(n-5) = #cases where first red block is of size 4 and so on…

Now I will prove that this is fibonacci-like seq
Lets assume
g(n) = f(n) + f(n-1) + f(n-2) + f(n-3) …. + f(1)

So, g(n) – g(n-1) = g(n-2) + f(n-2) + f(n-3 )
=> g(n) = 2g(n-1) – g(n-2) – g(n-4)
=> x^4 = 2x^3 – x^2 – 1
=> x(x-1) = +/- 1
which gives 4 roots( out of which 2 are phi and 1-phi. Other 2 are imaginary ).
So, f(n) is indeed fibonacci-like seq and you are looking for f(50). You can assume the seq to be of type = a*w^n + b*x^n + c*y^n + d*z^n where a,b,c,d can be calculated with initial conditions and w,x,y,z are the 4 roots.

Funny thing about the number 16475640049 is that it is the 9th number which is both triangular and heptagonal, see https://oeis.org/A039835

Leave a Reply