; In the Min Cover problem, a state consists of
;   the size of the initial set
;   a list of the currently uncovered elements
;   a list of the currently available subsets,
;   and a list of the subsets used so far for the cover

(define (initial-size state) (car state))
(define (uncovered state) (cadr state))
(define (subsets state) (caddr state))
(define (cover state) (cadddr state))

(define (build-state i u s c) (list i u s c))

(define start1 '(8 (1 2 3 4 5 6 7 8)
                  ((2 4 6 8) (3 6) (4 8) (5) (6) (7) (8))
                  ()))
(define start2 '(8 (1 2 3 4 5 6 7 8)
                  ((1) (2 4 6 8) (3 6) (4 8) (5) (6) (7) (8))
                  ()))
(define start3 '(7 (1 2 3 4 5 6 7)
                  ((1 2 3) (1 3 5) (1 2 4 6) (2 3 6) (4 7))
                  ()))
(define start4 '(7 (a b c d e f g)
                  ((e g g) (b a g) (b e d) (f a c e) (c a b)
                   (b a g g a g e) (c a b b a g e))
                  ()))
(define start5 '(7 (mon tue wed thu fri sat sun)
                  ((mon wed fri) (sat sun) (fri sat) (tue thu)
                   (mon tue wed thu fri) (sat sun mon tue wed))
                  ()))
(define start6 '(6 (1 2 3 4 5 6) ((5) (4) (1) (3) (2) (6)) ()))


; A state is a goal state if all elements have been covered

(define (goal? state) (null? (uncovered state)))


; This estimator ranks first by the length of the current partial cover,
;   and then by the number of uncovered elements (smaller is better)
; To be optimistic, its value must be at most
;   1 + [the length of the current partial cover]

(define (estimator state)
  (if (goal? state)
      (length (cover state))
      (+ (length (cover state))
         (/ (length (uncovered state))) (initial-size state))))


; The successors of a given state are obtained by adding every remaining
;   subset to the cover.  SUCCESSORS calls a recursive function
;   SUCCESSORS-REC, which does all the work, taking an extra argument
;   SUCCESSORS-SO-FAR to contain the list of successors.
; An auxiliary function REMOVE-ALL is used to remove all elements of
;   the new subset from the set of uncovered elements.  It in turn
;   calls REMOVE to remove one element at a time.

(define (successors state)
  (define (successors-rec subs size uncov cov successors-so-far)
    (cond ((null? subs) successors-so-far)
          (else (successors-rec (cdr subs) size uncov cov
                                (cons (build-state
                                        size
                                        (remove-all (car subs) uncov)
                                        (cdr subs)
                                        (cons (car subs) cov))
                                      successors-so-far)))))
  (define (remove-all source target)
    (define (remove elt set)
      (cond ((null? set) set)
            ((eqv? elt (car set)) (cdr set))
            (else (cons (car set) (remove elt (cdr set))))))
    (cond ((null? source) target)
          (else (remove-all (cdr source) (remove (car source) target)))))
  (successors-rec (subsets state) (initial-size state)
                 (uncovered state) (cover state) '()))