; Assumes votes sorted in nonincreasing order
; Assumes all inequalities must be strict
; Could automatically assign first vote to one side or other

; A state has 3 components --
;   TOTALS, a pair of integers representing the running total of the
;           votes already case on each side
;   SIDES, a pair of lists representing the list of votes cast on
;           each side
;   VOTES, a list of uncast votes

(define (build-state t s v) (list t s v))
(define (totals state) (car state))
(define (sides state) (cadr state))
(define (votes state) (caddr state))


(define start1 (build-state '(0 . 0) '(() . ()) '(64 32 16 8 4 3 2)))
(define start2 (build-state '(0 . 0) '(() . ()) '(128 64 32 16 8 4 2)))
(define start3 (build-state '(0 . 0) '(() . ()) '(11 11 11 11 11 11)))
(define start4 (build-state '(0 . 0) '(() . ()) '(40 30 20 10 7 5 3 2)))
(define start5 (build-state '(0 . 0) '(() . ()) '(40 30 20 20 7 5 3 2)))
(define start6 (build-state '(0 . 0) '(() . ()) '(40 30 20 20 20 5 3 2)))
(define start7 (build-state '(0 . 0) '(() . ()) '(80 40 30 20 15 8 8 3)))


; A goal state is a state with a single number remaining in VOTES,
;   such that that number will be in the majority when added to
;   either side.

(define (goal? state)
  (and (null? (cdr (votes state)))
       (> (+ (car (totals state)) (car (votes state)))
          (cdr (totals state)))
       (> (+ (cdr (totals state)) (car (votes state)))
          (car (totals state)))))


; The current difference between the two running totals is not guaranteed
;   an optimistic estimate for the optimization version of this
;   problem, but it's a reasonable estimator for the decision problem

(define (estimator state)
  (abs (- (car (totals state)) (cdr (totals state)))))


; Generates 2 successors for those states with more than one voter
;   remaining.  One successor has the next voter on the first side
;   and one has the next voter on the next side.
; generates nonfeasible states -- but note that they're given low priority

(define (successors state)
  (cond ((null? (cdr (votes state))) '())
        (else (let ((v (car (votes state))))
                (list (build-state (cons (+ v (car (totals state)))
                                         (cdr (totals state)))
                                   (cons (cons v (car (sides state)))
                                         (cdr (sides state)))
                                   (cdr (votes state)))
                      (build-state (cons (car (totals state))
                                         (+ v (cdr (totals state))))
                                   (cons (car (sides state))
                                         (cons v (cdr (sides state))))
                                   (cdr (votes state))))))))