;;; =========================
;;;  CMPU-145, Spring 2013
;;;  Lab 3 Solutions
;;;  Feb. 18, 2013
;;; =========================

(load "asmt-helper.txt")

(header "Lab 3" "Solutions")

(problem "1:  PRINT-ALL-PAIRS")

;;;  PRINT-ALL-PAIRS
;;; -----------------------------
;;;  INPUT:  LISTY, a list
;;;  OUTPUT:  None
;;;  SIDE EFFECT:  Prints all pairs consisting of elements from LISTY

(define print-all-pairs
  (lambda (listy)
    (dolist (x listy)
            (dolist (y listy)
                    (printf "(~A,~A) " x y)))))

(tester '(print-all-pairs '(a b c)))
(newline)
(tester '(print-all-pairs '(1 2 3 4)))
(newline)

(problem "2:  ACCUM-ALL-PAIRS")

;;;  ACCUM-ALL-PAIRS
;;; ------------------------------
;;;  INPUT:  LISTY, a list
;;;  OUTPUT:  A list of all pairs consisting of elements from LISTY

(define accum-all-pairs
  (lambda (listy)
    ;; Create local variable, ACC, to accumulate pairs
    (let ((acc ()))
      (dolist (x listy)
              (dolist (y listy)
                      ;; Update value of ACC
                      (set! acc (cons (list x y)
                                      acc))))
      ;; return the accumulated list of pairs
      acc)))

(tester '(accum-all-pairs '(a b c)))
(tester '(accum-all-pairs '(1 2 3 4)))


(problem "3:  FIND-SAT-PAIR")

;;;  FIND-SAT-PAIR
;;; ---------------------------------------
;;;  INPUTS:  LOL, a list of pairs
;;;           PRED, a function that takes two inputs and returns boolean output
;;;  OUTPUT:  A pair (x y) such that (pred x y) returns #t
;;;           Or, if no such pair exists, returns #f

(define find-sat-pair
  (lambda (lol pred)
    (cond
      ;; Base Case:  LOL is empty 
      ((null? lol)
       ;; No satisfying pairs!
       #f)
      ;; Base Case 2:  WE found a satisfying pair!
      ((pred (first (first lol))
             (second (first lol)))
       ;; So return it!
       (first lol))
      ;; Recursive Case:  Haven't found a sat. pair yet
      (#t
       ;; So keep looking
       (find-sat-pair (rest lol) pred)))))

(tester '(find-sat-pair '((1 2) (1 3) (1 4) (2 2) (2 3) (2 4) (3 3) (3 4))
                        (lambda (x y) (= (* x x) y))))
(newline)

(tester '(find-sat-pair '((1 2) (1 3) (1 4) (2 2) (2 3) (2 9) (3 3) (3 4))
                        (lambda (x y) (= (* x x) y))))

(problem "4: FIND-SAT-PAIR-FROM")

;;;  FIND-SAT-PAIR-FROM
;;; -------------------------------------------
;;;  INPUTS:  LISTY, a list of stuff
;;;           PRED, a predicate that takes two inputs (like those
;;;                   in LISTY),
;;;  OUTPUT:  A pair (x y) where (pred x y) ==> #t, and both
;;;               x and y are in LISTY

(define find-sat-pair-from
  (lambda (listy pred)
    (find-sat-pair (accum-all-pairs listy) pred)))

(tester '(find-sat-pair-from '(1 2 3 4) >))
(tester '(find-sat-pair-from '(1 2 3 4) <))
(tester '(find-sat-pair-from '(1 2 3 4)
                             (lambda (x y) (= x (* y y))))