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.
Related posts
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 🙂
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