## Project Euler Problem #117

### May 20, 2010

Read the details of the problem here

Summary

Investigating the number of ways of tiling a row using different-sized tiles.

Solution

This question follows on nicely from Problem 114, Problem 115 & Problem 116. I used my solution from Problem 115 as a base and amended it so that, rather than having a hardcoded block/tile size iteration it would accept a range as parameter m into the count method. Apart from the change to allow no gaps between tiles and a corresponding change to F() to allow ranges that was about it.

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

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

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

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

def answer = F((2..4), 50)
```

This runs in 64 milliseconds and returns an amazingly high number!

Conclusion

As per the solution to Problems 114, 115 & 116, Groovy kept the syntax terse but it wasn’t really a Groovy solution. It did make the adding the ability to accept a range parameter a really trivial exercise though, so big win for Groovy over Java in this respect.

Advertisements