Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Money exchange solver in Racket - fast version

By: burjui on Apr 6th, 2012  |  syntax: Scheme  |  size: 1.09 KB  |  hits: 114  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #lang racket
  2.  
  3. (define coins (vector-immutable 50 25 10 5 1))
  4. (define coins-amount (vector-length coins))
  5. (define cache-width 1000001)
  6. (define cache (make-vector (* cache-width (add1 coins-amount)) #f))
  7.  
  8. (define (count-exchanges sum coin-index)
  9.   (let* ([index (+ sum (* coin-index cache-width))]
  10.          [entry (vector-ref cache index)]
  11.          [result
  12.           (cond [entry entry]
  13.                 [(zero? sum) 1]
  14.                 [(negative? sum) 0]
  15.                 [(>= coin-index coins-amount) 0]
  16.                 [else
  17.                  (begin
  18.                    (let find-smaller-coin ()
  19.                      (when (and (< coin-index coins-amount)
  20.                                 (< sum (vector-ref coins coin-index)))
  21.                        (set! coin-index (add1 coin-index))
  22.                        (find-smaller-coin)))
  23.                    (+ (count-exchanges (- sum (vector-ref coins coin-index)) coin-index)
  24.                       (count-exchanges sum (add1 coin-index))))])])
  25.     (unless entry
  26.       (vector-set! cache index result))
  27.     result))
  28.  
  29. (time (count-exchanges 1000000 0))
create a new version of this paste RAW Paste Data