Posted by Tom Moertel
Fri, 28 Apr 2006 20:30:00 GMT
At last night’s
meeting
of the Pittsburgh Coding Dojo, we worked
on the Supermarket Pricing
Kata.
This particular kata was intended to be food for thought – a “shower
kata” – but our goal was to do some coding, so we made the problem
more concrete:
- Come up with a sensible way to represent common supermarket
pricing rules such as “buy one, get one free,” “three for a dollar,”
”$0.34 per ounce,” and so on
- Implement a method to check out a shopping cart full of goods,
applying all applicable pricing rules, and computing the total price
for the cart’s contents
Most people paired up, but I worked alone because I wasn’t ready to code right away. (Laptop issues.) At the end of the meeting, nobody had a working solution. (I guess it
was a shower kata for a reason.)
I had a partial solution, but I
didn’t like my internal representation of prices because it conflated
goods and their pricing rules.
Over lunch today I came up with a more
sensible representation and finished off my implementation.
Now I’m happy with it.
The code
Here’s my solution. I stripped the comments to emphasize the code
itself (a forest and trees thing). If you want to see the comments,
see the unstripped source.
module SupermarketPricing where
import Control.Arrow ((&&&))
import Data.List (groupBy, sort)
import Test.HUnit
type Portion = Double
type Count = Portion
type Price = Double
type Name = String
data PricingRule
= Per Portion Price
| For Count Price Price
deriving (Eq, Ord, Read, Show)
data Good
= G { name :: Name, quantity :: !Portion, rule :: PricingRule }
deriving (Eq, Ord, Read, Show)
per nm y x p = G nm y (Per x p)
each nm p = G nm 1 (For 1 p p)
for nm n p = G nm 1 (For n p p)
bogo = flip bngo 1
btgo = flip bngo 2
bngo nm n p = G nm 1 (For n' np p)
where (n', np) = (n + 1, p * n)
checkout :: [Good] -> Price
checkout =
checkoutBy $ sum . map price
subtotal :: [Good] -> [((Portion, Name), Price)]
subtotal =
checkoutBy $ map ((quantity &&& name) &&& price)
checkoutBy :: ([Good] -> a) -> [Good] -> a
checkoutBy f =
f . map (foldl1 combine) . groupByName . sort
where
groupByName = groupBy (\g1 g2 -> name g1 == name g2)
price :: Good -> Price
price (G nm y (Per x p)) = y * p / x
price (G nm m (For n p p2)) = (m r) * p / n + r * p2
where
r = fromIntegral $ round m `rem` round n
combine :: Good -> Good -> Good
combine g1@(G nm x rule) g2@(G nm2 x2 rule2)
| nm /= nm2 || rule /= rule2
= error $ "can't combine incompatible goods " ++ show [g1, g2]
| otherwise
= G nm (x + x2) rule
Read on for an explanation of the code and my unit tests.
Read more...
Posted in programming, haskell, pittsburgh
Tags coding, dojo, haskell, katas, pricing, supermarket
no comments
no trackbacks
Posted by Tom Moertel
Thu, 20 Apr 2006 21:36:00 GMT
Last year, I wrote about some beekeeping stories on Kuro5in.org. Interesting stuff.
The stories, like the bees, stopped when winter came. Now that spring is here, the bees have emerged from their hive, and the beekeeping guy, xC0000005, has resumed his writing.
At this time, he has a story on the front page: Tales from the Hive – Birth of a Package. But the good stuff to come will appear in his diary. Keep an eye on it.
Posted in interesting stuff
no comments
no trackbacks
Posted by Tom Moertel
Wed, 12 Apr 2006 16:29:00 GMT
If you live anywhere near Pittsburgh and are interested in Perl, have
I got a couple of announcements for you:
First, the ever-fascinating Mark Jason
Dominus is speaking tonight (2006-04-12, now passed) on
Improving Your Perl Code at
the regular meeting of the Pittsburgh Perl
Mongers. If you are interested in Perl,
be there. (You don’t need to be a Perl Monger to attend.) Mark is a
great speaker and wrote one of my favorite Perl books, Higher Order
Perl, which puts the fun in functional
programming.
Second, The Pittsburgh Perl Workshop is on. Put a big circle around this date on your
calendar: Saturday, 23 September 2006. It’s
a full day of sleeves-rolled-up Perl fun, all focused on the sweat-inducing theme of Perl At Work. To top it off, the Workshop is dirt cheap, especially if you get the 50-percent “Early Bird” discount. (Hint:
register now.)
It’s a fun time for Perl folks in Pittsburgh.
Update: MJD gave his talk, and it rocked. If you missed it, you should find a time machine now and use it to take yourself back to Wednesday evening to hear his talk. Or you could find out when he is speaking in the future and be there. Either way, don’t miss out again.
Posted in perl, pittsburgh
no comments
no trackbacks
Posted by Tom Moertel
Fri, 07 Apr 2006 15:55:00 GMT
One of the things I miss when coding in Ruby is
inexpensive function composition. In Haskell, for example,
I can compose functions using the dot (.) operator:
inc = (+1)
twice = (*2)
twiceOfInc = twice . inc
Because of Ruby’s open classes, however, I can easily
add the feature to the language. In
the code below, I introduce
Proc.compose and overload the
star (
*) operator for the purpose:
# func_composition.rb
class Proc
def self.compose(f, g)
lambda { |*args| f[g[*args]] }
end
def *(g)
Proc.compose(self, g)
end
end
And that’s all it takes:
$ irb --simple-prompt -r func_composition.rb
>> inc = lambda { |x| x + 1 }
=> #<Proc:0x00002aaaaaad7810@(irb):1>
>> twice = lambda { |x| x * 2 }
=> #<Proc:0x00002aaaaabd2d18@(irb):2>
>> inc[1]
=> 2
>> twice[2]
=> 4
>> twice_of_inc = twice * inc
=> #<Proc:0x00002aaaaab32458@./func_composition.rb:3>
>> twice_of_inc[1]
=> 4
>> twice_of_inc[2]
=> 6
Now, isn’t that refreshing?
Posted in functional programming, ruby
Tags fp, functional_programming, ruby
2 comments
no trackbacks
Posted by Tom Moertel
Wed, 05 Apr 2006 19:18:00 GMT
On the WPLUG mailing list I came across a post
about the formation of a Pittsburgh Coding
Dojo. The idea is to get a bunch
of hackers together and have them work on solving a challenge
problem with the goal of sharpening their programming skills and
learning from each other.
There was a trial meeting on 31 March that focused on The Bowling Game
Kata.
The challenge was essentially to write some code that scores
a full (ten-frame) game of bowling. A game is represented by a series
of “rolls,” each being the number of pins knocked down by a
roll of the bowling ball. The scoring function must
determine frame boundaries from the sequence of rolls and score all
ten frames according to the rules of bowling, i.e., taking into account
spares and strikes and the final frame.
The challenge sounded like a fun lunch-break problem, and so I
whipped up the following solution in Haskell. (You might find
it interesting to compare this solution to the Java-based
solutions on the web.)
module Bowling (score) where
import Test.HUnit
score rs = sc 0 1 rs
sc s 11 _ = s
sc s f rs = case rs of
10:rs' -> sc' 3 rs'
x:y:rs' | x + y == 10 -> sc' 3 rs'
| otherwise -> sc' 2 rs'
_ -> error "ill-formed sequence of rolls"
where
sc' n rs' = sc (s + sum (take n rs)) (f + 1) rs'
Here are my unit tests:
tests = test
[ "gutters" ~: score (rep 20 0) ~?= 0
, "ones" ~: score (rep 20 1) ~?= 20
, "fives" ~: score (rep 22 5) ~?= 150
, "strikes" ~: score (rep 12 10) ~?= 300
, "1 + gutters" ~: score (1 : rep 19 0) ~?= 1
, "first spare" ~: score (5:5:5 : rep 17 0) ~?= 20
, "first strike" ~: score (10:5:5 : rep 17 0) ~?= 30
, "last spare" ~: rscore (5:5:5 : rep 18 0) ~?= 15
, "last strike" ~: rscore (5:5:10 : rep 18 0) ~?= 20
]
where
rep = replicate
rscore = score . reverse
If you have a little free time, code up a solution in your
favorite language.
Posted in programming, haskell, pittsburgh
Tags bowling, haskell, kata
4 comments
no trackbacks
readers