(Lisp) Counting Change code

Question

I've recently started learning lisp and i thought an interesting problem would be the Count Change algorithm which has been attempted many times however i've found it very difficult to even sort out how to approach this and thought i would try using loops but it just isn't working. I'll put my two useless attempts below but if anyone has any suggestions of even how i should be thinking about this problem in terms of lisp it would be really appreciated. I would much prefer to use a recursive solution aswell.

I've been looking through the questions on here about counting change but they all tend to be object orientated while i need something more functional. It's not home work, just private study!

(defun dollar (amount)   
(let ((l 0) (j 0) (array (make-array '(5 10 20 50 100 200 500 1000 2000 5000 100000))) (results (make-array 50 :initial-element nil))
        (do (l 10 (+ l 1))
       (do ((= j (aref array l)) amount (+ j 1))
         (+ (aref array j) (- (aref results j) (aref array l))))))
                   ))

(defun coin-change (amount coins)
(cond ((< amount 0) 0)
      ((= amount 5) 1)
      ((null coins) 0)
      (t (+ (make-change-with-coins (- amount (car coins)) coins)
            (make-change-with-coins amount (cdr coins)))))

)

sample input would be (coin-change 20 '(5 10 20 50 100 200 500 1000 2000 5000 100000)) which would return 4

Answer 1

It's not clear to me what the first function is supposed to do.

The second one almost ok, this is a fixed version:

(defun coin-change (amount coins)
  (cond
    ((< amount 0) 0)
    ((= amount 0) 1)
    ((= (length coins) 0) 0)
    (t (+ (coin-change (- amount (first coins)) coins)
          (coin-change amount (rest coins))))))

The idea is:

• A negative amount cannot be matched (0 ways)
• Zero can be matched in exactly one way (not giving any coin)
• If amount is >0 and we've no coin types remaining then there are no ways
• Otherwise we can either A) give one piece of the first coin type and count how many ways we can match the remaining part, B) computing the ways without using the first coin type. The answer is A+B

Note that this is going to give huge computing times for large amounts because it doesn't take advantage of the important fact that the number of ways to match a certain amount starting with a certain coin type doesn't depend on how we got to this amount (i.e. the past history). By adding caching you can get a dynamic-programming solution that is much faster because does each computation only once.

Answer 2

Standard formatting helps getting the code structure right. Reading some kind of documentation about a new language helps even more.

This is what you have written:

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array (make-array '(5 10 20 50 100 200 500 1000 2000 5000 100000)))
        (results (make-array 50 :initial-element nil))
        (do (l 10 (+ l 1))
            (do ((= j (aref array l)) amount (+ j 1))
                (+ (aref array j) (- (aref results j) (aref array l))))))))

Dollar doesn't get the semantics right. Make-array takes the dimensions as first argument, and you most likely wanted the do form as a body of the let. I'd use a vector literal here.

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array #(5 10 20 50 100 200 500 1000 2000 5000 100000))
        (results (make-array 50 :initial-element nil)))
    (do (l 10 (+ l 1))
        (do ((= j (aref array l)) amount (+ j 1))
            (+ (aref array j) (- (aref results j) (aref array l)))))))

Do takes first a list of bindings, then a form containing an end condition and return forms and finally forms that form a body.

(defun dollar (amount)
  (let ((l 0)
        (j 0)
        (array #(5 10 20 50 100 200 500 1000 2000 5000 100000))
        (results (make-array 50 :initial-element nil)))
    (do ((l 10 (+ l 1)))
        (#| end condition here |#
         #| some more forms
         that return something |#)
      (do ((= j (aref array l)) ; uh, so this binds the variable "=" to j
                                ; and updates it to (aref array l) on iteration
           amount    ; an empty binding, initially nil
           (+ j 1))  ; binds the variable "+" to j and updates it to 1
          (+           ; tries to evaluate the variable "+" as a form...
           (aref array j)   ; no effect
           (- (aref results j) (aref array l)))))))  ; would return this

I tried to correct the shape of the outer do and annotated the inner do. It makes no sense at all, as you can see.

(defun coin-change (amount coins)
  (cond ((< amount 0) 0)
        ((= amount 5) 1)
        ((null coins) 0)
        (t (+ (make-change-with-coins (- amount (car coins)) coins)
              (make-change-with-coins amount (cdr coins))))))

This looks at least semantically correct, but I cannot tell how it is supposed to work (and I don't know what make-change-with-coins does).

I think it would be prudent to perhaps read a good introductory book first (I like Practical Common Lisp) and peruse the Common Lisp Hyperspec (CLHS).