## Project Euler Problem #114

### May 20, 2010

Read the details of the problem here

Summary

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

Solution

Nice little problem to start the day with. I opted for a recursive solution that places blocks of length 3 upwards into a gap, shuffling them to the right as far as possible. For each position it calls itself to place blocks in a new gap to the right of the placed block leaving a space of 1 unit between them. Note that it’s important to initialize total as a long to prevent overflow (that had me flummoxed for a few minutes!). It’s also necessary to add one to the returned answer to cater for an empty solution with no blocks placed.

```def cache = new long[51]
Arrays.fill(cache,-1)
cache[3] = 1

def count(gap, cache) {

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

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

def answer = 1 + count(50, cache)
```

This runs in 91 milliseconds. A Java version runs in 960 microseconds or thereabouts, so about 95x faster.

Conclusion

Groovy kept the syntax terse but it wasn’t really a Groovy solution. Although it’s possible to rewrite the loops as listops, I don’t really think that it adds any value to the solution and has an adverse impact on performance.

Advertisements

### One Response to “Project Euler Problem #114”

1. […] just completed Problem 114 and with that fresh in my mind, this problem was very straightforward. I just parameterised the […]