[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/XQuQhu5C    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Feb 17:
; floupia

(define (filter pred? xs)
  (let loop ((xs xs) (ys '()))
    (cond ((null? xs) (reverse ys))
          ((pred? (car xs))
            (loop (cdr xs) (cons (car xs) ys)))
          (else (loop (cdr xs) ys)))))

(define (sum xs) (apply + xs))

(define (negate x) (- x))

(define (binom n m)
  (let loop ((n n) (m m) (b 1))
    (if (zero? m) b
      (loop (- n 1) (- m 1) (* b n (/ m))))))

(define (combinations-without-replacement n xs)
  (if (= n 0) (list (list))
    (if (null? xs) (list)
      (append (map (lambda (xss) (cons (car xs) xss))
                   (combinations-without-replacement (- n 1) (cdr xs)))
              (combinations-without-replacement n (cdr xs))))))

(display (binom 5 3)) (newline)
(display (combinations-without-replacement 3 '(a b c d e))) (newline)

(define (combinations-with-replacement n xs)
  (if (= n 0) (list (list))
    (if (null? xs) (list)
      (append (map (lambda (xss) (cons (car xs) xss))
                   (combinations-with-replacement (- n 1) xs))
              (combinations-with-replacement n (cdr xs))))))

(display (binom (+ 5 3 -1) 3)) (newline)
(display (combinations-with-replacement 3 '(a b c d e))) (newline)

(define (floupia price coins)
  (if (positive? (modulo price (apply gcd coins)))
      (error 'floupia "infeasible")
      (let ((coins (append coins (map negate coins))))
        (let loop ((n 1))
          (let ((xs (filter (lambda (xs) (= (sum xs) price))
                            (combinations-with-replacement n coins))))
            (if (null? xs) (loop (+ n 1)) xs))))))

(display (floupia 13 '(2 5 10))) (newline)
(display (floupia 18 '(1 2 5 10))) (newline)
(display (floupia 17 '(1 3 7 31 153))) (newline)
(display (floupia 11 '(3 6))) (newline)


Output:
1
2
3
4
5
6
7
8
10
((a b c) (a b d) (a b e) (a c d) (a c e) (a d e) (b c d) (b c e) (b d e) (c d e))
35
((a a a) (a a b) (a a c) (a a d) (a a e) (a b b) (a b c) (a b d) (a b e) (a c c) (a c d) (a c e) (a d d) (a d e) (a e e) (b b b) (b b c) (b b d) (b b e) (b c c) (b c d) (b c e) (b d d) (b d e) (b e e) (c c c) (c c d) (c c e) (c d d) (c d e) (c e e) (d d d) (d d e) (d e e) (e e e))
((5 10 -2))
((10 10 -2))
((3 7 7) (31 -7 -7))
floupia: infeasible


Create a new paste based on this one


Comments: