letter-distribution.clj

(ns plumbing.letters
  (:use plumbing.core))

(def letters
  (array-map "A" 0.03559596939643605 "B" 0.08791477424094518 "C" 0.07694824074741784 "D" 0.04579860597727158 "E" 0.018669123556424614 "F" 0.034505834128967044 "G" 0.05439868577642196 "H" 0.07268753217954918 "I" 0.003955862892091837 "J" 0.03025983302791189 "K" 0.03294327720020791 "L" 0.04848650695769241 "M" 0.09608053808826617 "N" 0.018547007013788936 "O" 0.014720280137130485 "P" 0.049319930077139015 "Q" 0.002206565702878153 "R" 0.05763521983707609 "S" 0.09580978699464698 "T" 0.035309842314786705 "U" 0.002210911090800405 "V" 0.015875707643636012 "W" 0.05861438058222256 "X" 2.4144758019273616E-4 "Y" 0.006166216881876424 "Z" 0.005097919974221793))

(defn best [n-parts]
  (let [letters (vec letters)
        target (/ (sum second letters) n-parts)]
    ((memoized-fn
      best-solution [from n-parts]
      (if (= from (count letters))
        {:solution []
         :score (if (zero? n-parts) 0 Double/POSITIVE_INFINITY)}
        (if (= n-parts 0)
          {:solution [] :score Double/POSITIVE_INFINITY}
          (apply min-key
                 :score
                 (for [n (range 1 (- (inc (count letters)) from))]
                   (letk [part (subvec letters from (+ from n))
                          wt (sum second part)
                          [score solution] (best-solution (+ from n) (dec n-parts))]
                     {:score (+ score (* (- wt target) (- wt target)))
                      :solution (cons (mapv first part) solution)}))))))
     0 n-parts)))

(best 6)