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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: