Project Euler Problem #117

May 20, 2010

Read the details of the problem here


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


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]
  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!


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: