Code Katas

Some of you may be familiar with the term kata.  It comes from martial arts, mainly karate, and means a practice exercise, especially one done over and over to train your "muscle memory".

After enough years programming, you build up similar semi-automatic approaches, like how to organize a program, or thinking imperatively or functionally, or iteratively or recursively.  Code katas help you practice such things, with deliberate emphasis on a particular aspect.  (Actually, IMHO this makes them more like Toastmasters speech projects, but that's another story.)

There are many sources of lists of code katas out there.  Recently, to sharpen my Ruby-fu, I began working through the ones that Dave Thomas, of Pragmatic Programmer fame, put up at http://codekata.pragprog.com/.  The first kata does not involve code.  So, here is my solution to the second one:

#! /usr/bin/ruby

# Dave Thomas Code Kata #2, Karate Chop
# See http://codekata.pragprog.com/2007/01/kata_two_karate.html
# Solution by Dave Aronson

# TODO MAYBE: see if I can do the helper funcs as lambdas or some such....


# version 1: iterative

def chop1 tgt, arr
  # TODO: check arg types
  # TODO: check for empty array
  hi = arr.length - 1
  lo = 0
  while hi >= lo do
     mid = (hi + lo) / 2
     test = arr[mid]
     if test < tgt: lo = mid + 1
     elsif test > tgt: hi = mid - 1
     else return mid
     end
  end
  -1
end



# version 2: recursive and not functional

def chop2 tgt, arr
  chop2_helper tgt, arr, 0, arr.length - 1
end

def chop2_helper tgt, arr, min, max
  slot = (min + max) / 2
  test = arr[slot]
  if test == tgt: slot
  elsif min == max: -1
  elsif test < tgt: chop2_helper tgt, arr, slot + 1, max
  else chop2_helper tgt, arr, min, slot - 1
  end
end



# version 3: recursive and functional, passing array slice.

def chop3 tgt, arr
  # use another func to stop having to calc middle slot over and over
  chop3_pass_mid tgt, arr, arr.length / 2
end

def chop3_pass_mid tgt, arr, mid
  # use another func to stop having to retrieve middle value over and over
  chop3_pass_test tgt, arr, mid, arr[mid]
end

def chop3_pass_test tgt, arr, mid, test
  if test == tgt: mid
  elsif mid == 0: -1
  elsif test < tgt
    chop3_fix_offset mid + 1, chop3(tgt, arr[mid + 1 .. arr.length])
  else chop3 tgt, arr[0 .. mid - 1]
  end
end

# kind of a kluge; TODO MAYBE: do something cleaner with this problem!
def chop3_fix_offset offset, result
  result == -1 ? -1 : result + offset
end



# version 4: recursive and functional, passing whole array.

def chop4 tgt, arr
  chop4_helper tgt, arr, 0, arr.length - 1
end

def chop4_helper tgt, arr, min, max
  # use another func to not have to calc midpoint over and over
  chop4_pass_midpoint tgt, arr, min, max, (min + max) / 2
end

def chop4_pass_midpoint tgt, arr, min, max, midpt
  # use another func to not have to retrieve middle value over and over
  chop4_pass_midval tgt, arr, min, max, midpt, arr[midpt]
end

def chop4_pass_midval tgt, arr, min, max, midpt, midval
  if midval == tgt: midpt
  elsif min == max: -1
  elsif midval < tgt: chop4_helper tgt, arr, midpt + 1, max
  else chop4_helper tgt, arr, min, midpt - 1
  end
end



# TESTS

require 'test/unit'

class TC_MyTest < Test::Unit::TestCase

  def setup
    @arr = [ 0, 1, 2, 3, 5, 8, 13, 21, 34 ]  # fibonacci, btw
  end

  def test_chops
    [:chop1, :chop2, :chop3, :chop4].each do |func|

      # test that each thing in there, is found
      @arr.length.times do |slot|
        tgt = @arr[slot]
        assert_equal slot, send(func, tgt, @arr), "testing #{func.to_s}(#{tgt})"
      end

      # test that a bunch of things that should NOT be in there, are not found
      [@arr[0]-1, @arr[0]-0.1, 4, 33, @arr.last+0.1, @arr.last+1].each do |tgt|
        assert_equal -1, send(func, tgt, @arr), "testing #{func.to_s}(#{tgt})"
      end

    end

  end

end

Note, I'm not saying that this is the best solution, let alone the One True Solution.  Your mileage is practically guaranteed to vary, especially on matters of style.

In fact, I'd like to hear how you would have done it differently -- feedback is how one improves.  What would you have done differently, and why?  Would it be faster, clearer, more canonically Rubyish, or what?  Inquiring minds want to know!