Project Euler Problem #173

Apr 11, 2010

Read the details of the problem here

Summary

Using up to one million tiles how many different “hollow” square laminae can be formed?

Solution

I started by considering a maths solution based around differences of sums of squares. In the examples given: 62-22 = 92-72 = 32. This seemed a viable approach to working out areas of laminae given the outline width and “hole” widths but it was getting late and I thought I’d go for something more obviously correct when coding!

All I do is start with a single ringed lamina and then add rings inside it until I run out of tiles, or run out of space in which to contain an inner ring. I then repeat this process with a lamina that starts one tile wider. Essentially I was trading mathematically complexity for computational iterations which suited me just fine at 2am!

The coding for this was trivial. Each inner ring is 2 tiles narrower and so 8 tiles smaller – only basic addition and subtraction is required in the inner loop. The solution is simple and “obviously correct”! No understanding of maths required!

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

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

This runs in 0.91 seconds, well within the alloted time. A Java version runs in about 3ms – 310x faster. Unsurprisingly, the algorithm doesn’t scale well but was perfectly adequate for this solution. I may have to revisit it for subsequent problems of this nature.

Conclusion

Groovy didn’t add or detract from this solution. It saved some boilerplate but that was about it.