Software Ramblings

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

Tweet This Post Digg This Post Reddit Stumble This Post

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

Tweet This Post Digg This Post Reddit Stumble This Post

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

Tweet This Post Digg This Post Reddit Stumble This Post