#lang scheme

;; KataPotter problem
;; from:  http://codingdojo.org/cgi-bin/wiki.pl?KataPotter

;; We'll define our shopping bag as a list of bundles
(define-struct bundle (count) #:transparent)

;; A bag is a (listof bundle)


;; We're trying to calculate the price of a bag.  Without taking advantage
;; of any discounts
(define (pricing-without-discounts bag)
  (local [(define (price-of-bundle a-bundle)
            (* (bundle-count a-bundle) 8))]
    (cond
      [(empty? bag)
       0]
      [else
       (+ (price-of-bundle (first bag))
          (pricing-without-discounts (rest bag)))])))


;; Of course, we want to take advantage of discounts.

;; count-distinct: bag -> number
;; We'd like a function to count the number of distinct books left
;; in a bag.
(define (count-distinct a-bag)
  (cond [(empty? a-bag)
         0]
        [(> (bundle-count (first a-bag)) 0)
         (add1 (count-distinct (rest a-bag)))]
        [else
         (count-distinct (rest a-bag))]))



;; remove-n-distinct: bag number -> bag
;; We also want to remove n distinct books from a bag; we'll need to use
;; this when computing discounts.
(define (remove-n-distinct a-bag n)
  (cond
    [(= n 0)
     a-bag]
    [(empty? a-bag)
     (error 'remove-n-distinct)]
    [(> (bundle-count (first a-bag)) 0)
     (cons (make-bundle (sub1 (bundle-count (first a-bag))))
           (remove-n-distinct (rest a-bag) (sub1 n)))]
    [else
     (cons (first a-bag)
           (remove-n-distinct (rest a-bag) n))]))


;; discount-multiplier: number -> number
;; The discount we get if we buy n distinct books.
(define (discount-multiplier n)
  (cond
    [(= n 1) 1]
    [(= n 2) .95]
    [(= n 3) .90]
    [(= n 4) .80]
    [(= n 5) .75]))


;; Now we can compute the optimal pricing of a bag.
;; optimal-pricing: bag -> number
(define (optimal-pricing a-bag)
  (local [(define (find-best-solution-trying-n-distinct n best-so-far)
            (cond
              [(> n (count-distinct a-bag))
               best-so-far]
              [else
               (let ([price-with-n
                      (+ (* (discount-multiplier n) n 8)
                         (optimal-pricing (remove-n-distinct a-bag n)))])
                 (find-best-solution-trying-n-distinct
                  (add1 n)
                  (min best-so-far price-with-n)))]))]
    (cond [(= (count-distinct a-bag) 0)
           0]
          [else
           (find-best-solution-trying-n-distinct 1 +inf.0)])))


;; We now expect to see (optimal-pricing (list (make-bundle 2) (make-bundle 2) (make-bundle 2) (make-bundle 1) (make-bundle 1))) is 51.20.
(optimal-pricing (list (make-bundle 2)
                       (make-bundle 2)
                       (make-bundle 2)
                       (make-bundle 1)
                       (make-bundle 1)))