Skip to content

Project Euler Problem 79

March 8, 2012

Project Euler Problem 79 solution is straightforward and fun. It took me more time to come up with an algorithm, than simply solve this problem with pen and paper, indeed.

Anyway, the first step is to convert triplets given in the keystrokes file into a list of unique pairs of kind (preceding keystroke, following keystroke). This is what ends up in pairs list in the code.

Then, the core algorithm is of “divide and conquer” type, where the role of controller is performed by function pull. On each step it finds a sigle keystroke that does not precede any other. This is performed by function last of folding keystroke precedence pairs. Upon finding this last keystroke is prepended to the list of previously found keystrokes. Afterwards, all pairs having just found keystroke on the second place are excluded from the precedence list. This is performed by function cut. Then everything is repeated for this shrinked list again and again until the precedence list having only one pair. Then it keystrokes are added to the list of found keystrokes.

open System.IO
open System

let getData (path: string) =
    [ use sr = new StreamReader(path)
      while not sr.EndOfStream do
      yield sr.ReadLine() |> int ]

let pairs =
    getData @"..\..\..\Datafiles\"
    |> set |> Set.toSeq
    |> Seq.collect (fun x ->
                    |> fun y -> seq {
                                        yield (y.[0], y.[1])
                                        yield (y.[1], y.[2])
    |> set |> Set.toList

let last ts =
    ts |> List.fold (fun (f,t) (x,y) ->
        ((Set.add x f), (Set.add y t))) (Set.empty,Set.empty)
    |> fun (x,y) -> Set.difference y x |> Set.toList |> List.head

let cut i ts = ts |> List.fold (fun ts' (x,y) ->
    if y <> i then (x,y) :: ts' else ts') []

let rec pull pairs chain =
    match pairs with
    | [(x,y)] -> x::y::chain
    | _ -> pull (cut (last pairs) pairs) ((last pairs)::chain)

let problem079 () =
    pull pairs [] |> List.toArray |> fun x -> Int32.Parse(new string(x))

Few days after posting this I had being tipped that my approach is a reinvention of toposort, indeed.


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 )

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: