- Count-change generates a tree-recursive process with redundancies similar to those in our first implementation of fib. (It will take quite a while for that 292 to be computed.) On the other hand, it is not obvious how to design a better algorithm for computing the result, and we leave this problem as a challenge.
What's hubski's take on this? I'll write my implementation and post it later.
The obvious answer is to memoize count-change. A similar approach is to use dynamic programming. In python: def count_change(change): return count(change, len(coin_value)) def count(change, num_coins): result=[[0 for j in range(num_coins)] for i in range(change + 1)] for i in range(change + 1): for j in range(num_coins): if i == 0: # exact change IS possible with given coin_value result[i][j] = 1 elif j == 0: # no coins left, still change to give result[i][j] = 0 elif coin_value[j] > i: # current coin is too large result[i][j] = result[i][j-1] else: # tally how many ways we can get here from previous results result[i][j] = result[i-coin_value[j]][j] + result[i][j-1] return result[change][num_coins-1] >>> count_change(100) 292 coin_value = [0, 1, 5, 10, 25, 50] >>> from count_change import count_change
Nice. Python is such an elegant language. I can't follow your logic immediately (I'll come back to it later when I have time), but looks like it's getting the right result. Is it fast?
About the speed: I added a counter to check how many times it went through the inner loop: count_change(100) = 292: with 606 steps count_change(200) = 2435: with 1206 steps count_change(300) = 9590: with 1806 steps ... count_change(1000) = 801451: with 6006 steps You can see it's going up linearly That's the dynamic programming approach. A similar technique is memoization which lends itself very nicely to the way the original problem is given in scheme. I'll use racket: Adding a count to the program given in SICP (define steps 0) (define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (set! steps (add1 steps)) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50))) (count-change 100): 292 in 15499 steps (count-change 200): 2435 in 229589 steps (count-change 300): 9590 in 1292591 steps Yeah - I'm not even going to try (count-change 1000) This is the problem with tree recursion :( Converting to a memoized version (I'm cheating by using a library that gives define/memo but it's evasy enough to write a memoized version of a function. (define (count-change amount) (cc/memo amount 5)) (set! steps (add1 steps)) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc/memo amount (- kinds-of-coins 1)) (cc/memo (- amount (first-denomination kinds-of-coins)) kinds-of-coins))))) (count-change 100): 292 in 250 steps (count-change 200): 2435 in 496 steps (count-change 300): 9590 in 742 steps (count-change 1000): 801451 in 2464 steps That's even less steps than using dynamic programming although it probably uses a little extra memory to store teh memoized values. #lang racket (require memoize) (define/memo (cc/memo amount kinds-of-coins)
It's an O(n) algorithm - although there is an inner loop - since the number of coin values is fixed it's still a linear algorithm So it's a very fast algorithm. The basic approach with dynamic programming is: Start from the bottom and save the base case results. Go to the "nest level" and calculate those results based on the previously stored results. Keep going until you get your answer. The i - loop represents the amount of change to be given The j - loop represents how many distinct coin values there are. Note that isn't the number of coins in change given its how many coin values you have. The insight is that to calculate how many ways to give change for a given amount using coins of specific values: a) Use 1 of your coins and deduct that from the amount. Result for a) is 1 + ways to count (amount - coin used). e.g. for 57¢ - you can use 1¢ and calculate 56¢. Those results are stored in the results[i] - since python doesn't have native arrays result is a list of lists b) Result for b) is how many ways can you give change by ignoring all coins of one specific value. e.g. for 57¢ - how many ways can you give change when you NEVER use any 1¢ coins? Those results are stored in the result[amount] list indexed by how many coin values are used For a given amount and given number of coin values total = a) + b) To find how many ways to count 10¢ using 1¢, 5¢, 10¢, 25¢, 50¢ Build up the result 'array' like this How many ways to give 0¢ change result[0] = [1, 1, 1, 1, 1, 1] - there is 1 way of giving 0¢ change with a 0¢ coin there is 1 way of giving 0¢ change with 0¢ and 1¢ coins. there is 1 way of giving 0¢ change with 0¢, 1¢, 5¢ coins... How many ways to give 1¢ change result[1] = [0, 1, 1, 1, 1, 1] - there is no way of giving 1¢ change with a 0¢ coin there is 1 way of giving 1¢ change with with 0¢ and 1¢ coins there is 1 way of giving 1¢ change with with 0¢, 1¢, 5¢ coins... these don't change until we hit 5¢ result[5] = [0, 1, 2, 2, 2, 2] - there is no way of giving 5¢ change with a 0¢ coin there is 1 way of giving 5¢ change with with 0¢ and 1¢ coins there are 2 ways of giving 5¢ change with with 0¢, 1¢, 5¢ coins... these don't change until we get to 10¢ result[10] = [0, 1, 3, 4, 4, 4] - there is no way of giving 10¢ change with a 0¢ coin there is 1 way of giving 10¢ change with with 0¢ and 1¢ coins result there are 3 ways of giving 10¢ change with with 0¢, 1¢, 5¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢ coins there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢, 50¢ coins. Since we want to know how many ways using all coins - the answer is at the last value in the last row which is 4.
I banged out a brute-force iterative solution pretty quickly in C. It's not general, but could be made so pretty easily. #define NUM_COINS 5 #define GOAL_IN_CENTS 100 unsigned char ucCoinVal[] = { 1, 5, 10, 25, 50 }; unsigned char isGoodSet( unsigned char aucCoins[] ); int main( void ) { int i; unsigned char max[NUM_COINS]; unsigned char aucCoins[NUM_COINS]; int iTotal = 0; for ( i = 0; i < NUM_COINS; i++ ) { max[i] = GOAL_IN_CENTS / ucCoinVal[i]; printf( "\nCoin %3d cents has max %3d for goal", ucCoinVal[i], max[i] ); } printf( "\n" ); for ( aucCoins[0] = 0; aucCoins[0] <= max[0]; aucCoins[0]++ ) { for ( aucCoins[1] = 0; aucCoins[1] <= max[1]; aucCoins[1]++ ) { for ( aucCoins[2] = 0; aucCoins[2] <= max[2]; aucCoins[2]++ ) { for ( aucCoins[3] = 0; aucCoins[3] <= max[3]; aucCoins[3]++ ) { for ( aucCoins[4] = 0; aucCoins[4] <= max[4]; aucCoins[4]++ ) { if ( isGoodSet( aucCoins ) ) { iTotal++; printf( "\nGood set : %3d %3d %3d %3d %3d", aucCoins[0], aucCoins[1], aucCoins[2], aucCoins[3], aucCoins[4] ); } } } } } } printf( "\nFound %d solutions.\n", iTotal ); } // Function to determine if we have a good set of coins (adds up to the goal). unsigned char isGoodSet( unsigned char aucCoins[] ) { int i; int iSum = 0; for ( i = 0; i < NUM_COINS; i++ ) { iSum += ( aucCoins[i] * ucCoinVal[i] ); } return ( iSum == GOAL_IN_CENTS ) ? 1 : 0; } #include <stdio.h>
Nonsense! The rule is always, "Get it working first, then optimise - but only if necessary!" But there are several simple optimisations possible, I freely admit :-)
Note - in the centre of the loops, markup has swallowed my increment operator - should be "iTotal ++;" Same story for all the for-loop incrementors. There may be other manglings I haven't noticed. [edit] I've fixed up the missing "++" operators - let me know if you notice any other manglings.
hubski's markdown implementation is really bad for posting code because it still parses what's inside the code rather than outputting it verbatim. You STILL have to escape special symbols ilke + inside code too. It's very frustrating.
mk forwardslash rob05c -- regarding our conversation regarding markdown
Agreed - not great for code, or for poetry / song-lyrics. I had to bung in two spaces at the front of every line to convince it to use a monospace font. There ought to be a way to say "don't format this text at all please".
Here's the output (or run it yourself, if you have gcc) : Coin 5 cents has max 20 for goal Coin 10 cents has max 10 for goal Coin 25 cents has max 4 for goal Coin 50 cents has max 2 for goal Good set : 0 0 0 0 2 Good set : 0 0 0 2 1 Good set : 0 0 0 4 0 Good set : 0 0 5 0 1 Good set : 0 0 5 2 0 Good set : 0 0 10 0 0 Good set : 0 1 2 1 1 Good set : 0 1 2 3 0 Good set : 0 1 7 1 0 Good set : 0 2 4 0 1 Good set : 0 2 4 2 0 Good set : 0 2 9 0 0 Good set : 0 3 1 1 1 Good set : 0 3 1 3 0 Good set : 0 3 6 1 0 Good set : 0 4 3 0 1 Good set : 0 4 3 2 0 Good set : 0 4 8 0 0 Good set : 0 5 0 1 1 Good set : 0 5 0 3 0 Good set : 0 5 5 1 0 Good set : 0 6 2 0 1 Good set : 0 6 2 2 0 Good set : 0 6 7 0 0 Good set : 0 7 4 1 0 Good set : 0 8 1 0 1 Good set : 0 8 1 2 0 Good set : 0 8 6 0 0 Good set : 0 9 3 1 0 Good set : 0 10 0 0 1 Good set : 0 10 0 2 0 Good set : 0 10 5 0 0 Good set : 0 11 2 1 0 Good set : 0 12 4 0 0 Good set : 0 13 1 1 0 Good set : 0 14 3 0 0 Good set : 0 15 0 1 0 Good set : 0 16 2 0 0 Good set : 0 18 1 0 0 Good set : 0 20 0 0 0 Good set : 5 0 2 1 1 Good set : 5 0 2 3 0 Good set : 5 0 7 1 0 Good set : 5 1 4 0 1 Good set : 5 1 4 2 0 Good set : 5 1 9 0 0 Good set : 5 2 1 1 1 Good set : 5 2 1 3 0 Good set : 5 2 6 1 0 Good set : 5 3 3 0 1 Good set : 5 3 3 2 0 Good set : 5 3 8 0 0 Good set : 5 4 0 1 1 Good set : 5 4 0 3 0 Good set : 5 4 5 1 0 Good set : 5 5 2 0 1 Good set : 5 5 2 2 0 Good set : 5 5 7 0 0 Good set : 5 6 4 1 0 Good set : 5 7 1 0 1 Good set : 5 7 1 2 0 Good set : 5 7 6 0 0 Good set : 5 8 3 1 0 Good set : 5 9 0 0 1 Good set : 5 9 0 2 0 Good set : 5 9 5 0 0 Good set : 5 10 2 1 0 Good set : 5 11 4 0 0 Good set : 5 12 1 1 0 Good set : 5 13 3 0 0 Good set : 5 14 0 1 0 Good set : 5 15 2 0 0 Good set : 5 17 1 0 0 Good set : 5 19 0 0 0 Good set : 10 0 4 0 1 Good set : 10 0 4 2 0 Good set : 10 0 9 0 0 Good set : 10 1 1 1 1 Good set : 10 1 1 3 0 Good set : 10 1 6 1 0 Good set : 10 2 3 0 1 Good set : 10 2 3 2 0 Good set : 10 2 8 0 0 Good set : 10 3 0 1 1 Good set : 10 3 0 3 0 Good set : 10 3 5 1 0 Good set : 10 4 2 0 1 Good set : 10 4 2 2 0 Good set : 10 4 7 0 0 Good set : 10 5 4 1 0 Good set : 10 6 1 0 1 Good set : 10 6 1 2 0 Good set : 10 6 6 0 0 Good set : 10 7 3 1 0 Good set : 10 8 0 0 1 Good set : 10 8 0 2 0 Good set : 10 8 5 0 0 Good set : 10 9 2 1 0 Good set : 10 10 4 0 0 Good set : 10 11 1 1 0 Good set : 10 12 3 0 0 Good set : 10 13 0 1 0 Good set : 10 14 2 0 0 Good set : 10 16 1 0 0 Good set : 10 18 0 0 0 Good set : 15 0 1 1 1 Good set : 15 0 1 3 0 Good set : 15 0 6 1 0 Good set : 15 1 3 0 1 Good set : 15 1 3 2 0 Good set : 15 1 8 0 0 Good set : 15 2 0 1 1 Good set : 15 2 0 3 0Coin 1 cents has max 100 for goal