# Euler Solution 85

### From ProgSoc Wiki

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

## Haskell by SanguineV

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.