[ create a new paste ] login | about

Link: http://codepad.org/RekApsRy    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on May 17:
; coin change, part 1

(define (count xs n)
  (let ((cs (make-vector (+ n 1) 0)))
    (vector-set! cs 0 1)
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((x (car xs) (+ x 1))) ((< n x))
        (vector-set! cs x (+ (vector-ref cs x)
          (vector-ref cs (- x (car xs)))))))))

(define (coins xs n)
  (let ((cs (make-vector (+ n 1) (list))))
    (vector-set! cs 0 (list (list)))
    (do ((xs xs (cdr xs)))
        ((null? xs) (vector-ref cs n))
      (do ((i (car xs) (+ i 1))) ((< n i))
        (vector-set! cs i
          (append (vector-ref cs i)
                  (map (lambda (zs) (cons (car xs) zs))
                       (vector-ref cs (- i (car xs))))))))))

(display (count '(1 5 10 25) 40)) (newline)
(for-each (lambda (x) (display x) (newline))
          (coins '(1 5 10 25) 40))


Output:
31
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(5 5 5 5 5 5 1 1 1 1 1 1 1 1 1 1)
(5 5 5 5 5 5 5 1 1 1 1 1)
(5 5 5 5 5 5 5 5)
(10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 5 5 5 5 1 1 1 1 1 1 1 1 1 1)
(10 5 5 5 5 5 1 1 1 1 1)
(10 5 5 5 5 5 5)
(10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 10 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(10 10 5 5 1 1 1 1 1 1 1 1 1 1)
(10 10 5 5 5 1 1 1 1 1)
(10 10 5 5 5 5)
(10 10 10 1 1 1 1 1 1 1 1 1 1)
(10 10 10 5 1 1 1 1 1)
(10 10 10 5 5)
(10 10 10 10)
(25 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(25 5 1 1 1 1 1 1 1 1 1 1)
(25 5 5 1 1 1 1 1)
(25 5 5 5)
(25 10 1 1 1 1 1)
(25 10 5)


Create a new paste based on this one


Comments: