change-coins

;;;; Copyright (c) 2010 Olexiy Zamkoviy <[email protected]>
;;;;
;;;; Permission is hereby granted, free of charge, to any person obtaining
;;;; a copy of this software and associated documentation files (the
;;;; "Software"), to deal in the Software without restriction, including
;;;; without limitation the rights to use, copy, modify, merge, publish,
;;;; distribute, sublicense, and/or sell copies of the Software, and to
;;;; permit persons to whom the Software is furnished to do so, subject to
;;;; the following conditions:
;;;;
;;;; The above copyright notice and this permission notice shall be included
;;;; in all copies or substantial portions of the Software.
;;;;
;;;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
;;;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
;;;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
;;;; IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
;;;; CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
;;;; TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
;;;; SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

;;; Function itself
(defun change-coins(sum posible-values)
  "Function changes the `sum` with coins list `posible-values`.
  For example to change 5 cents with 1 2 coins we need to call
  (change-coins 5 (list 1 2)) the result is 3

  The ways to change 5 with 1,2 coins are

  2 2 1
  2 1 1 1
  1 1 1 1 1

  If it is not posible to change sum with given coins function returns zero

  (change-coins 5 (list 3)) results to 0
  "
  (let ((ret 0)(posible-values (sort posible-values #'>)))
    (dotimes (i (length posible-values))
      (let ((item (nth i posible-values)))
         (incf ret (if (= item sum)
                        1
                        (if (< item sum)
                            (change-coins (- sum item) (subseq posible-values i))
                            0))))) 
    ret))

;;; Testing
(let ((test-data '(
                  (1 (1) 1)
                  ; 1
                  ;
                  (2 (1) 1)
                  ; 1 1
                  ;
                  (3 (1) 1)
                  ; 1 1 1
                  ;
                  (3 (2 1) 2)
                  ; 2 1 
                  ; 1 1 1
                  ;
                  (3 (2) 0)
                  ; 2 ...
                  (4 (2) 1)
                  ; 2 2 
                  ;
                  (4 (2 1) 3)
                  ; 2 2
                  ; 2 1 1
                  ; 1 1 1 1
                  ;
                  (5 (2 1) 3)
                  ; 2 2 1
                  ; 2 1 1 1
                  ; 1 1 1 1 1
                  ;
                  (5 (1 2) 3))))
                  ; 2 2 1
                  ; 2 1 1 1
                  ; 1 1 1 1 1
                  ;
  (dolist (i test-data)
          (assert (= (third i) (change-coins (first i) (second i))))))