Thursday, May 27, 2010

Problem 26: Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

After taking a break for a few days, having spent 3 consecutive weeks solving problems 1-25 every free hour and deep into the night, this turned out to be a pleasant return despite it’s intimidating appearance.  I simply worked out the first 7 values of d on paper using long division, spotted a pattern corresponding to recurring cycle lengths, and churned out an implementation of the algorithm in F#.  I am finding that looping via recursion is a very gentle way to implement algorithms: you simply reason out each case one at a time and return when you come to the end of a branch.  No worrying what happens next, just pass it on.

let problem26c =     
    let cycleLength d =
        let rec cycleLength (steps:ResizeArray<int>) step =
            if d > step then 
                cycleLength steps (step*10)
            else 
                if steps.Contains(step) then
                    (d, steps.Count - steps.IndexOf(step))
                else
                    steps.Add(step)
                    let step = step - d*(step/d)
                    if step = 0 then
                        (d, 0)
                    else
                        cycleLength steps step
        cycleLength (ResizeArray<int>()) 1
    //on dual core, runs in 60ms vs. 90ms when parallelized, 
    //and twice as fast with larger ranges
    {2..999}
    |> PSeq.map cycleLength 
    |> PSeq.maxBy snd 
    |> fst

No comments:

Post a Comment