Skip to content

Instantly share code, notes, and snippets.

@wdkrnls
Last active December 16, 2015 20:39
Show Gist options
  • Save wdkrnls/5493530 to your computer and use it in GitHub Desktop.
Save wdkrnls/5493530 to your computer and use it in GitHub Desktop.
#lang racket
(provide
(contract-out
[make-coinage (-> (listof positive-integer?) list?)]))
(define (positive-integer? x)
(and (positive? x)
(integer? x)))
(module+ test
(require rackunit))
(define (make-coinage coins)
(define (make-payment value)
(define (closest-coin value)
(caar (sort (map list coins (for/list ([c coins]) (abs (- value c)))) #:key second <)))
(if (not (zero? (remainder value (apply gcd coins))))
(error "Payment not possible!")
(let loop ([value value] [pays empty] [gets empty])
(cond [(zero? value) (list pays gets)]
[(positive? value)
(define coin-selected (closest-coin value))
(loop (- value coin-selected) (cons coin-selected pays) gets)]
[(negative? value)
(define coin-selected (closest-coin (- value)))
(loop (+ value coin-selected) pays (cons coin-selected gets))]))))
make-payment)
(module+ test
(define us (make-coinage (list 1 5 10 25 50 100)))
(check-equal? (us 40) (list (list 50) (list 10)))
(check-equal? (us 23) (list (list 25) (list 1 1)))
(check-equal? (us 26) (list (list 1 25) empty))
(check-equal? (us 27) (list (list 1 1 25) empty))
(check-equal? (us 101) (list (list 1 100) empty))
(check-equal? (length (flatten (us 119))) (length (flatten '((10 10 100) (1)))))
(check-equal? (us 123) '((25 100) (1 1)))
(check-equal? (length (flatten (us 3))) 3) ; ((1 1 1) ()) or ((5) (1 1))
(check-equal? (us 33) (list (list 10 25) (list 1 1)))
(define uk (make-coinage '(1 2 5 10 20 50 100 200)))
(check-equal? (uk 119) '((20 100) (1)))
(check-equal? (uk 123) '((1 2 20 100) ()))
(define harry-potter (make-coinage '(1 17 493)))
(check-equal? (harry-potter 100) '((17 17 17 17 17 17) (1 1))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment