Skip to content

Project Euler Problem 85

June 24, 2012

After detail-laden Problem 84 solving Project Euler Problem 85 is a breeze. Nevertheless, prior to coding we need to do some preparatory math.
For our grid of h*w cells a specific rectangle can be selected by crossing 2 horizontal lines with 2 vertical. We can pick 2 horizontal lines in (h + 1)!/2!*(h + 1 – 2)! ways (see combination for justification). Similar is true for vertical lines: (w + 1)!/2!*(w + 1 – 2)!. After simplification it comes out that the number of different rectangles on a grid of h*w cells is h*(h + 1)*w*(w + 1)/4.
Now, let’s express approximate value of w via h assuming that overall number of rectangles is less, than 2000000:
w = int(sqrt(float(8000000/(h*(h + 1))))). As we took w*w for w*(w + 1) approximation sometimes we may overshoot by 1; in these cases we would need to decrease w by 1.
The rest is quite simple: starting with h=1 and ending with largest h less, than w let’s find all pairs (w,h) that function rectangles w h yields value closest to 2000000. Of this sequence we select such area w*h that yields minimal difference with 2000000:

let rectangles w h = w * (w + 1) * h * (h + 1) / 4
let solutions =
    Seq.unfold(fun h ->
        let w = int(sqrt(float (8000000/(h*(h+1)))))
        let solution = if rectangles w h > 2000000 then (w - 1,h)
            else (w,h)
        if fst solution <= h then None else Some(solution, h + 1)) 1

let problem085() =
    solutions |> Seq.toList
    |> (fun (w,h) -> (2000000 - (rectangles w h), w*h))
    |> List.sortBy (fun (diff,area) -> diff) |> List.head |> snd

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: