(unit/sig
  (good-case bad-case short1 short2 med1 med2 long1 long2
   strongest-coalition-1 sc1 strongest-coalition-2 sc2
;   gabi helmut pierre chantelle pebbles bambam godzillette
   )
  (import plt:userspace^)

;; (powers-of-2 n)
;; n is an integer
;; Return a list of n+1 integers:
;;   the powers of two, 2^n downto 2^0
;; 
(define (powers-of-2 n)
  (if (zero? n)
      (list 1)
      (let ([r (powers-of-2 (1- n))])
	(cons (* 2 (car r)) r))))

;; (powers-of-1 n)
;; n is an integer
;; Return a list of n+1 integers:
;;   the powerr of one, 1^n downto 1^0
;; 
(define (powers-of-1 n)
  (if (zero? n)
      (list 1)
      (cons 1 (powers-of-1 (1- n)))))


(define good-case powers-of-2)
(define bad-case
  (lambda (n)
    (append (powers-of-1 (1- n)) (list 2))))

(define short1 (good-case 10))
(define short2 (bad-case  10))
(define med1   (good-case 20))
(define med2   (bad-case  20))
(define long1  (good-case 100))
(define long2  (bad-case  100))




;; (strongest-coalition-1  popularities)
;; popularities is a list of numbers: popularity ratings of politicians
;; Return the strength of the most popular coalition,
;;  where a coalition's strength is as follows:
;;   Think of people joining a group, one by one.
;;      If they're more popular than
;;      any existing coalition, they found their own new coalition.
;;      Otherwise they join the existing most popular coalition, adding
;;      their popularity.
;;
(define strongest-coalition-1
  (lambda (popularities)
    (cond [(null? popularities) 0]
          [else (if (>= (car popularities)
                        (strongest-coalition-1 (cdr popularities)))
                    (car popularities)
                    (+ (car popularities)
                       (strongest-coalition-1 (cdr popularities))))])))


;; save myself some typing!
;;
(define sc1 strongest-coalition-1)



;; revised version of strongest-coalition-1, see above
;;
(define strongest-coalition-2
  (lambda (popularities)
    (cond [(null? popularities) 0]
          [else (let ([mob-pop (strongest-coalition-2 (cdr popularities))])
                     (if (>= (car popularities) mob-pop)
                         (car popularities)
                         (+ (car popularities) mob-pop)))])))

(define sc2 strongest-coalition-2)






;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; family tree example, for data sharing:
;;
;         Gabi    Helmut
;          |         |
;          +---------+
;              |
;          +--------+
;          |        |
;Mary   Pierre   Chantelle  Hunko
;|        |         |        |
;+--------+         +--------+
;   |                    |
; Pebbles               Bambam
;   |                     |
;   +---------------------+
;             |
;          Godzillette

;; If we export our branch structure, it won't be the same
;; as the branch structures we want them to define by hand!
;; Just have them cut-and-paste the tree definition from the web page.
;;
;(define-structure (branch mom name dad))
;
;(define gabi      (list 'unknown 'gabi 'unknown))
;(define helmut    (list 'unknown 'helmut 'unknown))
;(define pierre    (list gabi 'pierre helmut))
;(define chantelle (list gabi 'chantelle helmut))
;(define pebbles   (list (list 'unknown 'Mary 'unknown) 'pebbles pierre))
;(define bambam    (list chantelle 'bambam (list 'unknown 'Hunko 'unknown)))
;(define godzillette  (list pebbles 'godzillette bambam))

)