Binary Tree in Ruby

I've returned back to Dave Thomas's katas and picked up number 11: Sorting. Harking back to the reuse we saw in the data munging kata we must sort through a pair of unordered lists efficiently without using built in libraries. I chose to implement a binary tree and enjoyed reminding myself of this algorithm very much. As usual, source is at the GitHub.

    def insert(node)
      self.count_all = self.count_all + 1
      insert_left(node) if node.word < word
      self.count = count + 1 if node.word == word
      insert_right(node) if node.word > word
    end

Travel Itinerary Algorithm in Ruby

I've found a great new site for interesting and challenging programming exercises called TalentBuddy. Today I completed a fairly straight forward algorithm to reconstruct a travel itinerary from a pair of parallel arrays containing all the history departures and destinations. One of the neat things about TalentBuddy is that they expose your work to fairly large data sets (around 10,000 elements) and have a two second timeout, so implementations must be efficient.

My implementation begins by mapping the parallel arrays to a hash of destinations and departures. Then we calculate the first departure by getting the intersection of the two original arrays. Then a loop begins iterating through all destinations, retracing the history. This is made easy by the fact that no destination is visited twice. Finally, we have to handle the final case where the loop terminates when no additional destinations are found, printing the final destination. As always, full source is on GitHub

class PlaneTickets
  def get_journey(departure_ids, destination_ids)
    destination_for = map_departures_to_destinations(departure_ids, destination_ids)

    next_departure = (departure_ids - destination_ids).first

    while next_departure
      puts next_departure

      last_departure = next_departure
      next_departure = destination_for[next_departure]
    end

    puts destination_for[last_departure]
  end
end

Product Pricing Kata in Ruby

Continuing along with Dave Thomas's kata series, I'd like to share my implementation of the Product Pricing kata where we're asked to implement a checkout system that accepts rules for different pricing strategies. This immediately reminded me of my FizzBuzz implementation. In the end it was actually a fairly straight forward implementation of the Strategy pattern. The more challenging part of the exercise was extracting the actual pricing rules from the supplied test suite; a user story is often easier to read than a test of very specific behavior.

In the end, I was pleased with the rule set I implemented. For the full solution, please visit GitHub.

def rules
    [
        QuantityDiscountRule.new(sku: "A", quantity: 3, price: 30),
        QuantityDiscountRule.new(sku: "B", quantity: 2, price: 15),
        RegularPriceRule.new({
                                 "A" => 50,
                                 "B" => 30,
                                 "C" => 20,
                                 "D" => 15
                             })
    ]
end

Data Munging Kata in Ruby

Back in 2007, Dave Thomas posted a series of katas that continue to have an enduring appeal. The katas ranged from algorithm implementations to thinking exercises. This Data Munging kata had a particularly real world flare by focusing on data munging and algorithm reuse.

In short, the kata asks you to parse two data files and determine the minimum variance between two fields in each data set. The idea is to implement a solution for the first data set without reuse in mind. Next, implement a solution for the second data set and extract out the common, minimum variance algorithm between the two solutions. Nice!

I was pleased with my solution of passing in a data structure to my SpreadCalc class as well as the min_method and max_method the class could use to query the data structure to determine variance. This design would allow the class to be used on any data set that could respond to a method call and allow for the extension into all sorts of calculations related to minimums and maximums in a dataset.

class SpreadCalc
  def initialize(spread_data: spread_data, max_method: max_method, min_method: min_method)
    @spread_data = spread_data
    @max_method = max_method
    @min_method = min_method
  end

  def minimum
    min_index = 0
    min_spread = calc_spread(spread_data[min_index])

    spread_data.each_with_index do |data, i|
      spread = calc_spread(data)
      if spread < min_spread
        min_index = i
        min_spread = spread
      end
    end

    spread_data[min_index]
  end
end

I was also able to extract out a common algorithm for parsing the data files even though they were in slightly different formats. Although not intentional, I was in the mindset of extracting common functionality and the duplication was quickly obvious. I suppose that's the point of the kata! You can find the full source for my implementation on Github.

FizzBuzz in Ruby

FizzBuzz is a common and simple exercise in implementing the Strategy pattern. A brief synopsis of the Kata is as follows:

Print the numbers one through 100.
If the number is divisible by 3, print FIZZ.
If the number is divisible by 5, print BUZZ.
If the number is divisible by both, print FIZZBUZZ.

Using Ruby, the algorithm for this is quite straight forward using conditionals:

(1..100).each do |i|
  if i%3==0 and i%5==0
    puts "FIZZBUZZ"
  elsif i%3==0
    puts "FIZZ"
  elsif i%5==0
    puts "BUZZ"
  else
    puts i
  end
end

The kata only becomes interesting when you add an additional requirement; don't use conditionals. And of course, test drive your implementation. You can see my implementation on GitHub. I implemented two classes for processing a digit: Fizz and Buzz. These processors responded to process and processable? and were injected into a FizzBuzzRunner class along with the range. Additionally a default processor PassThrough was injected to the runner, which would be applied if no other processor was applicable and shared the same interface as the other processors.

The runner would query applicable_processors, asking each if the digit was processable?. If no processor was applicable, it would use the default, PassThrough. After collecting the applicable_processors, the results_from each processor were collected into an array. This allowed my final algorithm algorithm to read like well written prose.

class FizzBuzzRunner

  def initialize(range: range, processors: processors, default_processor: default_processor)
    @range = range
    @processors = processors
    @default_processor = default_processor
  end

  def as_string
    as_array.join(" ")
  end

  def as_array
    range.collect { |i| results_from(applicable_processors(i), i) }
  end
end