Clojure Kata Two: Karate Chop (Pt. 2)
March 7, 2010
This is the second attempt at a Clojure-based solution to the Karate Chop kata detailed at http://codekata.pragprog.com/2007/01/kata_two_karate.html
Source code is available from BitBucket at http://bitbucket.org/metaljoe/metaljoe_codekata/ and is offered under the liberal MIT License. Since the aim of a kata is to learn and become a better programmer, feedback is always welcome.
Since the previous solution became a recursive one, my aim for this attempt was to work on an iterative implementation. Concerned about the rather ugly feel to the recursive code, I was also looking to produce something a bit more compact, a bit more elegant.
The code actually came to me pretty quickly compared to the first attempt. One advantage is that the problem domain is clearer on the second attempt, my brain has had time to consider the pitfalls and map out a more concise understanding of the problem. The other factor is that writing my own Clojure code, as opposed to quick REPL exploration or fill-in-the-blank exercises, has become more natural. I have begun to start thinking in Clojure. Note that I said “have begun to” – I still have more work to do on that front.
As far as implementation went, it was pretty smooth until I hit one snag: an infinite loop. It took a while to figure out what was going on, until I spotted a glaring issue. If the slice/partition of the list I’m looking at reaches one element, I check it for a match. If it didn’t match, I would loop around and search it again. An embarrassing newbie error, but a useful mistake to make. I added the appropriate check and all the tests passed.
After completing the implementation I spotted the second mistake when I reviewed the code later on. I was testing for an empty list on each iteration. While it has no impact on the output, it’s an unnecessary check for the implementation – if the list does suddenly become empty, we have bigger problems!
One thing that did intrigue me was that with almost no effort, the solution was much smaller and more readable than the first approach. I usually find the opposite with recursive versus iterative code, but in the case it’s probably because the problem seems more natural expressed iteratively. Or maybe my recursive approach just sucked :-)
Here’s the completed algorithm, with tests removed and the code tidied for clarity. See the Mercurial repository at BitBucket for the original source.
(defn chop [item list] (if (empty? list) -1 (loop [ min 0 mid (quot (count list) 2) max (count list)] (if (= item (get list mid)) mid (if (or (= mid min) (= mid max)) -1 (if (< item (get list mid)) (recur min (quot (+ mid min) 2) mid) ; look left (recur mid (quot (+ mid max) 2) max))))))) ; look right
If I broke my rule to revisit the code, I’d change a few minor things for readability. For example: why did I put those two comments there, and not elsewhere? The loop initialisation looks a bit of a blur at first glance, the or statement might need to be wrapped in an intention-revealing function name. However, the code is good enough for the task at hand and that’s all that really matters.