Project Euler Problem #174

April 12, 2010

Read the details of the problem here

Summary

Counting the number of “hollow” square laminae that can form one, two, three, … distinct arrangements.

Solution

Having just completed Problem #173 the previous evening, I found this a very easy one to start the day with! The same solution could be used with just a few minor alterations.

Rather than just incrementing the count of laminae I incremented an element in an array corresponding to the number of tiles in use for the lamina so, for the examples given, element 8 => 1 and element 32 => 2. This should have had a negligible effect on the runtime and given me an array containing how many laminae were created for any particular number of tiles.

The question is worded a little confusingly but is really just asking “How many tile counts, in the given range, can form between one to ten laminae?” This information is easily extracted from the array using a couple of Groovy listops.

def LIMIT = 1000000
def MAX = LIMIT.intdiv(4)+1
def (MINW, MAXW) = [ 3, LIMIT.intdiv(4)+1 ]

def L = new int[LIMIT+1] 
Arrays.fill(L,0)

for (width in MINW..MAXW) {
  def tiles = (width - 1) * 4
  L[tiles]++
  def (inner, inside) = [ width - 2, tiles - 8 ]
  while ((tiles + inside <= LIMIT) && (inner >= MINW)) {
    tiles += inside
    L[tiles]++
    inner -= 2
    inside -= 8
  }
}

def answer =
    L.toList().findAll { it > 0 && it < 11 }.size()

This runs in 2.09 seconds, well within the alloted time but taking 1.18 seconds longer that than before! The addition of the array to the Problem #173 solution brought the runtime up to 1.09 seconds (adding 180ms) so the bulk of that time – 1 second – was in the single line assignment to the answer! I found that coding an explicit accumulation loop over L reduced the runtime down to 1.31 seconds, so was 5x faster than the listop method.

Note: A Java version runs in about 15ms – 140x faster than this Groovy code, but 5x slower than before. Only 2ms is attributable to the final accumulation loop, the other 10ms is simply from array access. I must look into this!

Conclusion

Groovy didn’t add or detract from this solution, but it only goes to show that, while Groovy listops are great syntactically, they suck in performance. I know that I should really be using Groovy lists rather than explicit arrays but, in this case, they bump up the runtime by another 30% or more.

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: