While having lots of pieces, this problem is mostly straightforward. The only part that required any analysis is determining sufficient lower and upper bounds for the product, since the worst case range (1 to 999999999) is far too large. Letting p be the product, mn be the multiplican, and mr be the multiplier, we observe that if mn * mr = p, then (len p) = ((len mn) + (len mr)) + (-1 or 0). Which implies the length of the product is cannot be less than 4 or greater than 5 or we will have either too few or too many digits in our pandigital set. Thus the range may be restricted to 1234 to 98765.
let problem32c = let hasDistinctPositiveDigits (nstr:string) = not (nstr.Contains("0")) && nstr.Length = (nstr |> Seq.distinct |> Seq.length) let isPositivePanDigitalSet mnstr mrstr pstr = let concatedDigitStr:string = mnstr + mrstr + pstr concatedDigitStr.Length = 9 && hasDistinctPositiveDigits concatedDigitStr let findPositivePanDigitalSet p = let pstr = p |> string if not (hasDistinctPositiveDigits pstr) then None else let sr = sqrtn p let rec loop mn = if mn > sr then None elif p % mn = 0 then let mr = p/mn if isPositivePanDigitalSet (mn |> string) (mr |> string) pstr then Some(mn, mr, p) else loop (mn + 1) else loop (mn + 1) loop 2 {1234..98765} //product must be between 4 and 5 digits |> Seq.map findPositivePanDigitalSet |> Seq.filter Option.isSome |> Seq.sumBy (fun (Some(_,_,p)) -> p)
No comments:
Post a Comment