Project Euler Problem #114

May 20, 2010

Read the details of the problem here


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


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]
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 {
    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.


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.


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: 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: