Wednesday, May 27, 2015

Exercises in Clojure with Commentary

I was recently browsing some links from my Twitter feed and came across some programming exercises and their solutions. I selected a few that I thought were interesting, solved them, and now I want to present my solutions here along with some commentary on how they were solved. I think the solutions and especially their comments might be helpful to new Clojurists as well as Java developers who are looking for some examples of why Clojure code is so much more concise. Without further ado, here they are.

Problem 1: Square Code/Crypto Square
Read all about it here and here. Basically, you do the following to encode a text string:
  1. Convert the initial string to a lowercase character string with only alpha characters
  2. Arrange the result of step 1 into a square of text (If the string length is not a square integer the last line will not be as long as the rest of the square)
  3. Create a sentence in which the "words" are the columns of the square
Here is my solution:
(require '[clojure.string :as s])

(defn crypto-square[s]
  (let[ss (-> s s/lower-case (s/replace #"[^a-z]" ""))
       l (-> ss count Math/sqrt Math/ceil int)]
    (->> ss
         (partition l l (repeat ""))
         (apply map vector)
         (map #(apply str %))
         (s/join " "))))

You can give it a try right here:

Enter text to encode:

  • This solution makes heavy use of threading macros (-> is called "Thread first" and ->> is called "Thread last"). These are great for assembling computation pipelines. These macros take the item after the arrow and repeatedly insert the argument into the next form in the pipeline, carrying forward the result into each successive form. The "first" and "last" refer to where in the succeeding form the new argument goes (first goes after the function name in the form, last goes in the last position in front of the last parens).
  • The partition function creates partitions from a sequence with a specified chunk and step size. A final default argument is used to pad the last partition when the sequence cannot be equally subdivided.
  • The default padding argument to partition along with the repeat function make ensuring that the string was square trivial. Any missing characters in a non-square string are filled in by padding with empty strings.
  • The apply method (which I use in several more of these examples) "applies" a function to a sequence by inserting the function in the first position of the sequence and evaluates the new sequence as if it were a list.
  • A key takeaway in this example is that threading computations as shown really only works with immutability and side-effect free functions. Were either of these properties missing, there are no guarantees regarding your computations and assembling these sorts of pipelines are impossible.
Problem 2: Kindergarten Garden
In this problem, described here and solved here, two rows of plants are assigned to a group of students who are sorted alphabetically by name. Each student gets a block of plants from left to right (two each in the front row and two each in the back). Depending on the letters in the diagram, you are to determine which kind of plants each student has.
;Solution 1
(defn char->plant[s]
  (map #(case %
         \V "Violets"
         \R "Radishes"
         \C "Clover"
         \G "Grass") s))

(defn kinder[names rows]
  (apply merge-with concat
           #(zipmap (sort names) (partition 2 %))
           (map char->plant (s/split-lines rows)))))

;Solution 2
(defn kinder-thread-last[names rows]
  (->> rows
       (map #(map { \V "Violets" \R "Radishes" \C "Clover" \G "Grass" } %))
       (map #(zipmap (sort names) (partition 2 %)))
       (apply merge-with concat)))
(def ch ["Alice" "Bob" "Charlie" "David" "Eve" "Fred" "Ginny" "Harriet" "Ileana" "Joseph" "Kincaid" "Larry"])
(prn ((kinder-thread-last ch rows) "David"))
;prints ("Radishes" "Violets" "Clover" "Radishes")
  • I provided two solutions. My first did not use threading macros. I think the thread last version (#2) is much easier to read. It is quite easy to see the sequence of steps being followed.
  • Another important thing to note is how I mapped the characters in the gardens to plants. I can use a case statement like what is done in the char->plant function. However, a simpler and more concise solution is to simply use a map. Clojure maps (and vectors and sets) are not just data structures, but are also functions. This may seem weird at first, but it actually makes sense. A map (in any language) is simply a discrete 1:1 function that maps keys to values. A vector is a function of its indices and a set is a function of its contents. Using this knowledge, I just mapped the characters in the strings using the map of characters to plant names as an inlined function.
Problem 3: Treasure Hunt
In the treasure hunt problem described here you are given a 2D array of two digit map coordinates. From a starting coordinate that I am assuming comes from a pirate, you look up each successive coordinate on the map by using the first and second digits of the current coordinate as the row and column on the map. Once a coordinate maps to itself, start digging, you are done.

Here is my solution:
(defn map-step[m clue]
  (let [n (get-in m [(dec (quot clue 10)) (dec (rem clue 10))])]
    (when (not= n clue) n)))

(defn treasure-hunt [m start]
  (take-while identity (iterate (partial map-step m) start)))
Here it is in action:
(def treasure-map [[34 21 32 41 25]
                   [14 42 43 14 31]
                   [54 45 52 42 23]
                   [33 15 51 31 35]
                   [21 52 33 13 23]])

(prn (treasure-hunt treasure-map 11))
;prints (11 34 42 15 25 31 54 13 32 45 35 23 43 51 21 14 41 33 52)
  • The map-step function simply computes the next step in the map. What's beautiful about this method is that it very naturally uses the Clojure get-in function to solve the problem. get-in is a Clojure function that allows you to drill down into a nested data structure by providing a vector of successive indices. Conveniently, our two-digit coordinates can be split into a vector for get-in access. Note that I do need to decrement the coordinates to make them 0 indexed.
  • The only additional logic required was the exit criteria. I compared the looked up coordinate to the input. If they are different, I return the update. Otherwise, nil is returned.
  • The treasure-hunt is where the real awesomeness happens. I can create a partial map-step function by filling in the first argument of the function with a treasure map. I now have a function that takes an [x y] coordinate and returns an [x y] coordinate. I want to repeatedly do this until I return nil. Sounds like a perfect candidate for Clojure's iterate function. iterate takes a function and an initial condition and repeatedly returns the result of the applied function and reapplies that result to itself. To determine a stopping condition, I take results while the function satisfies the identity function. Identity is a clever method that simply returns what is passed to it. In Clojure, anything not false or nil will pass logical truth tests (this is called truthiness), so as long as my function returns new coordinates I will take coordinates from it.
  • It is quite common in Clojure to store your state in a structure and do a computation that returns a new state that is similarly structured to the original. Whenever you do this, iterate may be a great option. You can take a certain number of items from the iterated function or continue until a stop condition is met.
  • Finally, this problem really is one of data navigation, and that is something Clojure excels at. Clojure is all about nested heterogeneous data structures and has many methods to safely inspect, update, and transform them. Furthermore, Clojure's semantics for truthiness and handling of nil makes what would normally be exceptional behavior simple to handle.
Problem 4: Queen Attack
The basic problem is this:  Given two queens on a chessboard, are they in an "attack" configuration. In other words, are they in a shared column, row, or diagonal. Here's a solution from my original browsing exercise. As presented here, the problem is to encode an 8x8 board using different characters. I took a different approach and simply used the coordinates of the pieces to determine if they were visible to each other.

Here is my complete solution:
(defn queen-attack?[w b]
  (let [diff (map - w b)
        zs ((juxt first second #(reduce - %) #(reduce + %)) diff)]
    (true? (some zero? zs))))
Here are a few invocations of the function with results in comments:
(prn (queen-attack? [2 3] [2 10])) ;true - same row
(prn (queen-attack? [9 10] [2 10])) ;true - same column
(prn (queen-attack? [4 3] [2 10])) ;false
(prn (queen-attack? [7 12] [5 10])) ;true - same diagonal
  • The most important thing to note in this solution is that being on the same row, column, or diagonal reduces to simple difference checks on the piece indices. A zero difference in the row or column means you are on the same row or column. If the sum or difference of the row and column change is 0 you are on the same diagonal. If this last rule doesn't make sense, stop for a second and think about it. To move diagonally, you must move the same amount up or down as you do left or right. So, the sum or difference (depending on direction) will be 0.
  • I use juxt to compute the 4 potential zeroes. I also discuss juxt at length in this post.
  • some zero? checks if any zeroes exist. If any exist, the result is true. It none exist the result is nil. Therefore, I call true? to covert a nil to false. Note that Clojure uses "truthiness" when doing logic checks (i.e. nil and false return false, everything else returns true). So, I could just as easily drop the true? check if I felt like it.
  • Probably the biggest takeaway from this problem is the difference between a standard OOP solution vs. an FP solution. In OOP the natural approach to the problem would be to start with a  nice class hierarchy such as a Board (which would contain 64 Squares). You would probably have a ChessPiece class which you'd extend into Pawn, Rook, Knight, Bishop, Queen, and King classes. At this point you'd probably determine some basic methods such as move and attack which would allow you to finally approach solving the problem. In FP, you generally think directly in terms of what you are trying to do since your domain model is just data. Had I been asked to solve the problem for all chess pieces in Clojure, I'd probably just create a multimethod that dispatches on the attacker type (:pawn, :rook, :knight, :bishop, :queen, or :king). Each resulting defmethod would be as concise as the above function.
In a few short lines, I was able to solve 4 programming puzzlers using Clojure. While none of the problems were particularly hard, each illustrated several interesting functions and aspects of Clojure programming that I thought were worth pointing out. In particular, Clojure excels at representing, manipulating, and navigating data as simple structures. I find it much easier to model the data directly using Clojure's data structures than developing elaborate class hierarchies for each problem. This way of thinking allows you to jump right into solving your problem without having to spend a lot of time figuring out how to represent the data.

If you liked this page or learned anything from it, please tweet the link,follow me on Twitter, and/or follow this blog. Your support and interest is the fuel that drives the effort.

No comments:

Post a Comment