; In the Shortest Superstring problem, a state consists of
;    a candidate superstring
;    a count of the initial list of substrings
;    a list of the alphabet symbols appearing in any substring
;    a list of the substrings uncovered by the current candidate superstring


(define (superstring state) (car state))
(define (initial-size state) (cadr state))
(define (alphabet state) (caddr state))
(define (strings state) (cadddr state))
(define (build-state s i a str) (list s i a str))

(define start1 '(() 4 (a b) ((a b b) (b a b) (a b a b) (b b a))))
(define start2 '(() 6 (a b c) ((a b) (b c) (a c) (c a) (c b) (b a))))
(define start3 '(() 5 (0 1) ((0) (0 1) (0 0 1) (0 0 0 1) (0 0 0 0 1))))
(define start4 '(() 8 (0 1) ((0 0 0) (0 0 1) (0 1 0) (0 1 1)
                             (1 0 0) (1 0 1) (1 1 0) (1 1 1))))
(define start5 '(() 4 (a b) ((a a) (a b a) (a b b a) (a b b b a))))



; A state is a goal state if all the substrings are covered by the superstring

(define (goal? state) (null? (strings state)))


; The estimator gives highest priority to the length of the string constructed
;   so far, then to the number of input strings remaining (fewer is better)
; The initial length is subtracted to make sure the estimate is optimistic

(define (estimator state)
  (+ (length (superstring state))
     (/ (length (strings state)) (initial-size state))))


; The successor states of a given state are obtained by adding every
;   possible alphabet symbol to the beginning of the superstring.
; SUCCESSORS calls a recursive function SUCCESSORS-REC, which does
;   all the work.
; The only other state component that needs to be modified is the
;   list of uncovered substrings.  Determining which substrings
;   are covered by the new superstring is the job of the REMAINING
;   function.

(define (successors state)
  (define (successors-rec superstr size init-alpha
                          alpha strs successors-so-far)
    (cond ((null? alpha) successors-so-far)
          (else (successors-rec
                  superstr size init-alpha (cdr alpha) strs
                  (cons (build-state (cons (car alpha) superstr)
                                     size
                                     init-alpha
                                     (remaining superstr (car alpha) strs))
                        successors-so-far)))))
  ; remove all elements of STRS which are prefixes of (CONS SYMBOL SUPERSTR)
  (define (remaining superstr symbol strs)
    (define (prefix? source target)
      (cond ((null? source) #t)
            ((null? target) #f)
            ((eq? (car source) (car target))
             (prefix? (cdr source) (cdr target)))))
    (cond ((null? strs) '())
          ((and (eq? symbol (car (car strs)))
                (prefix? (cdr (car strs)) superstr))
           (remaining superstr symbol (cdr strs)))
          (else (cons (car strs) (remaining superstr symbol (cdr strs))))))
  (successors-rec (superstring state) (initial-size state)
                  (alphabet state) (alphabet state) (strings state) '()))