__Login__or

__Take a Tour__!

- 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:

`coin_value = [0, 1, 5, 10, 25, 50]`

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

`>>> from count_change import count_change`

>>> count_change(100)

`292`

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

`#lang racket`

(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.

`(require memoize)`

(define (count-change amount)

`(cc/memo amount 5))`

`(define/memo (cc/memo amount kinds-of-coins)`

(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.

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.

`#include <stdio.h>`

#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;

`}`

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 1 cents has max 100 for goal

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 0

Good set : 15 2 5 1 0

Good set : 15 3 2 0 1

Good set : 15 3 2 2 0

Good set : 15 3 7 0 0

Good set : 15 4 4 1 0

Good set : 15 5 1 0 1

Good set : 15 5 1 2 0

Good set : 15 5 6 0 0

Good set : 15 6 3 1 0

Good set : 15 7 0 0 1

Good set : 15 7 0 2 0

Good set : 15 7 5 0 0

Good set : 15 8 2 1 0

Good set : 15 9 4 0 0

Good set : 15 10 1 1 0

Good set : 15 11 3 0 0

Good set : 15 12 0 1 0

Good set : 15 13 2 0 0

Good set : 15 15 1 0 0

Good set : 15 17 0 0 0

Good set : 20 0 3 0 1

Good set : 20 0 3 2 0

Good set : 20 0 8 0 0

Good set : 20 1 0 1 1

Good set : 20 1 0 3 0

Good set : 20 1 5 1 0

Good set : 20 2 2 0 1

Good set : 20 2 2 2 0

Good set : 20 2 7 0 0

Good set : 20 3 4 1 0

Good set : 20 4 1 0 1

Good set : 20 4 1 2 0

Good set : 20 4 6 0 0

Good set : 20 5 3 1 0

Good set : 20 6 0 0 1

Good set : 20 6 0 2 0

Good set : 20 6 5 0 0

Good set : 20 7 2 1 0

Good set : 20 8 4 0 0

Good set : 20 9 1 1 0

Good set : 20 10 3 0 0

Good set : 20 11 0 1 0

Good set : 20 12 2 0 0

Good set : 20 14 1 0 0

Good set : 20 16 0 0 0

Good set : 25 0 0 1 1

Good set : 25 0 0 3 0

Good set : 25 0 5 1 0

Good set : 25 1 2 0 1

Good set : 25 1 2 2 0

Good set : 25 1 7 0 0

Good set : 25 2 4 1 0

Good set : 25 3 1 0 1

Good set : 25 3 1 2 0

Good set : 25 3 6 0 0

Good set : 25 4 3 1 0

Good set : 25 5 0 0 1

Good set : 25 5 0 2 0

Good set : 25 5 5 0 0

Good set : 25 6 2 1 0

Good set : 25 7 4 0 0

Good set : 25 8 1 1 0

Good set : 25 9 3 0 0

Good set : 25 10 0 1 0

Good set : 25 11 2 0 0

Good set : 25 13 1 0 0

Good set : 25 15 0 0 0

Good set : 30 0 2 0 1

Good set : 30 0 2 2 0

Good set : 30 0 7 0 0

Good set : 30 1 4 1 0

Good set : 30 2 1 0 1

Good set : 30 2 1 2 0

Good set : 30 2 6 0 0

Good set : 30 3 3 1 0

Good set : 30 4 0 0 1

Good set : 30 4 0 2 0

Good set : 30 4 5 0 0

Good set : 30 5 2 1 0

Good set : 30 6 4 0 0

Good set : 30 7 1 1 0

Good set : 30 8 3 0 0

Good set : 30 9 0 1 0

Good set : 30 10 2 0 0

Good set : 30 12 1 0 0

Good set : 30 14 0 0 0

Good set : 35 0 4 1 0

Good set : 35 1 1 0 1

Good set : 35 1 1 2 0

Good set : 35 1 6 0 0

Good set : 35 2 3 1 0

Good set : 35 3 0 0 1

Good set : 35 3 0 2 0

Good set : 35 3 5 0 0

Good set : 35 4 2 1 0

Good set : 35 5 4 0 0

Good set : 35 6 1 1 0

Good set : 35 7 3 0 0

Good set : 35 8 0 1 0

Good set : 35 9 2 0 0

Good set : 35 11 1 0 0

Good set : 35 13 0 0 0

Good set : 40 0 1 0 1

Good set : 40 0 1 2 0

Good set : 40 0 6 0 0

Good set : 40 1 3 1 0

Good set : 40 2 0 0 1

Good set : 40 2 0 2 0

Good set : 40 2 5 0 0

Good set : 40 3 2 1 0

Good set : 40 4 4 0 0

Good set : 40 5 1 1 0

Good set : 40 6 3 0 0

Good set : 40 7 0 1 0

Good set : 40 8 2 0 0

Good set : 40 10 1 0 0

Good set : 40 12 0 0 0

Good set : 45 0 3 1 0

Good set : 45 1 0 0 1

Good set : 45 1 0 2 0

Good set : 45 1 5 0 0

Good set : 45 2 2 1 0

Good set : 45 3 4 0 0

Good set : 45 4 1 1 0

Good set : 45 5 3 0 0

Good set : 45 6 0 1 0

Good set : 45 7 2 0 0

Good set : 45 9 1 0 0

Good set : 45 11 0 0 0

Good set : 50 0 0 0 1

Good set : 50 0 0 2 0

Good set : 50 0 5 0 0

Good set : 50 1 2 1 0

Good set : 50 2 4 0 0

Good set : 50 3 1 1 0

Good set : 50 4 3 0 0

Good set : 50 5 0 1 0

Good set : 50 6 2 0 0

Good set : 50 8 1 0 0

Good set : 50 10 0 0 0

Good set : 55 0 2 1 0

Good set : 55 1 4 0 0

Good set : 55 2 1 1 0

Good set : 55 3 3 0 0

Good set : 55 4 0 1 0

Good set : 55 5 2 0 0

Good set : 55 7 1 0 0

Good set : 55 9 0 0 0

Good set : 60 0 4 0 0

Good set : 60 1 1 1 0

Good set : 60 2 3 0 0

Good set : 60 3 0 1 0

Good set : 60 4 2 0 0

Good set : 60 6 1 0 0

Good set : 60 8 0 0 0

Good set : 65 0 1 1 0

Good set : 65 1 3 0 0

Good set : 65 2 0 1 0

Good set : 65 3 2 0 0

Good set : 65 5 1 0 0

Good set : 65 7 0 0 0

Good set : 70 0 3 0 0

Good set : 70 1 0 1 0

Good set : 70 2 2 0 0

Good set : 70 4 1 0 0

Good set : 70 6 0 0 0

Good set : 75 0 0 1 0

Good set : 75 1 2 0 0

Good set : 75 3 1 0 0

Good set : 75 5 0 0 0

Good set : 80 0 2 0 0

Good set : 80 2 1 0 0

Good set : 80 4 0 0 0

Good set : 85 1 1 0 0

Good set : 85 3 0 0 0

Good set : 90 0 1 0 0

Good set : 90 2 0 0 0

Good set : 95 1 0 0 0

Good set : 100 0 0 0 0

Found 292 solutions.

A couple of weeks ago someone on /r/learnpython asked for help on a recursive method to generate the number of ways to count to n when at any point you could step up by 1 or 2. That was a fairly easy problem to solve and this seems to be nothing more than an advanced version of the same question. N is fixed at 100 and we have steps of (1, 5, 10, 25, 50). The major difference is that when stepping by only 1 or 2 the number of solutions is not limited by duplicates (ie for n=5 you can have (2, 1, 1, 1) and (1, 2, 1, 1)) whereas in this problem the analogous solutions would be considered duplicates.

I'll see if I can come up with a solution.

I remember reading SICP. It's a lot of fun.

The recursive algorithm reminds me of something I was just looking at the other day, the Chu-Vandermonde identity.

One obvious way to speed it up is memoization. But I wonder if that would be as effective in this case as for Fibonacci.

Another way would be to just handle the penny case by just outputting 1 straight away if amount >= 0, and handle the penny-and-nickel case by outputting 1+floor(amount/5). I'd imagine that just doing this would speed up the program quite a bit.

But a straight-up, non-recursive calculation in one fell swoop? I'm not sure how to do that.

- But I wonder if that would be as effective in this case as for Fibonacci.

Sure, why not? It's still **tree recursion** after all. You just have to use an extra procedure that takes the change amount and how many coin values you have.

e.g. For the UK coin values are 1, 2, 5, 10, 20, 50, 100 and 200 so there are 8 coin values.

So instead of

` count_change(amount)`

you'd use

`count_change(amount)`

`cc(amount, num_coins)`

and you memoize cc with indexes of amount and num_coins

You're right. I hadn't quite thought it through, but it would work well: eg. for 8 coin values, if you need to calculate the number of ways to make 2.00, you need to make at most 200*8=1600 calls to the recursive function. So you get O(n) efficiency.

But it still seems like you should be able to do better: O(1) would be possible with a closed-form formula.

edit: Oh, I noticed you actually implemented it with memoization. Great!

- O(1) would be possible with a closed-form formula.

That's way beyond my maths ability. Do you think you could find such a formula?

I know there's Binet's formula for Fibonacci, but it's impractical for larger numbers as the floating point errors start to affec tthe results (on most machines anyway.)

Yeah, it's tough, I don't really know how to go about it. But here's at least a demonstration for three denominations, {1, 2, 5}: (n is the total amount to add up to)

`def onetwofive(n):`

numfives = math.floor(n/5.)+1

`return int( numfives * (n % 5 + n + 3)/4 - (numfives % 2) * (n % 2 - 0.5) / 2. )`

Disgusting, I know! But it works: I double checked it against your code, it gives the same result up to n=5000.

An estimate for four denominations {1, 2, 5, 10} is n^3/600; for five denominations {1, 2, 5, 10, 25}, n^4/60000. I got these by summing crudely and dropping low order terms. They seem to be asymptotic: the estimate for five denominations is accurate to within 5% of the true value for n > 2000. That might seem silly but count_change does get quite slow for n >> 10^6 (that's $10,000.00), while the approximation is good to within 0.01%.

edit: You could write a program that returns an estimator function for a given set of denominations. See Faulhaber's formula.

I'm impressed you managed a solution for 3 coins.

> count_change does get quite slow for n >> 10^6 (that's $10,000.00)

From a pure math angle, both memo & dynamic programming versions are linear in time and space. As you said though, those numbers are growing exponentially meaning the space will grow exponentially too.