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

January 9, 2012 at 02:06

[…] Yacoby’s Wanderings and Key Zero Conversation […]