## 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.