## Project Euler Problem #116

### May 20, 2010

Read the details of the problem here

Summary

Investigating the number of ways of replacing square tiles with one of three coloured tiles.

Solution

This question follows on nicely from Problem 114 and Problem 115. It was just a matter of amending the count() method from Problem 115 to cater for the facts that (i) the block is a fixed size and (ii) no gap is required to be kept between blocks. The F() method had to be changed slightly as an empty solution are not permitted. The rest was just a case of adding the values for each block type which a listop made easy.

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

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

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

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

def answer = (2..4).sum { F(it,50) }
```

This runs in 67 milliseconds. Again, acceptable for this solution especially with so little editing needed from my earlier solution!

Conclusion

As per the solution to Problems 114 & 115, Groovy kept the syntax terse but it wasn’t really a Groovy solution (apart from the last line!).