Project Euler 115: Finding a generalisation for the number of ways to fill a row with separated blocks.

Problem 115 of Project Euler is a continuation of Problem 114. The problem reads

NOTE: This is a more difficult version of problem 114.

A row measuring n units in length has red blocks with a minimum length of m 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.

Let the fill-count function, F(mn), represent the number of ways that a row can be filled.

For example, F(3, 29) = 673135 and F(3, 30) = 1089155.

That is, for m = 3, it can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million.

In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million.

For m = 50, find the least value of n for which the fill-count function first exceeds one million.

With the very efficient solution from Problem 114 I couldn’t help just trying to wrap it in a while loop until I found the solution. Such that we have the code

long solutions = 0;
int n = 50;

int limit = 1000000;
int m = n-1;

while (solutions < limit) {
    m++;
    cache = new long[m + 1];
    solutions = F(m, n);
}

This will correctly solve the problem in less than 6ms and give the result

The solutions exceeds 1000000 for m=168

There is one thing we can do to speed it up though. Since n is kept constant we can reuse the cache every iteration when increasing m. In a simple version where we just guess on an upper bound of 200 we could implement this as

long solutions = 0;
int n = 50;

int limit = 1000000;
int m = n - 1;

cache = new long[200];

while (solutions < limit) {
    m++;
    solutions = F(m, n);
}

This cuts the execution time to below 2ms. This is as far as I went with this problem.

Wrapping up

Reusing the recursive code from Problem 114 gives us a really efficient solution to this problem which is stated as harder. However, logically it was a very simple extension of the problem and the solution was again very efficient.

You can find the source code for the problem here.

Posted by Kristian

Leave a Reply