;;Solutions for Scheme Basics Assignment
;;CS61a Summer 2000


;;;;; Question One ;;;;;
;;a.   true
;;b.   -4
;;c.   ERROR: subtract primitive expects an argument of type number 
;;d.   a
;;e.   PROCEDURE
;;f.   rocks
;;g.   ERROR: parenthases' invocation expects a procedure
;;h.   PROCEDURE
;;i.   papers
;;j.   PROCEDURE
;;k.   RUNS FOREVER
;;l.   15
;;m.   ERROR: assignment in let does not recognize bindings to variables assigned in same scope
;;n.	 either 0 or 1
;;o.   ERROR: parenthases' invocation expects a procedure
;;p.   PROCEDURE
;;q.   either 0 or 1



;;;; Question Two ;;;;

; sort takes a sentence as argument, and returns the sentence stabily sorted from lowest to higest, with duplicates in place.
; here is an easy and direct recursive way to do this in Theta(n^2)
(define (sort sen)
(if (empty? sen)
'()
(let ((m (apply min sen)))
(se m (sort (remove m sen))))))

; remove takes a word to be removed and a sentence, and returns a sentence with the first occurance of the word removed. remove is a helper function for sort.
(define (remove wrd sen)
(cond
((empty? sen) '())
((equal? wrd (first sen)) (bf sen))
(else (se (first sen) (remove wrd (bf sen))))))





;;;; Question Three ;;;;

;;This is the corrected code
(define (mystery) 1)
(define (double1 a) (+ a a))
(define (double2 a) (+ (a) (a)))
(define (bar y z)
  (define (bar-helper1 x)
    (if (= x 0)
	0
	(+ (bar-helper1 (- x 1))
	   (y))))
  (define (bar-helper2)
    (bar-helper1 z))
  bar-helper2)
(double1 (double2 (bar mystery 4)))
	
;;Normal order: 16 Times
;;Applicative order: 8 Times




;;;; Question Four ;;;;
;a. No. Sort, takes every element in a list and sticks it into a new list; having to search for the right place in
;;that new place means linear time * linear time. 
;b. Yes
;c. Yes
;d. No. Well you may think of a way to make it perversely linear, though with any sense it is constant (theta(1)) time.
;e. Yes



;;;; Question Five ;;;;

;; part 1: recurisive-fooo

; recursive-fooo takes a sentence as argument and returns a sentence with all words continaing letters repeated 2 times with those letters repeated 4 times.

(define (recursive-fooo sen)
(cond
((empty? sen) '())
((duple? (first sen))
(se (recur-quadify (first sen)) (recursive-fooo (bf sen))))
(else (se (first sen) (recursive-fooo (bf sen))))))

; recur-quadify takes a word as argument and returns a word that contains all instances of two identical letters in a row replaced with four identical letters in a row.

(define (recur-quadify wrd)
(cond
((equal? wrd "") "")
((equal? (bf wrd) "") wrd)
((equal? (first wrd) (first (bf wrd)))
(let ((ltr (first wrd)))
(word ltr ltr ltr ltr (recur-quadify (bf (bf wrd))))))
(else (word (first wrd) (recur-quadify (bf wrd))))))


;; part 2: iterative-fooo

; iterative-fooo takes a sentence as argument and returns a sentence with all words continaing letters repeated 2 times with those letters repeated 4 times.

(define (iterative-fooo sen)
(define (f-helper sen res)
(cond
((empty? sen) res)
((duple? (first sen))
(f-helper (bf sen) (se res (recur-quadify (first sen)))))
(else (f-helper (bf sen) (se res (first sen))))))
(f-helper sen '()))

; iter-quadify takes a word as argument and returns a word that contains all instances of two identical letters in a row replaced with four identical letters in a row.

(define (iter-quadify wrd)
(define (q-helper wrd res)
(cond
((equal? wrd "") res)
((equal? (bf wrd) "") (word res wrd))
((equal? (first wrd) (first (bf wrd)))
(let ((ltr (first wrd)))
(q-helper (bf (bf wrd)) (word res ltr ltr ltr ltr))))
(else (q-helper (bf wrd) (word res (first wrd)))))))

; duple? checks to see if the supplied word contains two identical letters in a row, if so it returns true, false otherwise.

(define (duple? wrd)
(cond
((or (equal? wrd "") (equal? (bf wrd) "")) #f)
((equal? (first wrd) (first (bf wrd))) #t)
(else (duple? (bf wrd)))))


;;;; Q u e s t i o n S i x ;;;;

; dist takes two posisitions, defined in the pos data abstraction, and returns the Cartesian distance between the two points. 
(define (dist pos1 pos2)
(let ((a (- (getx pos1) (getx pos2)))
(b (- (gety pos1) (gety pos2)))
(c (- (getz pos1) (getz pos2))))
(sqrt (+ (square a) (square b) (square c)))))

; pos data abstraction

(define (make-pos x y z)
(se x y z))

(define (getx pos)
(first pos))

(define (gety pos)
(first (bf pos)))

(define (getz pos)
(last pos))

(define (square x) (* x x))