## 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: 6^{2}-2^{2} = 9^{2}-7^{2} = 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 answer++ def (inner, inside) = [ width - 2, tiles - 8 ] while ((tiles + inside <= LIMIT) && (inner >= MINW)) { tiles += inside answer++ 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.

Apr 12, 2010 at 00:09

[…] just completed Problem #173 the previous evening, I found this a very easy one to start the day with! The same solution could […]