Project Euler Problem 32 Solution

Question

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=725439 \times 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.

Haskell

import Data.List (nub, sort)

candidates :: [(String, Integer)]
candidates = [(concatMap show [a, b, a*b], a*b) | a <- [1..2000], b <- [1..50]]

pandigital :: String -> Bool
pandigital = (== "123456789") . sort

main :: IO ()
main = print $ sum $ nub [p | (digits, p) <- candidates, pandigital digits]
$ ghc -O2 -o pandigital pandigital.hs
$ time ./pandigital
real   0m0.080s
user   0m0.068s
sys    0m0.000s

Python

#!/usr/bin/env python
def is_pandigital(*args, **kwargs):
    num = sorted(''.join(str(arg) for arg in args))

    try:
        if kwargs['length'] and len(num) != kwargs['length']:
            return False
    except KeyError:
        pass

    for i in range(len(num)):
        if str(i+1) != str(num[i]):
            return False
    return True

def main():
    pandigitals = set()
    total = 0
    for multiplicand in range(1, 5000):
        for multiplier in range(1, 100):
            product = multiplicand * multiplier
            if is_pandigital(multiplicand, multiplier, product, length=9):
                pandigitals.add(product)
    print(sum(pandigitals))

if __name__ == "__main__":
    main()
$ time python3 pandigital-products.py
real   0m2.023s
user   0m2.008s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
puts (1..4999).flat_map { |a|
  (1..99).map do |b|  
    [a.to_s + b.to_s + (a*b).to_s, a*b]
  end
}.select { |p| 
  p[0].length == 9 && p[0].each_char.sort.join == "123456789"
}.map { |p| p[1] }.uniq.reduce(:+)
$ time ruby pandigital.rb
real   0m3.317s
user   0m3.268s
sys    0m0.036s

Questions? Comments? Send me an email: z@chdenton.com