;;; ==========================================
;;;  CMPU-145, Spring 2013
;;;  Asmt. 2 Solutions -- Programming Part
;;; ==========================================

(load "asmt-helper.txt")

(header "Asmt. 2" "Solution to Programming Problem (#4)")

;;; =================================================
(problem "4: Cartesian Product")
;;; =================================================

;;;  CARTESIAN-PRODUCT
;;; -----------------------------------
;;;  INPUTS:  LISTY, LISTZ, two lists representing sets
;;;  OUTPUT:  A list-of-lists representing the cartesian product of 
;;;           the two input sets

(define cartesian-product
  (lambda (listy listz)
    ;; The following shows a cool trick using the built-in APPLY and APPEND
    ;; functions.  Note the following:
    ;;    > (apply append '((1 2 3) (4 5) (6) (7 8 9 10)))
    ;;    (1 2 3 4 5 6 7 8 9 10)
    ;; So, the APPLY function applies the APPEND function to all of the
    ;; subsidiary lists in the list-of-lists!
    ;; Below, the MAP expression returns a list of lists, which APPLY-APPEND
    ;; nicely concatenates!    
    (apply append (map (lambda (y)
                         (map (lambda (z)
                                (list y z))
                              listz))
                       listy))))

(tester '(cartesian-product () '(a b)))
(tester '(cartesian-product '(1) '(a)))
(tester '(cartesian-product '(1 2) '(a b c)))
(tester '(length (cartesian-product '(1 2 3 4 5) '(1 2 3 4 5 6 7))))
(newline)


;;; ===> Version 2, given below, is outlined in the assignment instructions


;;;  HELPY -- helper function for CART-PROD-ALT, defined below
;;; ------------------------------------------------------------
;;;  INPUTS:  Y, an item
;;;           LISTZ, a list
;;;  OUTPUT:  A list of ordered pairs of the form (y z), where z is an
;;;             element of LISTZ, as illustrated below:
;;;              (helpy 2 '(a b c)) ==> ((2 a) (2 b) (2 c))

(define helpy 
  (lambda (y listz)
    (map (lambda (z) (list y z))
         listz)))

(tester '(helpy 2 '(a b c d)))
(tester '(helpy 3 '(a b c d e)))
(newline)

;;;  CART-PROD-ALT  --  alternate version of CARTESIAN-PRODUCT
;;; ------------------------------------------------------------
;;;  Same functionality as CARTESIAN-PRODUCT, but uses HELPY.
;;;  Walks through the elements of LISTY; for each Y in LISTY,
;;;  it uses (HELPY Y LISTZ) to create a list of the ordered
;;;  pairs whose first elements are Y; then it appends all of 
;;;  those lists together.

(define cart-prod-alt
  (lambda (listy listz)
    (cond
      ;; Base Case:  LISTY is empty
      ((null? listy)
       ())
      ;; Recursive Case:  At least one element in LISTY
      (#t
       ;; Let HELPY form a list of pairs, all of whose first elements are 
       ;; (FIRST LISTY).  Then the recursive function call to CART-PROD-ALT
       ;; generates a list containing all of the rest of the desired pairs.
       (append (helpy (first listy) listz)
               (cart-prod-alt (rest listy) listz))))))

(tester '(cart-prod-alt () '(a b)))
(tester '(cart-prod-alt '(1) '(a)))
(tester '(cart-prod-alt '(1 2) '(a b c)))
(newline)
(tester '(length (cart-prod-alt '(1 2 3 4 5) '(1 2 3 4 5 6 7))))