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