September 22, 2018

Just Juxt #39: Veitch, Please! (4clojure #140)

Veitch

You may want to read about kmaps first.

Create a function which accepts as input a boolean algebra function in the form of a set of sets, where the inner sets are collections of symbols corresponding to the input boolean variables which satisfy the function (the inputs of the inner sets are conjoint, and the sets themselves are disjoint... also known as canonical minterms). Note: capitalized symbols represent truth, and lower-case symbols represent negation of the inputs. Your function must return the minimal function which is logically equivalent to the input.

(ns live.test
  (:require [cljs.test :refer-macros [deftest is run-tests]]
            [clojure.set :as set]
            [clojure.string :as str]))

(defn veitch [ss]
   (let [sets
          (->> [ss #{}]
            (iterate (fn [[sets acc]]
                       (->> (for [a sets, b (disj sets a)] [a b])
                         (map (fn [[a b]]
                                (->> (set/union
                                       (set/difference a b)
                                       (set/difference b a))
                                  (map (comp str/lower-case str))
                                  ((fn [[x & xs :as all]]
                                     (and (seq all)
                                          (apply = x xs)
                                          [(set/intersection a b) a b]))))))
                         (filter identity)
                         ((juxt
                            #(->> % (map first) set)
                            #(->> %
                               (reduce (fn [z x] (disj z (second x) (last x))) sets)
                               (set/union acc)))))))
            (take-while #(seq (first %)))
            last
            (apply set/union))]
      (->> ss
        (map (fn [x] (filter #(set/subset? % x) sets)))
        (filter #(= 1 (count %)))
        (map first)
        set)))

(deftest veitch-test
  (is (= (veitch #{#{'a 'B 'C 'd}
                   #{'A 'b 'c 'd}
                   #{'A 'b 'c 'D}
                   #{'A 'b 'C 'd}
                   #{'A 'b 'C 'D}
                   #{'A 'B 'c 'd}
                   #{'A 'B 'c 'D}
                   #{'A 'B 'C 'd}})
         #{#{'A 'c} 
           #{'A 'b}
           #{'B 'C 'd}}))
  (is (= (veitch #{#{'A 'B 'C 'D}
                   #{'A 'B 'C 'd}})
         #{#{'A 'B 'C}}))
  (is (= (veitch #{#{'a 'b 'c 'd}
                   #{'a 'B 'c 'd}
                   #{'a 'b 'c 'D}
                   #{'a 'B 'c 'D}
                   #{'A 'B 'C 'd}
                   #{'A 'B 'C 'D}
                   #{'A 'b 'C 'd}
                   #{'A 'b 'C 'D}})
         #{#{'a 'c}
           #{'A 'C}}))
  (is (= (veitch #{#{'a 'b 'c} 
                   #{'a 'B 'c}
                   #{'a 'b 'C}
                   #{'a 'B 'C}})
         #{#{'a}}))
  (is (= (veitch #{#{'a 'B 'c 'd}
                   #{'A 'B 'c 'D}
                   #{'A 'b 'C 'D}
                   #{'a 'b 'c 'D}
                   #{'a 'B 'C 'D}
                   #{'A 'B 'C 'd}})
         #{#{'a 'B 'c 'd}
           #{'A 'B 'c 'D}
           #{'A 'b 'C 'D}
           #{'a 'b 'c 'D}
           #{'a 'B 'C 'D}
           #{'A 'B 'C 'd}}))
  (is (= (veitch #{#{'a 'b 'c 'd}
                   #{'a 'B 'c 'd}
                   #{'A 'B 'c 'd}
                   #{'a 'b 'c 'D}
                   #{'a 'B 'c 'D}
                   #{'A 'B 'c 'D}})
         #{#{'a 'c}
           #{'B 'c}}))
  (is (= (veitch #{#{'a 'B 'c 'd}
                   #{'A 'B 'c 'd}
                   #{'a 'b 'c 'D}
                   #{'a 'b 'C 'D}
                   #{'A 'b 'c 'D}
                   #{'A 'b 'C 'D}
                   #{'a 'B 'C 'd}
                   #{'A 'B 'C 'd}})
         #{#{'B 'd}
           #{'b 'D}}))
  (is (= (veitch #{#{'a 'b 'c 'd}
                   #{'A 'b 'c 'd}
                   #{'a 'B 'c 'D}
                   #{'A 'B 'c 'D}
                   #{'a 'B 'C 'D}
                   #{'A 'B 'C 'D}
                   #{'a 'b 'C 'd}
                   #{'A 'b 'C 'd}})
         #{#{'B 'D}
           #{'b 'd}}))
  (is (= (veitch #{#{'a 'b 'c 'd}
                   #{'A 'b 'c 'd}
                   #{'a 'B 'c 'D}
                   #{'A 'B 'c 'D}
                   #{'a 'B 'C 'D}
                   #{'A 'B 'C 'D}
                   #{'a 'b 'C 'd}
                   #{'A 'b 'C 'd}})
         #{#{'B 'D}
           #{'b 'd}})))

(run-tests)
Tags: coding exercises KLIPSE 4clojure Cryogen juxt