Skip to content

Project Euler Problem 68

December 27, 2011

Solving Project Euler Problem 68 has conveniently fallen on post-Christmas day as a benign mental exercise 🙂

Our 5-gon consists of outer and inner rings of 5 numbers each. Each number from inner ring participates in solution twice, while each number from outer ring – only once. Apparently, the maximum 16-digit string would come out from outer ring consisting of 6->10->9->8->7 in this specific order! If a 5-gon with such outer ring exists, then its inner ring would include numbers 1,2,3,4,5 in an order that preserves its “magic” property, i.e. each sum of outer->inner1->inner2 should be equal to ((6+7+8+9+10) + 2*(1+2+3+4+5))/5 = 14.

So, let’s assume that 5-gon with such outer ring exists and try brute force the content of the inner ring of only 5! = 120 combinations using “magic” requirement as solution(s) filter. If we get only one solution it must be the Problem 68 answer, otherwise we’d get back to problem considerations.

let isMagic5gon outer inner =
    List.zip3 outer inner (List.tail inner @ [List.head inner])
    |> List.forall (fun (o,i,i') -> o + i + i' = 14)

let glueSolution outer inner =
    List.zip3 outer inner (List.tail inner @ [List.head inner])
    |> List.fold (fun acc (o,i,i') -> sprintf "%s%d%d%d" acc o i i') ""

//---J.Harrop F# for Scientists; pp.166-167---------
let rec distribute e = function
   | [] -> [[e]]
   | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
and permute = function
    | [] -> [[]]
    | e::xs -> List.collect (distribute e) (permute xs)
//--------------------------------------------------

let problem068 () =
    let candidates = permute [1;2;3;4;5] |> List.filter (isMagic5gon [6;10;9;8;7])
    if List.length candidates= 1 then
        candidates |> List.head |> glueSolution [6;10;9;8;7]
    else
        failwith "Bad solution approach"

Lucky me, it worked!

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: