[ create a new paste ] login | about

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

programmingpraxis - Scheme, pasted on May 20:
; coin change, part 2

(define (make-matrix rows columns . value)
  (do ((m (make-vector rows)) (i 0 (+ i 1)))
      ((= i rows) m)
    (if (null? value)
        (vector-set! m i (make-vector columns))
        (vector-set! m i (make-vector columns (car value))))))

(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))

(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))

(define (count coins n)
  (let* ((k (vector-length coins))
         (c (make-matrix k (+ n 1) 0)))
    (do ((j 0 (+ j 1))) ((< n j))
      (matrix-set! c 0 j j))
    (do ((i 1 (+ i 1))) ((= i k))
      (do ((j 1 (+ j 1))) ((< n j))
        (matrix-set! c i j
          (if (< j (vector-ref coins i))
              (matrix-ref c (- i 1) j)
              (min (matrix-ref c (- i 1) j)
                   (+ 1 (matrix-ref c i
                          (- j (vector-ref coins i)))))))))
    (matrix-ref c (- k 1) n)))

(define (coins cs n)
  (let* ((k (vector-length cs))
         (c (make-matrix k (+ n 1) 0)))
    (do ((j 0 (+ j 1))) ((< n j))
      (matrix-set! c 0 j j))
    (do ((i 1 (+ i 1))) ((= i k))
      (do ((j 1 (+ j 1))) ((< n j))
        (matrix-set! c i j
          (if (< j (vector-ref cs i))
              (matrix-ref c (- i 1) j)
              (min (matrix-ref c (- i 1) j)
                   (+ 1 (matrix-ref c i
                          (- j (vector-ref cs i)))))))))
    (let loop ((i (- k 1)) (j n) (zs (list)))
      (cond ((and (zero? i) (zero? j)) zs)
            ((zero? i) (loop i (- j 1) (cons 1 zs)))
            ((= (matrix-ref c i j) (matrix-ref c (- i 1) j))
              (loop (- i 1) j zs))
            (else (loop i (- j (vector-ref cs i))
                        (cons (vector-ref cs i) zs)))))))

(display (count '#(1 5 10 25) 40)) (newline)
(display (coins '#(1 5 10 25) 40)) (newline)


Output:
1
2
3
(5 10 25)


Create a new paste based on this one


Comments: