# Project Euler Problem 32

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.