Project Euler Problem #173

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

Advertisements

One Response to “Project Euler Problem #173”


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


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: