Friday, November 19, 2010

Problem 49: What 12-digit number do you form by concatenating the three terms in this sequence?

This was a tough problem. Even after dreaming up an algorithm which would perform well enough, it went through several tweaks until I was satisfied. We resort to an array (though no mutation) and sequence expression in order to achieve short-circuiting and overcome F#’s lack of break and continue (again). This algorithm runs in about 1 minute and 500 milliseconds, just over the Project Euler suggested limit. I was able to uglify it a bit to get it to run in 59 seconds and 700 milliseconds, but I won’t even bother showing that here.

let problem49b =
    let fourDigitPrimes =
        {1000..9999}
        |> Seq.filter isPrime
        |> Seq.toArray

    let arithmeticTriples = seq {
        for i in {0..fourDigitPrimes.Length-1} do
            for j in {i+1..fourDigitPrimes.Length-1} do
                for k in {j+1..fourDigitPrimes.Length-1} do
                    let a = fourDigitPrimes.[i]
                    let b = fourDigitPrimes.[j]
                    let c = fourDigitPrimes.[k]
                    //is arithmetic seq other than given in question
                    if b-a = c-b && a <> 1487 then 
                        yield (a,b,c)
    }
    
    let arePerms (a,b,c) = 
        let setA = Set(Digits.fromInt a)
        let setB = Set(Digits.fromInt b)
        setA = setB && setB = Set(Digits.fromInt c)
        
    arithmeticTriples
    |> Seq.find arePerms
    |> (fun (a,b,c) ->
            [Digits.fromInt a; Digits.fromInt b; Digits.fromInt c] 
            |> Seq.concat 
            |> Digits.toInt64)

No comments:

Post a Comment