Project Euler Problem #115

May 20, 2010

Read the details of the problem here

Summary

Finding a generalisation for the number of ways to fill a row with separated blocks.

Solution

Having just completed Problem 114 and with that fresh in my mind, this problem was very straightforward. I just parameterised the count() function to accept the block length and created a wrapping function F() (as per the question) that would create an appropriately sized & initialized cache and then call count() to do the grunt work of the calculation. After that I had to find a way to call this with sufficient efficiency to return in a timely manner – I could have coded up a bisection search but, in this case, a simple ascending search was efficient enough for this purpose.

def count(m, gap, cache) {

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

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

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

def ( BLOCK_LEN, LIMIT ) = [ 50, 1e6 ]

def answer = BLOCK_LEN

while (F(BLOCK_LEN, answer) <= LIMIT) {
  answer++
}

This runs in 0.49 seconds. Perfectly acceptable for this solution and could be further tweaked for performance if needed.

Conclusion

As per the solution to Problem 114, Groovy kept the syntax terse but it wasn’t really a Groovy solution.

Advertisements

One Response to “Project Euler Problem #115”


  1. […] 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 […]


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: