Project Euler Problem 32

Ivar Thorson bio photo By Ivar Thorson

Project Euler Problem 32 asks us to once again find numbers that are pandigital from 1 to 9. This time, the digits of the numbers are taken from the equation (a*b=c), ignoring the * and = symbols.

;; Only two possible patterns of multiplications that produce 9 digits
;; 1. A 1 digit number times a 4 digit number can be 4 digits long.
;; 2. A 2 digit number times a 3 digit number can be 4 digits long. 

(defn as-digits [num]
  (map #(Character/getNumericValue %) (str num)))

(defn product-digits [a b]
  "Returns a list of digits of a, b, and (* a b)."
  (lazy-cat (as-digits a) (as-digits b) (as-digits (* a b))))

(defn all-unique? [digits]
  (let [unique (distinct digits)]
    (= (count unique) (count digits))))

(defn pandigital-9? [digits]
  (and (nil? (some zero? digits))
       (= 9 (count digits))
       (all-unique? digits)))

(defn euler-32 []
  (reduce + (into #{} (concat
                       (for [a (range 1 10)
                             b (range 1000 10000)
                             :when (pandigital-9? (product-digits a b))]
                         (* a b))
                       (for [a (range 10 100)
                             b (range a 1000)
                             :when (pandigital-9? (product-digits a b))]
                         (* a b))))))

(euler-32)

With a bit of effort, I was able to shorten this definition into the much more succinct one that follows:

(defn pandigital-multiplication? [a b]
  (= "123456789" (apply str (sort (flatten (map as-digits [a b (* a b)]))))))

(defn euler-32-concise []
  (reduce + (distinct (for [a (range 2 5000)
                            b (range a (/ 9999 a))
                            :when (pandigital-multiplication? a b)]
                        (* a b)))))

(time (euler-32-concise)) ;; "Elapsed time: 3415.286711 msecs"

Yet again, the folks over at clojure-euler have even more performant solutions, but what was most surprising to me is how changing the definition of pandigital-multiplication? could speed up my code by 10x:

;; Using split (thanks, semmons99!)
(defn pandigital-multiplication? [a b]
  (= "123456789" (apply str (sort (rest (.split (str a b (* a b)) ""))))))

(time (euler-32-concise)) ;; "Elapsed time: 161.618939 msecs"

Try as a might to modify it, I couldn’t get the algorithmically superior approach posted on clojure-euler by bibi (which uses combinations and permutations from clojure.contrib.combinatorics) to go faster than the above code. I guess the overhead of creating the combinations and permutations exceeds the benefit obtained through the reduction in the number of required tests for pandigitality.