99 Clojure Problems (50)

Fortunately for those of you following along at home, Wikipedia has a great article on Huffman Coding. The theory is simple, just keep taking the bottom two smallest frequency numbers and smoosh them into a new node with their frequency summed together until you’re left with only two elements. Then split each node of the tree into 0 and 1, and just keep appending on down the tree.

; P50 (***) Huffman code.
(comment "First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes!")

(comment "We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms. Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S. In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'), hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.]. The task shall be performed by the predicate huffman/2 defined as follows:")  

(defn huffman-tree [fs] 
  (let [fs-sorted (sort-by #(nth % 1) fs)]
    (loop [[a b & tail] fs-sorted] 
        (if (not (empty? tail)) 
          (recur (sort-by #(nth % 1) (conj tail (list (concat (list (nth a 0)) (list (nth b 0))) (+ (nth a 1) (nth b 1))))))
          (concat (list (nth a 0)) (list (nth b 0)))))))
(defn digit-map [a b c]
  (if (seq? a)
    (map digit-map a (list "0" "1") (list (str c b) (str c b)))
    (list a (str c b))))

(defn dft [ls]
  (mapcat (fn [e]
            (if (list? e)
              e
              (dft e)
              )) ls))
(defn process [ls] 
  (loop [[a b & tail] ls
         out '()] 
    (if (empty? tail) 
      (sort-by (fn [[a b]] a) (conj out (list a b))) 
      (recur tail (conj out (list a b))))))

(defn huffman [fs] 
  (let [tree (huffman-tree fs)]
    (process (dft (map 
      digit-map 
      tree 
      (list "0" "1")
      (list "" ""))))))

There’s probably a lot of room to optimize and shortcut a lot of what I did. This was a three star problem, though, so I’m sure that most of the optimization is going to be in the flattening code.

99 Clojure Problems (48)

Yesterday I was moping that I wasn’t able to do problem 48. Luckily for me, commenter Mark was able to show me that apply can be used to take each item of a list as separate parameters to that function. (Instead of taking the whole list.)

This gives me the following:

; P48 (**) Truth tables for logical expressions (3).
(comment "Generalize problem P47 in such a way that the logical expression may contain any number of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table for the expression Expr, which contains the logical variables enumerated in List.") 
(defn truth-table [n] 
  (loop [nleft n
         combos (list (list ))]
    (if (zero? nleft) 
      combos
      (recur (dec nleft) (concat (map #(conj % true) combos) (map #(conj % false) combos))))))

(defn table2 [nparams func] 
  (let [tfls (truth-table nparams)] 
    (doseq [ls tfls] 
      (do 
        (doseq [t ls] (print t "\t"))
        (println (apply func ls))))))

So, while it still doesn’t use the operator syntax, it does take any number of arguments as long as you tell it how many arguments there are. I’m happy with this solution, because I learned something doing it.

Badass, like REO Speedwagon or somethin'.

jon.com.org.net is using WP-Gravatar