Project euler 88

pe_88.clj

;;; problem 88
;;; "Elapsed time: 22843.242538 msecs"


(require '[clojure.test :as test])

;; defn-memo : defined elsewhere
;; creates memoized function which works properly with recursion.

;; fartors : defined elsewhere
;; returns prime factor list
;; ex. (factors 12) ;=> (2 2 3)


;;; functions to get list of prodect of n
(defn-memo destribute-n [n s]
  (if (empty? s)
    '()
    (cons (cons (* n (first s)) (rest s))
          (map #(cons (first s) %) (destribute-n n (rest s))))))

(test/is (= (destribute-n 2 [3 4 5])
            [[6 4 5] [3 8 5] [3 4 10]]))

(defn add-n [n s]
  (cons (sort (cons n s))
         (map sort (destribute-n n s))))

(test/is (= (set (add-n 2 [3 4 5]))
            (set [[2 3 4 5] [4 5 6] [3 5 8] [3 4 10]])))

(defn-memo product-list [factor-list]
  (if (empty? factor-list)
    [[]]
    (distinct
     (mapcat #(add-n (first factor-list) %)
            (product-list (next factor-list))))))

(test/is (= (set (product-list (factors 54)))
            (set '((2 3 3 3) (3 3 6) (2 3 9) (6 9) (3 18) (2 27) (54)))))

;;; calculate k from given num list
(defn calc-k [l]
  (+ (apply * l)
     (- (apply + l))
     (count l)))

(test/is (= (calc-k [2 3 3 3])
            47))
(test/is (= (calc-k [3 3 6])
            45))

;;; fill out the array using caluculated k & n data.
(defn all-k-data [end]
  (loop [n 4
         result (doto (int-array (inc end) 0)
                  (aset ,, 0 1))]
      (if (not-any? #{0} result)
        (into [] result)
        (let [new-k (sort (map calc-k (product-list (factors n))))]
  	  (recur (inc n)
                 (do (doseq [idx (take-while #(< % (inc end)) new-k)]
                       (if (= (aget result idx) 0)
                         (aset result idx n)))
                     result))))))


(test/is (= (all-k-data 12)
            [1 4 4 6 8 8 12 12 12 15 16 16 16]))

(defn pe88 [end]
  (->> (all-k-data end)
       (drop 1)
       (distinct)
       (reduce + )))