60 Days of Euler in F# - Problem 32

The Problem

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

The Solution

Let's start about by writing a function to figure out if two factors and their product form a "1 through 9 pandigital".

let allDigits = ['1'..'9']

let isPandigital9Product n1 n2 prod =
    let containsAllDigits (digits : string) =
        allDigits |> List.forall (fun c -> digits.IndexOf(c) >= 0)

    let digits = sprintf "%i%i%i" n1 n2 prod
    if digits.Length <> 9 then false
    else containsAllDigits digits

The isPandigital9Product function takes two numbers and their product and then turns them into a string. If the number of digits isn't 9, then we return false, otherwise we determine if all the digits 1..9 are found in the string.

Next, we need to generate all possible combinations of factors. We'll do this by cross-joining the sequence 1..9999 with itself.

Unfortunately, this generates nearly 100 million factors, and running our pandigital test on that many combinations makes us exceed our 1-minute time limit. I can't see a way to speed up the test very much, so the way to speed things up is to limit the number of factors we try. For every factor we eliminate, we eliminate almost 10,000 combinations.

The most obvious way I can see to do this is to eliminate all factors that have duplicate digits in them and any factors containing the digit 0. Doing this reduces the number of possible factors from 9999 to 3609. Which means that instead of testing 99,980,001 combinations, we only have to test 13,024,881, an 87% reduction. Not bad!

So let's get our combinations of factors:

let cartesianProductSeq xs ys = 
    xs 
    |> Seq.collect (fun x -> ys |> Seq.map (fun y -> x, y))

let containsUniqueDigits n =
    let digits = sprintf "%i" n
    digits.IndexOf('0') < 0 &&
    digits.Length = (digits |> Seq.distinct |> Seq.length)

let factors = [1..9999] |> List.filter containsUniqueDigits

And now we can get the answer.

#time
cartesianProductSeq factors factors
|> Seq.map(fun (n1,n2) -> (n1,n2,n1*n2))
|> Seq.filter(fun (n1,n2,prod) -> isPandigital9Product n1 n2 prod)
|> Seq.map(fun(_,_,prod) -> prod)
|> Seq.distinct
|> Seq.sum
#time

The above generates all the combinations of factors, combines them with their products, filters out all those that aren't pandigital, then finds the sum of the distinct products.

Other Posts in This Series