; This function takes a list of three coefficients of a quadratic 
;   polynomial (the leading coefficient first) and returns a list of
;   the two zeros of the polynomial (which may be complex). 
; It doesn't check for illegal input, including the case where 
;   the leading coefficient is 0.
                                                     
(define (quadratic a b c)
  (let ((d (sqrt (- (* b b) (* 4 a c)))))
    (list (/ (+ (- b) d) (* 2 a))
          (/ (- (- b) d) (* 2 a)))))


; This predicate takes a string as input and determines
;   whether the string contains a whitespace character.
; It doesn't check for illegal input.

(define (has-whitespace? str)
  (member #t (map char-whitespace? (string->list str))))


; This function takes an input list and returns the list obtained 
;   by removing every noncharacter from the list.
; It doesn't check for illegal input.
 
 (define (remove-noncharacters ls)
  (cond ((null? ls) ls)
        ((char? (car ls)) 
         (cons (car ls) (remove-noncharacters (cdr ls))))
        (else (remove-noncharacters (cdr ls)))))


; This function takes an association list as argument, and removes all 
;   superfluous elements from this list.  That is, it removes the 
;   second and subsequent occurrences of all keys (first components)
;   in the list.
; It doesn't check for illegal input.
; It uses a straightforward tail-recursive helper function to construct
;   the output list.

(define (clean-alist alist)
  (define (helper alist result)
    (cond ((null? alist) result)
          ((assoc (caar alist) result)
           (helper (cdr alist) result))
          (else (helper (cdr alist) 
                        (cons (car alist)result)))))
  (helper alist '()))

         
; A structure for representing the time of day.
; The intention is that it uses a 24-hour internal
;   representation (so that the hour component is
;   an integer from 0 to 23 and the minute component
;   is an integer from 0 to 59), but this will not
;   be enforced by the make-time-of-day constructor.

(define-struct time-of-day (hour minutes))


; This function is effectively an error-checking constructor
;   for the time-of-day structure type.  It takes two integers
;   representing the two components of this type, and returns
;   a structure with these components if they are integers 
;   in the appropriate range (0-23 for the hour; 0-59 for the 
;   minutes.  Otherwise it returns a string representing an
;   error message.

(define (build-time-of-day hour minutes)
  (cond ((not (integer? hour))
         "the hour must be an integer")
        ((not (integer? minutes))
         "the minutes must be an integer")
        ((or (< hour 0) (>= hour 24))
         "the hour must be in the range 0-23")
        ((or (< minutes 0) (>= minutes 60))
         "the minutes must be in the range 0-50")
        (else (make-time-of-day hour minutes))))


; This predicate checks for equality of two time-of-day
;   structures.  It returns #t iff the two structures
;   represent the same time of day.
; It doesn't check for illegal input.

(define (time-of-day-equal? t1 t2)
  (and (= (time-of-day-hour t1)
          (time-of-day-hour t2))
       (= (time-of-day-minutes t1)
          (time-of-day-minutes t2))))


; This function takes a time-of-day structure and returns a 
;   string representing the corresponding time of day in 
;   a normal U.S. format.  If the argument is not a time-of-day
;   structure, a string representing an error message is returned.
; The function assumes that all time-of-day are well-formed in that
;   their components satisfy the constraints of the build-time-of-day
;   function.  If not, the function could return a nonsense string
;   or even crash.

(define (time-of-day->string time)
  (define (pad string) (if (< (string-length string) 2) 
                           (string-append "0" string)
                           string))
  (cond ((not (time-of-day? time))
         "the argument must be a time-of-day structure")
        ((zero? (time-of-day-hour time))
         (string-append "12:" 
                        (pad (number->string (time-of-day-minutes time)))
                        " a.m."))
        ((= (time-of-day-hour time) 12)
         (string-append "12:" 
                        (pad (number->string (time-of-day-minutes time)))
                        " p.m."))
        ((< (time-of-day-hour time) 12)
         (string-append (number->string (time-of-day-hour time)) 
                        ":" 
                        (pad (number->string (time-of-day-minutes time)))
                        " a.m."))
        (else
         (string-append (number->string (- (time-of-day-hour time) 12))
                        ":" 
                        (pad (number->string (time-of-day-minutes time)))
                        " p.m."))))

         
; This function takes a start symbol for a grammar, a collection of
;   rules for the grammar, and a list of nonterminals of the grammar,
;   and returns a list of the nonterminal symbols that are reachable 
;   from the start symbol.
; The collection of rules is assumed to be represented as an 
;   association list mapping symbols to lists of right-hand sides
;   of their rules, where each right-hand side is a list of symbols.
;   So for example the rule set {E -> E+T | T,  T -> T*F | F,  F -> x}
;     would be represented as ((E (E + T) (T)) (T (T * F) (F)) (F (x)))
; There is no checking for illegal input, except that the start
;   symbol is checked to see whether it's a member of the list
;   of nonterminals.  Also, duplicate rules in the rule list are
;   harmless for this function.  It is assumed that all keys 
;   (first components) in the association list are in the list 
;   of nonterminals.
; Note that this function could be used with only minor modification
;   to check a grammar for direct or indirect left recursion
; The function uses a binary tail recursive helper function.  Its 
;   arguments are lists of those symbols known to be accessible, 
;   and for which accessibility from the symbol respectively has
;   not and has been explored.  It repeatedly takes the first
;   symbol from the first list, finds its directly accessible
;   successors (assuming it's an unexplored nonterminal), and
;   adds these successors to the unexplored list while transferring
;   the symbol to the explored list.  When the unexplored list is
;   exhausted, the explored list is returned.
; Another auxiliary function finds the list of symbols directly
;   accessible from a given symbol, by appending together the
;   right-hand sides of that symbol's rules.


(define (reachable-symbols start-symbol alist-of-rules list-of-nonterminals)
  (define (adjacent-symbols symbol)
    (apply append (cdr (assoc symbol alist-of-rules))))
  (define (helper new-reachable-symbols old-reachable-symbols)
    (cond ((null? new-reachable-symbols) old-reachable-symbols)
          ((not (member (car new-reachable-symbols) list-of-nonterminals))
           (helper (cdr new-reachable-symbols) old-reachable-symbols))
          ((member (car new-reachable-symbols) old-reachable-symbols)
           (helper (cdr new-reachable-symbols) old-reachable-symbols))
          (else (helper (cdr new-reachable-symbols) 
                        (helper (adjacent-symbols (car new-reachable-symbols))
                                (cons (car new-reachable-symbols)
                                      old-reachable-symbols))))))
  (if (member start-symbol list-of-nonterminals)
      (helper (adjacent-symbols start-symbol) (list start-symbol))
      null))