Monday, August 07, 2006

The Change-Counting Algorithm & TDD

I recently decided to make my way through Sussman & Abelson's classic CS textbook The Structure and Interpretation of Computer Programs, partly for reasons of professionalism, partly to clarify my thoughts on "test-driven development" and algorithmic programming. Every familiar example, and nearly every question I see on the Test-Driven Development newsgroup concerns object-oriented programming. The "bowling game" is simply too trivial a counterexample, in my opinion, but we can dispute this elsewhere.

At any rate, SICP poses this problem in Chapter 1: "How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to
change any given amount of money?" There is, it turns out, a fair amount of literature on this problem (cf. David Pearson's paper, or
What This Country Needs is an 18 Cent Piece). Despite having the solution right in front of me, an implementation eluded me until I really considered the structure of the problem, which is recursive. The authors provide unequivocal hints: "Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases: 1, If a is exactly 0, we should count that as 1 way to make change; 2, If a is less than 0, we should count that as 0 ways to make change; 3, If n [the number of available denominations] is 0, we should count that as 0 ways to make change." These should be the starting points for the test-driven development of the algorithm, but I only understood their significance within the recursion after pondering the problem while riding the bus. Imagine you've got quarters and pennies, and are asked to make $.26 in change. You can try to use 1 quarter. Now you've got to make $.01 with quarters and pennies. If you use another quarter, you've then got to make - $.24, at which point condition 1 will obtain; if you use a penny, you'll then have to make $.00, at which point condition 2 will obtain (and the recursion will stop). Condition 3 will also stop the recursion, i.e., you've got no more denominations to try. Once I'd understood all this, I could eliminate some of the recursive calls by using integer division, i.e., the largest number of quarters that I can use to make a will be a / 25.

After that, I quickly wrote the following code in Python, and indeed this implementation evolved in order with precisely these tests:

import unittest

def countChange(amount, coins):
if amount == 0:
return 1
if len(coins) == 0:
return 0
if len(coins) == 1 and amount % coins[0] == 0:
return 1
currentCoin = coins[0]
remainingCoins = coins[1:]
currentPossibilities = [currentCoin * i for i in range(0, amount / currentCoin + 1)]
return sum([countChange(amount - p, remainingCoins) for p in currentPossibilities])

class TestCountChange(unittest.TestCase):
def testAmountZeroWithNoCoins(self):
self.assertEqual(1, countChange(0, []))

def testAnyAmountWithNoCoins(self):
self.assertEqual(0, countChange(100, []))

def testAmountZeroWithAnyCoins(self):
self.assertEqual(1, countChange(0, (1, 5, 10)))

def testAmountsWithOneCoin(self):
self.assertEqual(1, countChange(1, [1]))
self.assertEqual(1, countChange(5, [5]))
self.assertEqual(1, countChange(10, [10]))

def testAnyAmountWithPennies(self):
self.assertEqual(1, countChange(10, [1]))
self.assertEqual(1, countChange(10000, [1]))

def testMultiplesOfSingleCoin(self):
self.assertEqual(1, countChange(100, [5]))
self.assertEqual(1, countChange(100, [50]))

def testTwoKindsOfCoins(self):
self.assertEqual(2, countChange(10, [5, 10]))
self.assertEqual(2, countChange(7, [5, 1]))
self.assertEqual(0, countChange(7, [5, 10]))

def testTextbookExample(self):
self.assertEqual(292, countChange(100, [1, 5, 10, 25, 50]))

if __name__ == '__main__':


Devin said...

Just for fun, Ruby:

def countChange(amount, coins)
  return 1 if amount == 0
  return 0 if coins.empty?
  return 1 if coins.size == 1 and amount % coins[0] == 0
  currentCoin, remainingCoins = coins[0], coins[1..-1]
  currentPossibilities = (0..amount/currentCoin).map {|i| currentCoin * i} {|p|
    countChange amount - p, remainingCoins
  }.inject {|acc, c| acc+c}

if __FILE__ == $0
  require 'test/unit'

  class TestCountChange < Test::Unit::TestCase
    def test_textbook_example
      assert_equal 292, countChange(100, [1,5,10,25,50])

and Haskell:

import HUnit

-- countChange amount coins
countChange 0 _ = 1
countChange _ [] = 0
countChange amount [coin] =
  if amount `mod` coin == 0 then 1 else 0
countChange amount (currentCoin:remainingCoins) =
  sum $ map (\p -> countChange (amount - p) remainingCoins) currentPossibilities
  where currentPossibilities = map (currentCoin*) [0..(amount `div` currentCoin)]

testTextbookExample = TestCase $
  assertEqual "countChange" 292 (countChange 100 [1,5,10,25,50])

tests = TestList [TestLabel "testTextbookExample" testTextbookExample]
main = runTestTT tests

Anonymous said...

Howdy! This post could not be written any better! Reading through this post reminds me of my good old room
mate! He always kept chatting about this. I will forward this post to him.
Pretty sure he will have a good read. Thanks for

Feel free to visit my web blog ... mens cargo pants

Anonymous said...

Hello this is kind of of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to
manually code with HTML. I'm starting a blog soon but have no coding skills so I wanted to get advice from someone with experience. Any help would be enormously appreciated!

my web site - huggies newborn coupons

Anonymous said...

Heya! I'm at work browsing your blog from my new iphone 3gs! Just wanted to say I love reading through your blog and look forward to all your posts! Carry on the fantastic work!

Here is my page;
My web page -

Anonymous said...

Ӏ ԁon't know whether it's just me οr if
perhaps eveгyone elѕe eхperiencing pгоblems
with your ѕite. It appears аs if somе of the text
within yоur content are running οff the screen.
Can sоmebody еlse pleasе provide feeԁback аnԁ let me know if this is hаppening to them tοо?

This might be a іssuе with mу bгowѕer becausе I've had this happen previously. Thanks

My blog post What Is The Best Electronic Cigarettes

Anonymous said...

The other day, while I was at work, my sister stole my
iphone and tested to see if it can survive a twenty five foot
drop, just so she can be a youtube sensation. My iPad is now broken and
she has 83 views. I know this is completely off topic but I had to share it with someone!

Also visit my blog: cheap vera wang shoes

Anonymous said...

Hi there! I could have sworn I've been to this site before but after browsing through some of the post I realized it's new to me.

Anyhow, I'm definitely delighted I found it and I'll be bookmarking and checking back often!

my web blog ::

Anonymous said...

Spot on with this write-up, I actually feel this
website needs a lot more attention. I'll probably be returning to read through more, thanks for the information!

Look into my web blog - healthy diet plans

Geek said...

I have seen this before - for a very elegant solution please see

Anonymous said...

Great delivery. Great arguments. Keep up the good work.

Feel free to surf to my web site

Anonymous said...

However, one must resist the temptation to write long emails as it will only
work against you. If you look on Google for "auto responders" or "email selling systems," you'll notice many completely different options.
" This macro is executed each time you open your database.

Here is my page: fichiers prospection

Anonymous said...

We stumbled over here from a different website and thought I might as well check things out.
I like what I see so now i'm following you. Look forward to looking at your web page

Feel free to surf to my page - click here ()

Anonymous said...

My partner and I stumbled over here by a different web address and thought I
may as well check things out. I like what I see so
now i am following you. Look forward to checking out your web page repeatedly.

Also visit my web page - black mold removal

Anonymous said...

Industry executives say that as these mobile games industry's potential, Akhavan predicts.

These are plants vs. zombies 2 cheats very well. Mobile
phones are abundant in Play Market. The best and should have downloads for different applications and social games
is the sword, and many more, they often drop mind runes, you'll be able to
download the game design studios.

My webpage; Plants vs. zombies 2 cheats no download

David said...

Excellent work! I'm learning scala right now and could NOT figure out how to do this problem with recursive functions. You managed to do it in Python in only a few lines. It'll translate well...thx for posting!