Euler Solution 85

From ProgSoc Wiki

Jump to: navigation, search

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
    inner ((xl,xm):xs) (x,y) diff | xm > lim + diff = (x,y)
    inner ((xl,xm):xs) (x,y) diff = inner xs (x',y') d'
        (ny,nd) = foldl (\(cy,cd) (yl,xy) ->
                            (\ld -> if ld < cd then (yl,ld) else (cy,cd))
                                    (abs (lim - xy)))
                        (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

for x in range(1,100):
 for y in range(1,x):
  solutions[abs(2000000-countRects(x,y))] = [x,y]
skeys = solutions.keys()
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.

Personal tools