Skip to content

Project Euler Problem 86

July 17, 2012

Solving Project Euler Problem 86 requires a single geometry-related “AHA”: the shortest path from one corner of a cuboid with sides l*w*h to the diagonally opposite one is the hypotenuse of right triangle with cathetes l and (w + h). The rest of the solution comes out quite straightforward: if we agree that 1<=h<=w<=l<=M, then for each l from 1 to M sum (h + w) runs from 2 to 2*M. For a sequence of growing ls we can find those sums (w + h) that yield positive integer of expression sqrt(l*l + (w + h)*(w + h)). Now the only thing is left to determine: how to for each suitable value (w + h) find the number of combinations of individual values w and h that are in line with 1<=h<=w<=l<=M. This is what function combinations detects in the code below.

With these prerequisites the solution is straightforward: from infinite sequence of growing Ms construct a sequence of tuples (l, (h + w)), then filter out all tuples, but those that yield integer hypotenuse lengths, then scan this filtered sequence into another sequence (paths, M), of which skip members until the first where paths >= 1000000. The associated M is the solution answer.

let combinations l ``h + w`` =
    if l >= ``h + w`` then ``h + w``/ 2
    else l - (``h + w`` + 1) / 2 + 1

let isIntegerHypotenuse (cathetus1,cathetus2) =
    let hypotenuse = sqrt (float (cathetus1 * cathetus1 + cathetus2 * cathetus2))
    hypotenuse = floor hypotenuse

let problem086() =
    Seq.initInfinite id
    |> Seq.collect (fun l ->
                        seq {for ``h + w`` in [2..2*l] -> (l,``h + w``)})
    |> Seq.filter isIntegerHypotenuse
    |> Seq.scan (fun (paths, M) (l, ``h + w``) ->
                     (paths + (combinations l ``h + w``), l))(0,0)
    |> Seq.skipWhile (fun (paths, M) -> paths < 1000000)     |> Seq.head
    |> snd
Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: