I have just started learning some Scheme this weekend. I recently solved a problem that goes something like:
Count the number of ways possible to give out a certain amount of change using 1 5 10 25 and 50 cent pieces. --SICP 1.16
So my code to this question looks like this:
(define (make-change amount) (define coin-total 5) ;;#Function that actually does the calculating (define (calculate amount coins) ;;#Lookup values on the table vector, if none is found find it and add it. (define (lookup) ;;#Location on the table vector (define position (- (+ coins (* coin-total (- amount 1))) 1)) ;;#Get the value in the table vector (define (search-for amount coins) (vector-ref table position)) ;;#Not quite so functional, but we need to add it somehow (define (update val) (begin (vector-set! table position val) val)) (let ((result (search-for amount coins))) (if (= result 0) (let* ((left-branch (calculate amount (- coins 1))) (right-branch (calculate (- amount (coin-value coins)) coins))) (update (+ left-branch right-branch))) result))) (cond ((= amount 0) 1 ) ((or (< amount 0) (= coins 0)) 0) (else (lookup)))) ;;#Table stuff (define table (make-vector (* amount coin-total) 0)) (define (init-table position) (if (< position 0) 0 (begin (vector-set! table position 1) (init-table (- position 1))))) ;;#The entry point, sets up the table and starts the calculation (begin (init-table 4) (calculate amount coin-total))) ;;#Mapping from coin number to value, order doesn't matter (define (coin-value n) (cond ((= n 1) 1) ((= n 2) 5) ((= n 3) 10) ((= n 4) 25) ((= n 5) 50)))
The logic in this code is sound, it "works" but I'm worried that I'm not writing it very idiomatically. What suggestions or alterations would you make for this code?
Note: I stuck this # in the comments here so that the code highlighting would stop treating it like code and messing up the syntax highlighting