Saturday, November 20, 2010

Code Kata Nine: Supermarket Checkout, Part B (Decouple)

   As you may recall, before life (real life, not Conway's) got rather busy, I left you hanging off the cliff of Dave Thomas's Code Kata #9.  I had finished the "just make it work" part.  Now for the "decouple the price rule format" part.

   As Dave (the other Dave) says, there are many ways to do it.  I chose to use the Strategy Pattern.  (If you're not familiar with design patterns, you really need to go read up on them.)

   As you can see in the code below, the piece that gets swapped out is actually very small.  It does nothing but parse the pricing rules.  How they get applied remains the same.

#! /usr/bin/ruby

# Dave Thomas Code Kata #9: Supermarket Checkout
# See http://codekata.pragprog.com/2007/01/kata_nine_back_.html
# Solution by Dave Aronson
# VERSION B: decouple the pricing format.


class CheckOut

  def initialize rules, parser
    @items = {}
    # only really need this in total, but IRL a customer
    # might just want a price-check on something....
    @pricer = Pricer.new rules, parser
  end

  def scan sku
    @items[sku] = 0 if @items[sku].nil?
    @items[sku] += 1
  end

  def total
    tot = 0
    @items.each_pair { |sku, qty| tot += @pricer.price sku, qty }
    tot
  end

end


# separate from CheckOut 'cuz IRL there may be price-check stations
class Pricer

  def initialize rules, parser
    @prices = parser.parse rules
  end

  def price sku, quantity
    qty = quantity
    tot = 0
    while qty > 0 do
      deal_qty, deal_price = find_best_deal sku, qty
      num_deals = qty / deal_qty
      tot += num_deals * deal_price
      qty -= num_deals * deal_qty
    end
    tot
  end

  private

  def find_best_deal sku, qty
    prices = @prices[sku]
    if prices.nil?
      puts "ERROR: NO PRICE FOUND for #{sku}!"
      return nil
    end
    deal = nil
    prices.each_pair do |rule_qty, rule_tot|
      if rule_qty > qty then
        break
      else
        # Inefficient to keep overwriting this,
        # but shouldn't happen too much....
        deal = [rule_qty, rule_tot]
      end
    end
    puts "ERROR: NO PRICE FOUND for #{qty} of #{sku}!" if deal.nil?
    deal
  end

end


# now we get to the heart of the matter:
# different ways to parse prices.
# essentially the strategy pattern.


class CSVPriceParser
  def parse rules
    prices = {}
    rules.each do |line|
      line.chomp!
      cur_sku, qty, tot = line.split ","
      prices[cur_sku] = {} if prices[cur_sku].nil?
      prices[cur_sku][qty.to_i] = tot.to_i
    end
    prices
  end
end


CSV_RULES = [
  "A,1,50",
  "A,3,130",
  "B,1,30",
  "B,2,45",
  "C,1,20",
  "D,1,15",
]


class YAMLPriceParser
  def parse rules
    prices = {}
    cur_sku = ''
    rules.each do |line|
      line.chomp!
      if line[0..0] == "\t"
        qty, tot = line[1..-1].split "\t"  # 1 to ignore tab
        # really should check for cur_sku not being set yet,
        # though that would mean it's an invalid file....
        prices[cur_sku] = {} if prices[cur_sku].nil?
        prices[cur_sku][qty.to_i] = tot.to_i
      else cur_sku = line
      end
    end
    prices
  end
end


YAML_RULES = [
  "A",
  "\t1\t50",
  "\t3\t130",
  "B",
  "\t1\t30",
  "\t2\t45",
  "C",
  "\t1\t20",
  "D",
  "\t1\t15",
]


# TESTS, initially supplied by Dave Thomas,
# but refactored by Dave Aronson
# to support swapping out strategies

require 'test/unit'

class TestPrice < Test::Unit::TestCase

  def helper_test_incremental rules, parser
    co = CheckOut.new rules, parser
    assert_equal 0, co.total
    co.scan "A";  assert_equal( 50, co.total)
    co.scan "B";  assert_equal( 80, co.total)
    co.scan "A";  assert_equal(130, co.total)
    co.scan "A";  assert_equal(160, co.total)
    co.scan "B";  assert_equal(175, co.total)
  end

  def helper_test_totals rules, parser
    assert_equal(  0, price("", rules, parser))
    assert_equal( 50, price("A", rules, parser))
    assert_equal( 80, price("AB", rules, parser))
    assert_equal(115, price("CDBA", rules, parser))

    assert_equal(100, price("AA", rules, parser))
    assert_equal(130, price("AAA", rules, parser))
    assert_equal(180, price("AAAA", rules, parser))
    assert_equal(230, price("AAAAA", rules, parser))
    assert_equal(260, price("AAAAAA", rules, parser))

    assert_equal(160, price("AAAB", rules, parser))
    assert_equal(175, price("AAABB", rules, parser))
    assert_equal(190, price("AAABBD", rules, parser))
    assert_equal(190, price("DABABA", rules, parser))
  end

  def price goods, rules, parser
    co = CheckOut.new rules, parser
    goods.split(//).each { |item| co.scan(item) }
    co.total
  end

  def helper_test rules, parser
    helper_test_incremental rules, parser
    helper_test_totals rules, parser
  end

  def test_rulesets
    helper_test CSV_RULES, CSVPriceParser.new
    helper_test YAML_RULES, YAMLPriceParser.new
  end


end

   As always (just had to continue starting each paragraph with "As"!), it's now your turn.  How would you have designed and/or implemented this differently?  Leave a comment.

4 comments:

  1. What if the price rule was "buy three boxes of cereal and get one free"? Your collection wouldn't notice that these counted as the same items since they had different SKUs. Similarly, what if the price rule is extended to specify that the cheapest of the four is the free one?

    ReplyDelete
  2. Hi Joe!

    The original exercise only identifies items by SKU, so presumably there is no intent to group them into similar items so as to enable discount across multiple SKUs.

    BUT...

    Now we get to contemplate what we would do if we had built a system like this, and the customer now comes to us and says they want such a feature. (You know, the kind of situation that happens after they swear up and down during the initial consultations, that they would never need such a feature. ;-) )

    Off the top of my head, one design is to tag each SKU with one or more tags. Add logic to the deal parser to allow the thing the deal applies to, to be a tag instead of a SKU; they should be in different formats somehow so we know whether something's a SKU or a tag. Add logic to the pricer to check the tags of each SKU bought, recording items and quantities by tag as we go; at the end, see if there are any deals that apply to the tags, and whether they can be applied to the combo we bought.

    Whatcha think?

    Thanks,
    Dave

    ReplyDelete
  3. As I just read your response to someone else on LinkedIn (http://www.linkedin.com/groupAnswers?viewQuestionAndAnswers=&discussionID=107978669&gid=40893&trk=eml-anet_dig-b_nd-pst_ttle-cn&ut=2JAQ3ZweePpBc1), I am just now reading this article (almost a year later).

    As to your point to Joe -- the SKU is just another tag, a way of identifying an item, generically or specifically. So, in Joe's situation I would consider recording items via these tags (as you say). Then the tricky part is knowing which deal to apply to which tag, or set of tags. I would probably abstract the deals as first-class citizens. Then I might use the Visitor pattern as an item is scanned, visiting all of the deals allowing them to accept the item or not. Deals would then need to vie for the "ownership" of any given item, unless we allow the application of multiple deals to a single item, which typically isn't allowed IRL.

    ReplyDelete
  4. Hi Jason!

    About reading it a year later, maybe now you'll subscribe and get 'em hot off the virtual press! :-) When I wrote the reply on LI, I had totally forgotten about my reply above to Joe. Guess I think in tags a lot!

    I like your idea about visiting the current set of deals and having them vie to be picked. That would be very easy for each individual SKU, where the score would be simple lowness of price, but when it gets into overlapping possibilities, it could get quite hairy. Imaging you have one special on Post Raisin Bran, another on Post cereals, and another on all cereals. A customer buys a box of PRB, some other Posts, and some Kelloggs. But some of the deals are BOGOs, some are buy two get a third 1/3-off, etc. How to group them optimally? For a relatively small purchase, brute-forcing all possible combos could be practical, but it could quickly explode. Sounds "NP-tough" to me. :-)

    ReplyDelete