Project Euler Problem #114

May 20, 2010

Read the details of the problem here

Summary

Investigating the number of ways to fill a row with separated blocks that are at least three units long.

Solution

Nice little problem to start the day with. I opted for a recursive solution that places blocks of length 3 upwards into a gap, shuffling them to the right as far as possible. For each position it calls itself to place blocks in a new gap to the right of the placed block leaving a space of 1 unit between them. Note that it’s important to initialize total as a long to prevent overflow (that had me flummoxed for a few minutes!). It’s also necessary to add one to the returned answer to cater for an empty solution with no blocks placed.

def cache = new long[51]
Arrays.fill(cache,-1)
cache[3] = 1

def count(gap, cache) {

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

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

def answer = 1 + count(50, cache)

This runs in 91 milliseconds. A Java version runs in 960 microseconds or thereabouts, so about 95x faster.

Conclusion

Groovy kept the syntax terse but it wasn’t really a Groovy solution. Although it’s possible to rewrite the loops as listops, I don’t really think that it adds any value to the solution and has an adverse impact on performance.

Advertisements

One Response to “Project Euler Problem #114”


  1. […] just completed Problem 114 and with that fresh in my mind, this problem was very straightforward. I just parameterised the […]


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: