Project Euler Problem 38 Solution

Question

Take the number 192 and multiply it by each of 1, 2, and 3:

\begin{aligned} 192 \times 1 & = 192 \\ 192 \times 2 & = 384 \\ 192 \times 3 & = 576 \end{aligned}

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3).

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with 1,2,...,n where n \gt 1?

Haskell

import Data.List (sort)

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

multiples :: Int -> [String]
multiples x = takeWhile ((== 9) . length) $ dropWhile ((< 9) . length) $ scanl (\acc n -> acc ++ show (x * n)) (show x) [2..]

main :: IO ()
main = putStrLn $ maximum $ filter pandigital $ concatMap multiples [1..10000]

$ ghc -O2 -o pandigital-multiples pandigital-multiples.hs
$ time ./pandigital-multiples
real   0m0.006s
user   0m0.000s
sys    0m0.006s

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 concatenated_product(number, n):
    try:
        return int(''.join(str(number * i) for i in range(1,n+1)))
    except ValueError:
        print(number, n)

def main():
    print(max(concatenated_product(i, n) for i in range(10000) for n in range(1, 10) if is_pandigital(concatenated_product(i, n))))

if __name__ == "__main__":
    main()

$ time python3 pandigital-concatenation.py
real   0m0.927s
user   0m0.927s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
p (1..9999).flat_map { |i|
  (1..9).map { |j|
    (1..j).map { |k|
      i * k
    }.reduce('') { |s,v| s + v.to_s }
  }
}.select { |s|
  s.length == 9 && s.split('').sort.join('') == '123456789'
}.map { |s| s.to_i }.max

$ time ruby pandigital-concatenation.rb
real   0m0.361s
user   0m0.361s
sys    0m0.000s