Kata Eighteen requires some code to calculate transitive dependencies, i.e. how dependencies propagate between things. Here is my solution.

class Dependencies

def initialize()
@direct = Hash.new
end

def add_direct(item, dependants)
@direct[item] = dependants
end

def dependencies_for(item)
dependants = []
toBeProcessed = @direct[item].clone
while not toBeProcessed.empty?
x = toBeProcessed.shift
if x != item and not dependants.include?(x)
dependants << x toBeProcessed.concat(@direct[x]) if @direct.include?(x) end end return dependants.sort! end end [/sourcecode]

Kata five requires the implementation of a Bloom filter. Here is my solution in Ruby using a non-optimized bitmap implementation and a reduced MD5 digest for the hashing functions.

class BloomFilter

def initialize(dictionary, num_bits, num_hashes)
@bitmap = Bitmap.new(num_bits)
@hashes = Array.new(num_hashes) { |i| BloomHash.new(i, num_bits-1) }

# compute the hash values for each word in the dictionary
# and set the appropriate bits in the bitmap
File.new(dictionary, ‘r’).each_line do |word|
@hashes.each { |h| @bitmap[h.compute(word.chomp)] = 1 }
end
end

def search(word)
@hashes.each { |h| return false if @bitmap[h.compute(word)] == 0 }
return true
end

end

class BloomHash

def initialize(seed, max_value)
@offset = seed
@num_digits = 0
@max_value = max_value
while(max_value > 0) do
@num_digits += 1
max_value >>= 4
end
end

def compute(word)
digest = Digest::MD5.hexdigest(word)
return digest[@offset, @num_digits].to_i(16) % @max_value
end

end

class Bitmap < Array def initialize(size) super(size) self.fill(0) end end [/sourcecode]

Dave Thomas maintains a blog of “Code Kata’s”. He describes a code kata as being a practice session for practicing coding skills:

Each is a short exercise (perhaps 30 minutes to an hour long). Some involve programming, and can be coded in many different ways. Some are open ended, and involve thinking about the issues behind programming. These are unlikely to have a single correct answer.

Here are two of my solutions for kata two using Ruby. The first uses recursion and the second uses an iterative approach.

Recursive solution …

# Recursive implementation
def chop(target, values)
  # Special handling for zero and single element arrays
  return -1 if values.empty?

  return ((target == values[0]) ? 0 : -1) if values.length == 1

  # Try the bottom half first
  pos = chop(target, values[0, values.length/2])
  return pos if pos != -1

  # Then the upper half ... remember that the returned 
  # position is relative to the middle of the array.
  pos = chop(target, values[values.length/2, values.length-1])
  return pos + (values.length/2) if pos != -1

  # Didn't find what we were looking for
  return -1
end

Iterative solution …

# Iterative implementation
def chop(target, values)
start = 0
stop = values.length # stop indexes one past the end of the array

# loop until something is found or until we
# run out of elements to search
while start != stop
# Find the middle
mid = start + (stop – start) / 2

# Check to see if we got lucky
return mid if values[mid] == target

# Not this time … so lets see which half it might be in
if target < values[pos] stop = mid else start = mid + 1 end end # Didn't find what we were looking for return -1 end [/sourcecode]