## Project Euler Problem #115

### May 20, 2010

Read the details of the problem here

Summary

Finding a generalisation for the number of ways to fill a row with separated blocks.

Solution

Having just completed Problem 114 and with that fresh in my mind, this problem was very straightforward. I just parameterised the count() function to accept the block length and created a wrapping function F() (as per the question) that would create an appropriately sized & initialized cache and then call count() to do the grunt work of the calculation. After that I had to find a way to call this with sufficient efficiency to return in a timely manner – I could have coded up a bisection search but, in this case, a simple ascending search was efficient enough for this purpose.

```def count(m, gap, cache) {

if (gap < m) return 0
if (cache[gap] != -1) return cache[gap]

def total = 0L
for (len in m..gap) {
total += gap - len + 1
def maxpos = gap - len + 1
for (pos in 0..maxpos) {
total += count(m, gap - len - pos - 1, cache)
}
}
cache[gap] = total
}

def F(m, n) {
def cache = new long[n+1]
Arrays.fill(cache,-1)
cache[m] = 1
1 + count(m, n, cache)
}

def ( BLOCK_LEN, LIMIT ) = [ 50, 1e6 ]

while (F(BLOCK_LEN, answer) <= LIMIT) {
}
```

This runs in 0.49 seconds. Perfectly acceptable for this solution and could be further tweaked for performance if needed.

Conclusion

As per the solution to Problem 114, Groovy kept the syntax terse but it wasn’t really a Groovy solution.