Wednesday, December 29, 2010

SICP 2.19: Counting Change Revisited

From SICP section 2.2.1 Representing Sequences

Exercise 2.19 asks us to modify the change counting procedure from section 1.2.2 (which we looked at in depth in exercise 1.14). We need to modify the program so that it takes a list of coins to be used instead of having the denominations hard coded as they were originally. The following lists of coins are provided:
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We're also provided with the following modified version of the cc procedure:
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else
(+ (cc amount
(except-first-denomination coin-values))
(cc (- amount
(first-denomination coin-values))
coin-values)))))

All that's left for us to do is define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive list operations. These procedures are very straightforward.
; return true if passed an empty list
(define (no-more? coin-values)
(if (null? coin-values) true false))

; return all coin values except the first
(define (except-first-denomination coin-values)
(cdr coin-values))

; return only the first coin value
(define (first-denomination coin-values)
(car coin-values))

> (cc 100 us-coins)
292
> (cc 100 uk-coins)
104561

Finally, we're asked if the order of the list coin-values affects the answer produced by cc. We can find out quickly enough by experiment.
; reversed list of us coins
(define su-coins (list 1 5 10 25 50))

> (cc 100 us-coins)
292
> (cc 100 su-coins)
292

We can see that the order doesn't matter. This is because the procedure recursively evaluates every sub-list after subtracting the value of the first coin from the target amount. It doesn't matter if that value is the smallest, largest, or even if the values are shuffled.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

5 comments:

Anonymous said...

The UK has £2 coins, and occasional special issues of £5 coins. And the US has $1 coins.

Bill the Lizard said...

Anonymous,

I'm not familiar with UK coins, but it's true that the US has a $1 coin. This just shows that the new implementation where you can create your own list of coin values is much better than the earlier version where the values were embedded in the code.

thelsdj said...

I went with the much shorter aliasing method:
(define no-more? null?)
(define first-denomination car)
(define except-first-denomination cdr)

Anonymous said...

Even if the answer is always correct without regard to the order of the coins. If you put the smaller coins first, it will take much longer.

(define (timed-cc amount coin-values start-time)
(cc amount coin-values)
(- (runtime) start-time))
(timed-cc 200 us-coins (runtime)) ;.6799
(timed-cc 200 (reverse us-coins) (runtime)) ;.1.27

(if (> (timed-cc 100 (reverse us-coins) (runtime))
(timed-cc 100 us-coins (runtime)))
(display "Reverse takes longer")
(display "Reverse does not take longer")) ;As expected, reverse take longer.

kapitan said...

As the last value returned is the result of the last expression, couldn't you simplify your no-more? this way?

; return true if passed an empty list
(define (no-more? coin-values)
(null? coin-values))