Project Euler Problem #85

May 14, 2010

Read the details of the problem here

Summary

Investigating the number of rectangles in a rectangular grid.

Solution

Firstly, I reduced this down to a basic 1D problem, solving the number of consecutive tiling solutions on a single line, as per the diagram below.

c1

It is evident that the combinations for each line is simply the sum of terms.

Length Rectangles
1 1
2 3
3 6
4 10

The 3×2 rectangular exemplar has 18 rectangles which is simply the product of the linear combinations, i.e. Sum[1,2,3] x Sum[1,2] = 18, and extending this (as shown below) to blocks of 2×2 (9 rectangles) and 3×3 (36 rectangles) shows this rule to hold.

c2

c3

The program is therefore very straightforward, I just need to multiply the combinations for the various length sides and look for the closest to 2 million. The square root of 2 million is 1414.2. Sum(1..53) is 1431 but this question needs to minimize the difference so it may be over or under the stated target. I simply picked a maximum side length of 100, kept my fingers crossed and it gave the correct answer.

def ( mindiff, answer ) = [ Integer.MAX_VALUE, 0 ]

def sums = (0..100).collect { (it * it + it) / 2 }

for (i in 1..100) {
  for (j in i..100) {
    def n = sums[i] * sums[j] - 2000000
    if ( Math.abs(n) < mindiff )
        ( mindiff, answer, x, y ) = [ Math.abs(n), i * j ]
    if (n > 0) break
  }
}

This runs in 74 ms, so even though it’s brute-force it performs quite adequately for this purpose.

Conclusion

Groovy provided a certain convenience in syntax but I didn’t really use any special features in this solution. A Java solution would have been almost as terse.

Advertisements

One Response to “Project Euler Problem #85”


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: