*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__':

unittest.main()

## 15 comments:

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}

currentPossibilities.map {|p|

countChange amount - p, remainingCoins

}.inject {|acc, c| acc+c}

end

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])

end

end

end

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

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

sharing!

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

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

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; http://www.hellolorain.com/discussion_forums/202340/is-it-really-worth-it-to-buy-an-electronic-cigarette

My web page-Www.Hellodurham.comӀ ԁ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

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

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 :: http://www.worldofgreentea.com

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

I have seen this before - for a very elegant solution please see Geecko.co.uk

Thanks

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

Feel free to surf to my web site howtosetupawebsiteeasily.info

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

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

again.

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

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

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

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!

Post a Comment