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!).

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: