# Solutions for Problem 85

It can be seen that a 3x2 grid can contain 18 rectangles:

There is no grid that contains exactly 2 million rectangles. Find the area of the grid that contains the closest number to 2 million rectangles.

Runtime: 100.058 ms

```{- Borrowed from other code, the triangular numbers -}
tris :: [Integer]
tris = 0:1:zipWith (+) [2..] (tail tris)

{- For a 1x"n" grid there are as many rectangles as the nth triangular number.
- Also for an "n"x"m" grid there are tri(n) * tri(m) rectangles.
- Create a list that has the dimension and the multiplier (dropm 0 and 1) -}
lenVals = drop 2 (zip [0..] tris)

{- Given a limit/number to aim for, find the "x" and "y" lengths for the grid with
- the closest value. -}
findXY :: Integer -> (Integer,Integer)
findXY lim = inner lenVals (1,1) lim
where
inner ((xl,xm):xs) (x,y) diff | xm > lim + diff = (x,y)
inner ((xl,xm):xs) (x,y) diff = inner xs (x',y') d'
where
(ny,nd) = foldl (\(cy,cd) (yl,xy) ->
(\ld -> if ld < cd then (yl,ld) else (cy,cd))
(abs (lim - xy)))
(0,diff)
(takeWhile (\(f,g) -> g < lim + diff) (map (\(l,r) -> (l,r*xm)) lenVals))
(x',y',d') = if nd < diff then (xl,ny,nd) else (x,y,diff)

{- Find the "x" and "y" for 2000000 and multiply them to obtain the area. -}
main = print ((\(x,y) -> x * y) (findXY 2000000))
```

The code is probably borderline incomprehensible, lots of anonymous functions and fiddling around inside the folding... Oh well, it is code.

## Python by Althalus

Runtime 5.7 seconds

```def countRects(x,y):
count = 0
for i in range(0,x):
for j in range(0,y):
count += (x-i)*(y-j)
return count

solutions={}
for x in range(1,100):
for y in range(1,x):
solutions[abs(2000000-countRects(x,y))] = [x,y]
skeys = solutions.keys()
skeys.sort()
theSolution =  solutions[skeys[0]]
print theSolution[0]*theSolution[1]
```

Sure, not as fast as Thomas's, and not all that elegant, but it's a damn site easier to understand... (for me at least, anyway.) And it's way past my bedtime.