sicp-ex-2.19

  
 ;; Counting change. 
  
 ;; Helper methods, could define them in cc too: 
 (define (first-denomination denominations) (car denominations)) 
 (define (except-first-denom denominations) (cdr denominations)) 
 (define (no-more? denominations) (null? denominations)) 
  
 (define (cc amount denominations) 
   (cond  
    ;; If there's no change left, we have a solution 
    ((= amount 0) 1) 
     
    ;; If we're gone -ve amount, or there are no more kinds of coins 
    ;; to play with, we don't have a solution. 
    ((or (< amount 0) (no-more? denominations)) 0) 
     
    (else 
     ;; number of ways to make change without the current coin type 
     ;; plus the number of ways after subtracting the amount of the 
     ;; current coin. 
     (+ (cc amount (except-first-denom denominations)) 
        (cc (- amount  
               (first-denomination denominations))  
            denominations))))) 
  
  
 (cc 100 (list 50 25 10 5 1)) 
 ;; 292 
  
 (cc 100 (list 100 50 20 10 5 2 1 0.5)) 
 ;; 104561 ... wow. 
  

this also works

  
 (define no-more? null?) 
 (define except-first-denomination cdr) 
 (define first-denomination car) 
  

For the last part of the exercise. The order of the coins does not affect the result. Becuase the procedure computes all possible combinations. But it does affect the speed of the computation. If you start with the lower valued coins, it'll 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 takes longer 
  

Using other methods to achieve the same function

  
 ;; functional programming 
 (define (count-change-1 amount denomination-list) 
     (length (filter 
                 (lambda (data) (= amount (apply + (map * data denomination-list)))) 
                 (accumulate 
                     (lambda (a-list b-list) 
                         (flatmap 
                             (lambda (a) (map (lambda (b) (cons a b)) b-list)) 
                             a-list)) 
                     (list '()) 
                     (map 
                         (lambda (c) (enumerate-interval 0 c)) 
                         (map (lambda (d) (floor (/ amount d))) denomination-list)))))) 
  
  
 ;; Using nested mappings 
  
 (define (nested-map mapping op keys-list) 
     (define (rec keys-list args) 
         (if (null? keys-list) 
             (apply op (reverse args)) 
             (mapping 
                 (lambda (key) 
                     (rec (cdr keys-list) (cons key args))) 
                 (car keys-list)))) 
     (rec keys-list '())) 
  
  
 (define (count-change-2 amount denomination-list)     
     (let ((count 0)) 
         (define (count-inc! . b) 
             (if (= amount (apply + (map * b denomination-list))) 
                     (set! count (+ count 1))))         
         (nested-map 
             for-each 
             count-inc! 
             (map 
                 (lambda (c) (enumerate-interval 0 c)) 
                 (map (lambda (d) (floor (/ amount d))) denomination-list))) 
         count))