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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 625 other followers

%d bloggers like this: