0
\$\begingroup\$

Here is my iterative implementation of the Counting change example in SICP. Please note that I'm a beginner, which means I only know the basic syntax for the time being.

Requirement:

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?

Code:

(define (count-change-iterative amount)
  ;; penny is not in the signiture, bacause it equals (- amount
  ;;                                                     (* half-dollar 50)
  ;;                                                     (* quarter 25)
  ;;                                                     (* dime 10)
  ;;                                                     (* nickeli 5))
  (define (count-iter half-dollar quarter dime nickeli)
    (cond ((> (* half-dollar 50) amount)
           0)
          ((> (+ (* half-dollar 50)
                 (* quarter 25)) amount)
           (count-iter (+ half-dollar 1) 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)) amount)
           (count-iter half-dollar (+ quarter 1) 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)
                 (* nickeli 5)) amount)
           (count-iter half-dollar quarter (+ dime 1) 0))
          (else (+ 1
                   (count-iter half-dollar quarter dime (+ nickeli 1))))))
  (count-iter 0 0 0 0))

If you run (count-change-iterative 100), it would tell you 292.

I think this is the best scheme code I've written by now. How can I improve it?

\$\endgroup\$
4
\$\begingroup\$

In SICP the authors note:

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.

And while your solution is more efficient than the solution they provide it still has a lot of redundancies. If you're will to sacrifice some readability you could use a bottom-up algorithm to eliminate these redundancies.

For example:

(define (add-if predicate x addition)
  (if predicate (+ x addition) x))

(define (inc-if predicate x)
  (add-if predicate x 1))

(define (zero-if predicate x)
  (if predicate 0 x))

(define (count-change amount)
  (define (cc-iter value ways-to-change new-ways nickel-ways dime-ways quarter-ways nickels dimes quarters)
    (define (current-coins num-nickels num-dimes num-quarters)
      (and (= nickels num-nickels)
           (= dimes num-dimes)
           (= quarters num-quarters)))
    (if (> value amount)
        ways-to-change
        (cc-iter (+ value 5)
                 (+ ways-to-change new-ways)
                 (+ new-ways (if (= nickels quarters) dime-ways nickel-ways))
                 (add-if (current-coins 0 1 1) nickel-ways quarter-ways)
                 (add-if (current-coins 0 1 0) dime-ways quarter-ways)
                 (inc-if (current-coins 0 1 0) quarter-ways)
                 (zero-if (or (= nickels 1) (= dimes 2)) 1)
                 (zero-if (= dimes 2) (inc-if (= nickels 1) dimes))
                 (zero-if (current-coins 0 2 1) (inc-if (= dimes 2) quarters)))))
  (cc-iter 0 0 1 1 0 1 0 0 0))
\$\endgroup\$
2
\$\begingroup\$

If you add a running sum to the formal parameters of count-iter, you'll have a truly iterative piece of code. As-is, every time through count-iter is called, you leave a "1+ ??" waiting on the stack, which will lead to a recursion depth exceeded error on larger inputs.

(define (count-change-true-iterative amount)
  ;; penny is not in the signiture, bacause it equals (- amount
  ;;                                                     (* half-dollar 50)
  ;;                                                     (* quarter 25)
  ;;                                                     (* dime 10)
  ;;                                                     (* nickeli 5))
  (define (count-iter sum half-dollar quarter dime nickeli)
    (cond ((> (* half-dollar 50) amount)
           sum)
          ((> (+ (* half-dollar 50)
                 (* quarter 25)) amount)
           (count-iter sum(+ half-dollar 1) 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)) amount)
           (count-iter sum half-dollar (+ quarter 1) 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 25)
                 (* dime 10)
                 (* nickeli 5)) amount)
           (count-iter sum half-dollar quarter (+ dime 1) 0))
          (else (count-iter (+ 1 sum) half-dollar quarter dime (+ nickeli 1)))))
  (count-iter 0 0 0 0 0))

And can thus handle a calculation like (count-change-true-iterative 3232) though it may take several minutes to do so. ;Value: 76915410

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.