Transformation Priority Premise Applied

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
conditional : if/switch/case/cond
while loop : applies to for loops 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.

Transformation #1

;[0 []]
(defn change-for [amount]
		[])

This is just to get the ball rolling. The change-for function simply returns an empty vector ([]).

Score:

[]: constant = 1
Total = 1

Transformation #2

;[1 [1]]
(defn change-for [amount]
		(if (<= amount 0)
				[]
				[1]))

Here I added an if form which falls into #4 conditional and also requires another constant ([1]). 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 there.

Score:

if: conditional = 4
(<= amount 0) : invocation + constant = 4
[1] : constant = 1
Score Adjustment = 9
Total Score = 10

Transformation #3

;[2 [1 1]]
(defn change-for [amount]
		(take amount (repeat 1)))

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.

Score:

(repeat 1): invocation + constant = 4
take : invocation = 3
[] : constant = -1 (this constant disappeared)
Score Adjustment = 6
Total = 7

Transformation #4

;[5 [5]]
(defn change-for [amount]
		(let [amount-for-pennies (rem amount 5)
								nickels (int (/ amount 5))]
				(concat
					(take nickels (repeat 5))
					(take amount-for-pennies (repeat 1)))))

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.

Score:

(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

Transformation #5

;[10 [10]]
(defn change-for [amount]
		(let [denominations [10 5 1]
								amounts (reductions #(rem %1 %2) amount denominations)
								coins (map #(int (/ %1 %2)) amounts denominations)]
				(mapcat #(take %1 (repeat %2)) coins denominations)))

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.

Score:

denominations [10 5 1]: scalar = 2
#(rem %1 %2): scalar + scalar = 3 (5 turned into %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

Transformation #6

;[25 [25]]
(defn change-for [amount]
		(let [denominations [25 10 5 1]
								amounts (reductions #(rem %1 %2) amount denominations)
								coins (map #(int (/ %1 %2)) amounts denominations)]
				(mapcat #(take %1 (repeat %2)) coins denominations)))

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.

Score:

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.

class CoinChanger
		def self.makeChange(n)
				change = []
				coins = [25,10,5,1]
				coins.each do |coin|
						while n >= coin
								change << coin
								n -= coin
						end
				end
				change
		end
end

Score:

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.