;;; ================================
;;;  CMPU-145, Spring 2013
;;;  Asmt. 1 Solutions
;;; ================================

(load "asmt-helper.txt")

(header "Asmt. 1" "Solutions!")

;;; ---------------
;;;  (1)
;;; ---------------

(problem "(1) DISJOINT?")

;;;  DISJOINT?
;;; ---------------------------------------------
;;;  INPUTS:  Two lists representing sets
;;;  OUTPUT:  #t if the two sets are disjoint (i.e., have no elements in common)
;;;           #f otherwise

(define disjoint?
  (lambda (listy listz)
    (cond
      ;; Base Case:  LISTY is empty
      ((null? listy)
       ;; Empty set is disjoint from every set (including itself)
       #t)
      ;; Base Case 2:  We found an element in both lists!
      ((member (first listy) listz)
       ;; So they can't be disjoint
       #f)
      ;; Recursive Case:  Keep looking
      (#t
       (disjoint? (rest listy) listz)))))

;;;  ALT-DISJOINT?
;;; ---------------------------------------------
;;;  Same functionality as DISJOINT?, but implemented using boolean operators.

(define alt-disjoint?
  (lambda (listy listz)
    ;; The following expression specifies the conditions under which this
    ;; function should return #t
    
    ;; Either LISTY is empty...
    (or (null? listy)
        ;; OR... The first element of LISTY is not also in LISTZ
        (and (not (member (first listy) listz))
             ;; AND... neither are any of the rest of the elements of LISTZ
             (alt-disjoint? (rest listy) listz)))))

(tester '(disjoint? () ()))
(tester '(disjoint? () '(a b c)))
(tester '(disjoint? '(a b c) '(d e f g h)))
(tester '(disjoint? '(a b c d) '(d e b f c h)))
(tester '(disjoint? '(a b c d e f g) '(1 2 3 4 g 5 6)))
(newline)
(tester '(alt-disjoint? () ()))
(tester '(alt-disjoint? () '(a b c)))
(tester '(alt-disjoint? '(a b c) '(d e f g h)))
(tester '(alt-disjoint? '(a b c d) '(d e b f c h)))
(tester '(alt-disjoint? '(a b c d e f g) '(1 2 3 4 g 5 6)))

;;; ---------------
;;;  (2)
;;; ---------------

(problem "(2) POWER-SET")

;;;  POWER-SET
;;; ------------------------------
;;;  INPUT:  LISTY, a list representing a set
;;;  OUTPUT:  A list of lists representing the power set of LISTY (i.e., the
;;;            set of all subsets of LISTY)

(define power-set
  (lambda (listy)
    (cond
      ;; Base Case:  LISTY is empty
      ((null? listy)
       ;; The power set of the empty list contains one element:  the empty list!
       (list ()))
      ;; Recursive Case:  LISTY has at least one element
      (#t
       ;; Use LET* to generate a sequence of useful results
       (let* ((firsty (first listy))
              ;; PSET-RESTY = the power-set of the REST of the list
              (pset-resty (power-set (rest listy)))
              ;; ALT-PSET-RESTY = same as PSET-RESTY, except that FIRSTY
              ;;                      has been consed onto each subset
              (alt-pset-resty (map (lambda (subbie) (cons firsty subbie))
                                   pset-resty)))
         ;; The answer is generated by appending the results collected
         ;; in PSET-RESTY and ALT-PSET-RESTY
         (append pset-resty alt-pset-resty))))))

(tester '(power-set ()))
(tester '(power-set '(a)))
(tester '(power-set '(1 2)))
(tester '(power-set '(X Y Z)))
(newline)
(tester '(length (power-set '(1 2 3 4 5 6))))
(tester '(length (power-set '(1 2 3 4 5 6 7 8 9 10))))