;Problem Set 5 Solutions
;January 23, 2006
;Grant Oladipo

(define tstlst1 (list 1 9 38 3 7 5 2)) 

;;;;;;;;;;;
;Problem 1;
;;;;;;;;;;;

(define (square-list lst)
  (if (null? lst)
      null
      (cons (* (car lst) (car lst)) (square-list (cdr lst)))))

;;;;;;;;;;;
;Problem 2;
;;;;;;;;;;;

(define (stutter-list lst)
  (if (null? lst)
      null
      (cons (car lst) (cons (car lst) (stutter-list (cdr lst))))))

(define (alt-stutter-list lst)
  (if (null? lst)
      null
      (append (list (car lst) (car lst)) (alt-stutter-list (cdr lst)))))

;;;;;;;;;;;
;Problem 3;
;;;;;;;;;;;

(define (only-even lst)
  (if (null? lst)
      null
      (if (even? (car lst))
          (cons (car lst) (only-even (cdr lst)))
          (only-even (cdr lst)))))

;;;;;;;;;;;
;Problem 4;
;;;;;;;;;;;

(define (add-lists lst1 lst2)
  (if (null? lst1)
      null
      (cons (+ (car lst1) (car lst2)) (add-lists (cdr lst1) (cdr lst2)))))

;;;;;;;;;;;
;Problem 5;
;;;;;;;;;;;

(define (replace-elem lst old new)
  (if (null? lst)
      null
      (if (= old (car lst))
          (cons new (replace-elem (cdr lst) old new))
          (cons (car lst) (replace-elem (cdr lst) old new)))))

;;;;;;;;;;;
;Problem 6;
;;;;;;;;;;;

(define (make-point x y)
  (list x y))

;PART A
;;;;;;;;

(define (make-polygon lst)
  lst)

#| Even though procedure is simply returning the exact same list, then you should not be worried about what the actual make up of a polygon is after you use the procedure.  All you should know is that the list of points is now a "polygon."|#

;PART B
;;;;;;;;

;part i
(define (get-polygon-point poly n)
  (if (= 0 n)
      (car poly)
      (get-polygon-point (cdr poly) (- n 1))))

#| Accessor functions can use list operations on poly only because they are the base level of the abstraction.  They are the only procedures that recognize that poly is really just a list.  When you want to alter your abstraction, you will alter your accessor functions accordingly. |#

;part ii
(define (get-polygon-point-list poly)
  poly)

#| This accessor is like this simply because the list of points it is to return is the actual polygon itself, it is still necessary, however, because of the implementation of an abstraction.  Later on you will see what we mean. |#

;PART C
;;;;;;;;

(define (make-segment p1 p2) 
  (list p1 p2))

(define (polygon->segments poly)   
  (polygon->segments-help poly 0))

#| When you first begin the problem, it should become pretty clear that you cannot complete it without some helper, so we put a helper and sent it a segment number.  Just like there are 0-n points, there are 0-n segments with the 0th segment being being point 0 and 1 and the nth segment being point n and 0. |#

(define (polygon->segments-help poly seg-num)
    (if (= seg (- (length (get-polygon-point-list poly)) 1)) 
        #| We test if we are at the last segment which would be the nth segment.  We get n by finding the length of the list of points.  Now it would still work if we just did (length poly), but that would be an ABSTRACTION VIOLATION because length is a list operator and poly is a "polygon."  When we are at the nth segment we make the special segment with the right points. |#
        (list (make-segment (get-polygon-point poly seg-num) (get-polygon-point poly 0)))
        (cons (make-segment (get-polygon-point poly seg-num) (get-polygon-point poly (+ seg-num 1))) 
              (polygon->segments-help poly (+ seg-num 1)))))

#| When we are not at the nth segment, the recursive case should be that we make the points seg-num and seg-num+1 into a segment and add them onto the segments list with cons. |#

;PART D
;;;;;;;;

(define (get-x p)
  (car p))

(define (get-y p)
  (cadr p))

(define (polygon-lower-left-point poly)
  (polygon-lower-left-point-help poly (get-polygon-point poly 0)))

#|Similar to the other problem, you need a helper to do this procedure.  We send the helper the polygon (look at alternative solution for major difference) and arbitrarily choose the first point in the polygon to be our tentative lowest and leftmost point. |#

(define (polygon-lower-left-point-help poly lower-left-point)
  (if (null? (get-polygon-point-list poly))
      #|If the polygon has no more points then we know that the lower-left-point variable has the answer to the procedure|#
      lower-left-point
      (if (and (<= (get-x (car(get-polygon-point-list poly))) 
                   (get-x lower-left-point))
               (<= (get-y (car (get-polygon-point-list poly)))
                   (get-y lower-left-point)))
          (polygon-lower-left-point-help (make-polygon (cdr (get-polygon-point-list poly))) 
                                         (car (get-polygon-point-list poly)))
          #| If the point that is first in the point-list of the current polygon is more left and lower than the point that is in the current lower-left-point parameter then call the procedure.  With the new call, remove the point you just compared to the lowest-left-point.  Notice how we had to get-polygon-point-list and then cdr and then make-polygon again.  This would work if we just put (cdr poly), but it would be an ABSTRACTION VIOLATION.  We have to get a list before we can use cdr, and we have to make it a polygon again because the procedure polygon-lower-left-point-help is expecting a polygon to be sent to it.  Lastly, since the comparison was successful we send a new lower-left-point by getting it from the point-list |#
          (polygon-lower-left-point-help (make-polygon (cdr (get-polygon-point-list poly))) lower-left-point))))
          #| If the point is not more left and lower then we just continue by still removing the compared point from the polygon, but we leave lower-left-point the same since it is still the lowest and most left. |#
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (alt-polygon-lower-left-point poly)
  (alt-polygon-lower-left-point-help (cdr (get-polygon-point-list poly)) (get-polygon-point poly 0)))

(define (alt-polygon-lower-left-point-help point-list lower-left-point)
  (if (null? point-list)
      lower-left-point
      (if (and (<= (get-x (car point-list)) 
                  (get-x lower-left-point))
               (<= (get-y (car point-list)) 
                  (get-y lower-left-point)))
          (alt-polygon-lower-left-point-help (cdr point-list) (car point-list))
          (alt-polygon-lower-left-point-help (cdr point-list) lower-left-point))))

#|This alternate solution uses the fact that the helper function doesn't need the polygon, just a list to operate with, so we send it just that.  Also since we send the helper function a list, we can cdr it because cdr is a list operation.  We cdr it before sending so that we dont have to compare the first point to itself. The helper function is now a lot less robust because we can use list operation directly on the list that was sent to the function.|#