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

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.

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.