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