Project Euler Problem 43

Ivar Thorson bio photo By Ivar Thorson

More pandigital problem madness for problem 43. Honestly, I think the guys at Project Euler were running out of ideas or something.

Coming up with a concise but inefficient solution was straightforward:

(use '[clojure.contrib.combinatorics :only (permutations)])

(defn as-int [coll]  (Integer/parseInt (apply str coll)))

(defn special? [n]
  (every? true? (map #(zero? (rem %1 %2))
                     (map as-int (partition 3 1 (rest n)))
                     [2 3 5 7 11 13 17])))

(defn euler-43 []
  (reduce + (map #(BigInteger. (apply str %))
                 (filter special? (permutations "0123456789")))))

(time (euler-43)) ;; "Elapsed time: 29441.089387 msecs"

The speed of the above algorithm could be greatly improved by not computing permutations whose first several digits do not satisfy the particular special? property for which we are testing. This means we could use nth-permutation from problem 24, and check how many digits are matching sequentially. Then we can skip ahead as needed until we find a match.

(defn factorial [n]
  (reduce * (range 2 (inc n))))

(defn all-but-nth [coll n]
  (lazy-cat (take n coll) (drop (inc n) coll)))

(defn nth-permutation [coll n]
  (if (= 1 (count coll))
    [(nth coll 0)]
    (let [f (factorial (dec (count coll)))
          x (quot n f)]
      (concat [(nth coll x)]
              (nth-permutation (all-but-nth coll x)
                               (- n (* x f)))))))

(defn as-bigint [coll] (BigInteger. (apply str coll)))

(defn matched-digits [n]
  (let [s (map #(zero? (rem %1 %2))
               (map as-bigint (partition 3 1 (rest n)))
               [2 3 5 7 11 13 17])
        c (count (take-while true? s))]
    (+ c 3)))

(defn euler-43-fast []
  (let [digits "0123456789"
        len (count digits)
        max (factorial len)]
    (loop [n 0
           ret 0]
      (if (>= n max)
        (let [p (nth-permutation digits n)
              m (matched-digits p)]
          (if (= m len)
            (recur (inc n) (+ ret (as-bigint p)))
            (recur (+ n (factorial (dec (- len m)))) ret))))))) 

(time (euler-43-fast)) ;; "Elapsed time: 4368.852353 msecs"

That was my best independent effort, without referencing another site. Yet, when I looked on clojure-euler I was surprised to an interesting solution by kotarak that completes in 15 msecs! By packaging all the computation into one hairy nut of a macro, the problem definition itself becomes quite clear. I must confess that the exact operation of his macro remains mysterious to me, however.