;;; ============================
;;;  CMPU-145, Fall 2012
;;;  Lab 2 Solutions!!
;;;  Sept. 24, 2012
;;; ============================

(load "asmt-helper.txt")

(header "Lab 2" "Solutions")

;;;  1:  RANGE of a binary relation
;;; ----------------------------------------

(problem "1:  Range")

(printf "**** Version 1:  RANGE using MAP and REM-DUPES~%~%")

;;;  REM-DUPES  --  helper function for RANGE
;;; ---------------------------------------------
;;;  INPUT:  LISTY, a list of stuff
;;;  OUTPUT:  Same as LISTY, except that duplicate occurrences of
;;;            items are not included

(define rem-dupes
  (lambda (listy)
    (cond
      ;; Base Case:  LISTY empty
      ((null? listy)
       ;; No dupes in the empty list!
       ())
      ;; Recursive Case 1:  First element is a duplicate
      ((member (first listy) (rest listy))
       ;; So ignore first element
       (rem-dupes (rest listy)))
      ;; Recursive Case 2:  First element is not a duplicate
      (#t
       ;; So keep it
       (cons (first listy)
             (rem-dupes (rest listy)))))))

;;;  RANGE  --  uses MAP and REM-DUPES
;;; ------------------------------------
;;;  INPUT:   PAIRS, a list of pairs representing a binary relation
;;;  OUTPUT:  A list representing the range of the input relation

(define range
  (lambda (pairs)
    (rem-dupes (map second pairs))))

(tester '(range '((1 2) (1 3) (1 4) (2 3) (2 4) (3 5) (3 1) (1 6))))
(tester '(range '((1 a) (1 b) (1 c) (2 a) (3 a) (4 b) (4 c) (5 c) (4 d) (5 a))))
(tester '(range ()))
      
(printf "~%**** Version 2:  RANGE-WR using accumulator-based helper function, RANGE-ACC~%~%")      

;;;  RANGE-ACC  --  accumulator-based helper function
;;; -------------------------------------------------------------
;;;  INPUTS:  PAIRS, a list of pairs representing (at least part of) a binary relation
;;;           ACC, an accumulator that holds the range values found so far
;;;  OUTPUT:  A list of all the range values in PAIRS together with the values already
;;;           found in ACC.

(define range-acc
  (lambda (pairs acc)
    (cond
      ;; Base Case:  No more pairs
      ((null? pairs)
       ;; So return the accumulator
       acc)
      ;; Recursive Case:  At least one more pair to check
      (#t
       ;; Recursive function call does all the work
       ;;  It is called on the REST of the pairs...
       (range-acc (rest pairs)
                  ;; and the updated accumulator (only insert new value if
                  ;; it is not already in there)
                  (if (member (second (first pairs)) acc)
                      acc
                      (cons (second (first pairs)) acc)))))))

;;;  RANGE-WR  --  a "wrapper" function for RANGE-ACC
;;; ----------------------------------------------------
;;;  INPUT:  PAIRS, a list of pairs representing a binary relation
;;;  OUTPUT:  A list representing the range of the input relation

(define range-wr
  (lambda (pairs)
    ;; Just call the helper function with accumulator initialized to ()
    (range-acc pairs ())))

(tester '(range-wr '((1 2) (1 3) (1 4) (2 3) (2 4) (3 5) (3 1) (1 6))))
(tester '(range-wr '((1 a) (1 b) (1 c) (2 a) (3 a) (4 b) (4 c) (5 c) (4 d) (5 a))))
(tester '(range-wr ()))


;;;  2:  CONVERSE of a binary relation
;;; -------------------------------------------------

(problem "2: Converse")

;;;  CONVERSE
;;; -------------------------------
;;;  INPUT:  PAIRS, a list of pairs representing a binary relation
;;;  OUTPUT:  A list of pairs representing the converse of that relation

(define converse
  (lambda (pairs)
    ;; Let MAP and REVERSE do all the heavy lifting!
    (map reverse pairs)))

(tester '(converse '((1 2) (1 3) (1 4) (2 3) (2 4))))
(tester '(converse ()))
(tester '(converse '((1 a) (1 b) (1 c) (2 b) (2 e) (1 f) (1 g))))


;;;  3:  SYMMETRIC?
;;; ---------------------------------

(problem "3:  Symmetric?")

(printf "**** Version 1:  Using REMOVE to get rid of pairs that are no longer needed~%~%")

;;;  SYMMETRIC?
;;; ------------------------------
;;;  INPUT:  PAIRS, a list of pairs representing a binary relation
;;;  OUTPUT:  #t if the input relation is symmetric; #f otherwise

(define symmetric?
  (lambda (pairs)
    (cond
      ;; Base Case:  No more pairs left!
      ((null? pairs)
       ;; Success!!
       #t)
      ;; Recursive Case 1:  First pair's symmetric partner appears somewhere in PAIRS
      ;;   Note:  If first pair has the form, (X X), then it is its own symmetric partner.
      ;;          That's why we ask whether the symmetric partner is in PAIRS, not (REST PAIRS).
      ((member (reverse (first pairs)) 
               pairs)
       ;; So, keep processing pairs -- but remove the symmetric partner (if necessary)
       (symmetric? (remove (reverse (first pairs)) 
                           (rest pairs))))
      ;; Base Case 2:  First pair's symmetric partner does NOT appear in PAIRS
      (#t
       ;; Failure!
       #f))))

(tester '(symmetric? ()))
(tester '(symmetric? '((1 2) (3 4) (5 6) (4 3) (6 5) (3 3) (2 1))))
(tester '(symmetric? '((1 2) (3 4) (5 6) (4 3) (2 4))))

(printf "**** Version 2:  Calling a helper function that keeps track of original list of pairs~%~%")

;;;  SYMMETRICK?
;;; ------------------------------------------
;;;  Same functionality as SYMMETRIC? above

(define symmetrick?
  (lambda (pairs)
    ;; Just call the helper function with suitably initialized inputs
    (symmetrick-helper pairs pairs)))

;;;  SYMMETRICK-HELPER
;;; ----------------------------------------
;;;  INPUTS:  ORIG-PAIRS, a list of pairs representing the ORIGINAL relation given to
;;;              the SYMMETRICK? function (this never changes)
;;;           PAIRS, the pairs from ORIG-PAIRS that we still have to check
;;;  OUTPUT:  #t if all the pairs in PAIRS has a symmetric partner in ORIG-PAIRS

(define symmetrick-helper 
  (lambda (orig-pairs pairs)
    ;; The following expression specifies the conditions under which this function
    ;; should return #t:
    
    ;; Either PAIRS is empty (in which case every pair we were originally given
    ;; had a symmetric partner)...
    (or (null? pairs)
        ;; OR...  the symmetric pair of the FIRST pair appears somewhere in ORIG-PAIRS
        (and (member (list (second (first pairs))
                           (first (first pairs)))
                     orig-pairs)
             ;; AND... all the rest of the PAIRS check out too
             (symmetrick-helper orig-pairs (rest pairs))))))

(tester '(symmetrick? ()))
(tester '(symmetrick? '((1 2) (3 4) (5 6) (4 3) (6 5) (3 3) (2 1))))
(tester '(symmetrick? '((1 2) (3 4) (5 6) (4 3) (2 4))))


(printf "~%**** Version 3:  Using MAP~%~%")

;;;  SYMM?
;;; ---------------------------------------------------------
;;;  Same functionality as SYMMETRIC? and SYMMETRICK? above

(define symm?
  (lambda (pairs)
    
    ;; Note that when MEMBER finds an occurrence of an ITEM in a LIST, 
    ;;   it does NOT return #t; instead, it returns the portion of that LIST 
    ;;   that starts at the occurrence of ITEM that it found.
    ;;   For example:  (member 3 '(1 2 3 4 3 5 6)) ==> (3 4 3 5 6)
    ;;   In the "Full Swindle" language, anything other than #f counts as #t.
    ;;   So, when MEMBER returns a LIST, it is saying "I found something!!".
    ;;   On the other hand, when MEMBER does NOT find an occurrence of ITEM
    ;;   in a LIST, then it returns #f.
    ;; Below, we use MAP to check whether the symmetric partner of each pair
    ;;   occurs in PAIRS.  The MAP expression returns a LIST of values that
    ;;   are either LISTS (which count as #t) or #f.  
    ;; If #f appears in that list, then we know that at least one pair did
    ;;   NOT have a symmetric partner in PAIRS, in which case, we would want
    ;;   to return #f.  Thus, we use NOT to flip the polarity of the answer
    ;;   returned by MEMBER.
    ;; Note that (not #f) ==> #t  and   (not anything-else) ==> #f
    
    ;; ===> Convince yourself that the following code works!!
    
    (not (member #f (map (lambda (pr)
                           (member (reverse pr) pairs))
                         pairs)))))
        
(tester '(symm? ()))
(tester '(symm? '((1 2) (3 4) (5 6) (4 3) (6 5) (3 3) (2 1))))
(tester '(symm? '((1 2) (3 4) (5 6) (4 3) (2 4))))