# Project Euler Problem 79

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\Problem079.data" |> set |> Set.toSeq |> Seq.collect (fun x -> x.ToString().ToCharArray() |> 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.