Tag Archives: programming

While the exact usage of games from this era is unclear, computer archaeologists have observed that they primarily served as collectables for mentally ill obsessives. These “gamers” would pin the wares they acquired from procurers into electronic albums, where the games remained unplayed to preserve their purity.

… and the Student Was Enlightened

As a huge fan of the ancient Tao of Programming text, I was happy to see someone returning to the format with a more modern programming spin.

The Abbess Jinyu was inspecting the state of the Laughing Monkey clan. In the hall she came upon a half-drowned monk, soaked and shivering.

“Explain,” said the Abbess.

“The m-m-master commanded me to t-take his coracle out onto the r-r-river,” said the monk through chattering teeth. “When I was far from shore I discovered that it had m-m-many holes in the sides. M-most were plugged with corks but t-t-t-two had been overlooked. Had I not stopped them with my f-f-fingers I would have p-perished.”

The Abbess bowed and went in to see the Java master.

“Explain,” said the Abbess, indicating the monk.

“That monk was given the task of implementing the Shopping Cart for our new site,” said the master. “He discovered that if a particular database entry was not initialized, attempts to display the Shopping Cart would fail. So the monk found every page that offered a link to the Shopping Cart and attempted to initialize the database entry there. There were over a dozen such pages. Lamentably, two were overlooked.”

The Abbess struck the master with her cane.

“Next time,” she said, “Drill more holes.”

More thought and smile provoking koans can be found at The Codeless Code

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)
              (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 
      (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) 
      (recur (dec nleft) (concat (map #(conj % true) combos) (map #(conj % false) combos))))))

(defn table2 [nparams func] 
  (let [tfls (truth-table nparams)] 
    (doseq [ls tfls] 
        (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.

99 Clojure Problems (46, 49)

I had some difficulty with the “Logic and Codes” section, since neither Prolog or Scala are really all that lisp like.

Here’s my answer for 46. Many thanks to Brian Carper for responding to my StackOverflow question. It really helped me to reformulate this question with more of a clojure style than a Scala or Prolog style.

; P46 (**) Truth tables for logical expressions.
(comment "Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed. Note that A and B can be Prolog goals (not only the constants true and fail).")
(comment "A logical expression in two variables can then be written in prefix notation, as in the following example: and(or(A,B),nand(A,B)).")

(defn not_ [a] (if a false true))
(defn and_ [a b] (if a (if b true false) false))
(defn or_ [a b] (if a true (if b true false)))
(defn nand_ [a b] (not_ (and_ a b)))
(defn nor_ [a b] (not_ (or_ a b)))
(defn xor_ [a b] (or_ (and_ a (not_ b)) (and_ (not_ a) b)))
(defn impl_ [a b] (or_ (not_ a) (and_ a b)))
(defn equ_ [a b] (not_ (xor_ a b)))

(comment "Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.")
(defn table [f] 
  (doseq [a '(true false)
        b '(true false)] 
     (println a "\t" b "\t" (f a b))

I skipped number 47 (turning the functions into operators) because clojure doesn’t really deal with infix notation at all. It seems really foreign to me to try to write (a and b). I can see doing this in ruby


or f#

a |> and b

but not clojure.

I skipped number 48, because I couldn’t figure out how to count the parameter “arity” of the function being passed in. Even with the number of parameters being passed in, I wasn’t able to figure out how to pass a list as the parameters to a function. (Basically converting (func ‘(a b c)) to (func a b c) with a simple bit of code.

Here’s my answer to number 49, which was mercifully easy after messing with 48 for a little while.

; P49 (**) Gray code.
(comment "An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,") 
(comment "n = 1: C(1) = ['0','1']. ")
(comment "n = 2: C(2) = ['00','01','11','10'].")
(comment "n = 3: C(3) = ['000','001','011','010','110','111','101','100'].")

(defn gray [n] 
  (loop [nleft n
         combos (list (list ))]
    (if (zero? nleft) 
      (map #(apply str %) combos)
      (recur (dec nleft) (concat (map #(conj %1 1) combos) (map #(conj %1 0) combos)) ))))

I did not do result caching. I couldn’t figure out where to start with it, and this code is so devilishly simple that I can’t figure out where I would store anything for future use.