; 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 (negate x) (- x))

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

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

(display (binom 5 3)) (newline)
(display (binom (+ 5 3 -1) 3)) (newline)

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

(display (combs 3 '(a b c d e))) (newline)

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

(display (combs 3 '(a b c d e))) (newline)

(define (floupia price coins)
  (let ((coins (append coins (map negate coins))))
    (let loop ((n 1))
      (let ((xs (filter (lambda (xs) (= (sum xs) price))
                        (combs 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)

10
35
((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))
((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))