problem 140

problem140

(fn [sos]
  (letfn [
          (combine [x y]
            (let [diff [nil (.toUpperCase (str (clojure.set/difference x y)))] ]
              (conj (clojure.set/intersection x y) diff)))
          (remove-dontcares [minterms]  (set (remove vector? minterms)))
          (get-off-by-ones [all-minterms [current-key current-vals]]
            (let [
                  off-by-one
                  (map #(combine current-key %)
                       (filter #(= 1
                                   (count
                                    (clojure.set/difference % current-key)))
                               (keys  all-minterms)))]
              (if (empty? off-by-one)
                (hash-map current-key current-vals)
                (zipmap off-by-one (repeat current-vals) )
                )))
          (collect-implicants [minterms ]
            (loop [reducible (zipmap minterms (map vector minterms))]
              (let [new-reducible
                    (reduce #(merge-with concat %1 %2)
                            (map #( get-off-by-ones reducible %) reducible )) ]
                ( if (= reducible new-reducible)
                  (reduce #(assoc %1 (remove-dontcares (key %2)) (val %2)) {} reducible)
                  (recur new-reducible)))))
          (find-minimum-solution [minterms-by-implicant]
            (let
                [
                 tuples
                 (set (for
                          [k (keys minterms-by-implicant)
                           v (minterms-by-implicant k)] [k v]))

                 essential-tuples
                 (filter
                  (fn [tuple] (nil? (next
                                     (filter #(= (second tuple) (second %)) tuples)))) tuples)]
              ;; assuming that the essential implicants cover the solution. This is not true for all examples but the examples that are on 4clojure work this way. It's just that the solution to do the sum-of-product stuff is nasty even when it is working!
                 (set (map first essential-tuples))
              ))]
    (find-minimum-solution (collect-implicants sos))))