At SCNA 2012 I entered into a kata battle against Aaron Bedra. The idea was that we'd both perform the Coin Changer Kata live in front of all the conference attendees. The winner of the battle was to be determined by a combination of speed, creativity, performance, etc... Now, don't tell Aaron, but I was terrified to battle him. We were both doing our kata in Clojure and, well, Aaron is one of the Clojure overlords. So I prepared well in advance.
I recorded the kata and posted it on Vimeo if you'd like to see the result. In preparing, I took the opportunity to really explore Unclebob's Transformation Priority Premise. The idea that a better algorithm could be reached by always choosing the highest priority transformation was fascinating. I'd seen Unclebob's examples but I had to try it for myself. And it worked!
Before digging into my code, Unclebob has roughly 12 transformations (I've seen difference version of his list). As I pondered these transformations, I found it simpler to think about them in terms of the resulting code, and that led me to the short list below.
constant: a value
scalar: a local binding, or variable
invocation: calling a function/method
while loop: applies to
forloops as well
assignment: replacing the value of a variable
My goal in preparing the Coin Changer Kata was to develop an algorithm that uses pieces of code that fell highest on the list and try to avoid those that fell lower on the list. For example,
constants are first on the list can can be added to your code with little thought. Whereas
assignments are the worst type of code and should be avoided more than anything else.
Coin Change is a small kata and my rendition went through 6 distinct transformations, each triggered by a specific test case. I'm going to score them as we go.
This is just to get the ball rolling. The
change-for function simply returns an empty vector (
: constant = 1
- Total = 1
Here I added an
if form which falls into #4 conditional and also requires another constant (
). In hindsight this was wrong and step #3 below is much simpler. But my 'fake it 'til you make it' instincts kicked in and made me put that
if: conditional = 4
(<= amount 0): invocation + constant = 4
: constant = 1
- Score Adjustment = 9
- Total Score = 10
It's all pennies at this point so the amount represents the number of pennies we need. As you can see this is much better than the
if in the previous step. So let's score this as though we skipped transformation #2.
(repeat 1): invocation + constant = 4
take: invocation = 3
: constant = -1 (this constant disappeared)
- Score Adjustment = 6
- Total = 7
My knee-jerk reaction was to add another
if here, and in early practice that's exactly what I did. It led down an expensive road that involved loops and more conditionals. After a while I realized I could avoid the
if with the rather large transition above.
(rem amount 5): invocation + constant = 4
amount-for-pennies: scalar = 2
(int (/ amount 5)): invocation + invocation + constant = 7
nickels: scalar = 2
(take nickels (repeat 5)): invocation + invocation + constant = 7
concat: invocation = 3
- Score Adjustment = 4 + 2 + 7 + 2 + 7 + 3 = 25
- Total = 32
This transition is the most fascination of all. By introducing another coin denomination (dimes), the calculations get nested one level deeper. In other implementations you'll see nested loops. Those are expensive according to TPP. However in this case, the code almost writes itself. All of the expressions remain in their basic form, but they get turned into functions and their constants turn into scalars. Let's be careful to score only the additional cost of the scalars.
denominations [10 5 1]: scalar = 2
#(rem %1 %2): scalar + scalar = 3 (
%2, only 1 extra cost)
reductions: invocation = 3
#(int (/ %1 %2)): scalar + scalar = 3 (constant turns into a scalar)
map: invocation = 3
#(take %1 (repeat %2)): scalar + scalar = 3 (%2 used to be a constant)
mapcat: invocation = 0 (used to be
concat... just a different invocation)
(take amount-for-pennies (repeat 1)): invocation + invocation + constant = -7 (this code disappeared!)
- Score Adjustment = 2 + 3 + 3 + 3 + 3 + 3 + 0 - 7 = 10
- Total = 42
To handle quarters we simply add 25 to the denominations. No significant code change is required. Just to check my math, I'll score the end result.
denominations [25 10 5 1]: scalar = 2
amounts (reductions #(rem %1 %2) amount denominations): scalar + invocation + invocation + scalar + scalar = 12
coins (map #(int (/ %1 %2)) amounts denominations): scalar + invocation + invocation + invocation + scalar + scalar = 15
(mapcat #(take %1 (repeat %2)) coins denominations): invocation + invocation + scalar + invocation + scalar = 13
- Total = 2 + 12 + 15 + 13 = 42
It all adds up!
Alternative Solution in Ruby
In this Clojure solution I managed to avoid the more complex transitions: conditional, while loop, and assignment. I feel like the result is about as simple as can be. But I'm curious if that's true.
My colleague Ben Voss has also done the Coin Changer Kata, except in Ruby. His bite size solution is below. Let's see how it scores.
change = : scalar = 2
coins = [25,10,5,1]: scalar = 2
coins.each do |coin|: invocation + scalar + invocation = 8 (each + block invoked with coin param)
while n >= coin: while loop + invocation = 8
change << coin: invocation + assignment = 9 (state change implies assignment)
n -= coin: invocation + assignment = 9
- Total = 2 + 2 + 8 + 8 + 9 + 9 = 38
Well, according to my scoring system, this Ruby implementation beats my Clojure implementation despite leaning on the complex end of the the transformation priorities.
Personally, I'm left with more questions than answers.
- Are the transformations priorities in the right order?
- Is the list of transformation complete?
- Does this linear scoring system make sense?
- Is there a simpler solution in Clojure?
Nonetheless, I'm intrigued by the Transformation Priority Premise and plan to investigate further.