;; Practice Final Solutions


;; Warm Up

(define (copies n wd)
  (if (= n 0)
      '()
      (sentence wd (copies (- n 1) wd))))

(define (zip left right)
  (if (or (null? left) (null? right))
      (append left right)
      (append (list (car left) (car right))
	      (zip (cdr left) (cdr right)))))


;; ADTs: The answers to these are in the book/Section 3 lecture notes.


;; Caesar Cyphers

(define (caesar-word wd num)
  (every (repeated rot num) wd))

(define (caesar sent num)
  (every (lambda (wd) (caesar-word wd num)) sent))

;; Hote: there are 26 letters in the english alphabet, so rotating
;; a letter 26 times gives you that same letter.

(define (caesar-decode sent num)
  (every (lambda (wd) (caesar-wd wd (- 26 num))) sent))


;; Quicksort

;; The description in the practice final is not quite right, and it
;; needs a small modification. (If you implement exactly what the problem
;; says, you'll end up with a procedure that never reaches the base case.)

;; The correct way: pick the first element as your "pivot", then separate
;; the rest of the elements into a list of smaller ones and a list of bigger
;; ones (compared to the pivot). By smaller we really mean less than or equal.
;; Now recursively sort the two lists, and put everything together, with the
;; pivot falling in-between the two. The code looks weird at first, but is
;; really a direct translation from the description (base case: empty list).

(define (qsort l)
  (if (null? l)
      l
      (let ((pivot (car l)))
	(let ((rest (cdr l)))
	  (let ((smalls (filter (lambda (x) (<= x first)) rest)))
	    (let ((bigs (filter (lambda (x) (> x first)) rest)))
	      (let ((sorted-smalls (qsort small)))
		(let ((sorted-bigs (qsort big)))
		  (append sorted-smalls
			  (list first)
			  sorted-bigs)))))))))

;; Extra Credit: Exercise! :-)


;; Vectors

;; Here, the helper procedures do the same job as the main procedure,
;; except they start at position i in the vector (and not at the beginning).
;; The main procedure then starts up the helper with position 0.
;; (The strange (+ i 1)'s in the code are because the positions start with 0).

(define (max-vector v)
  (define (max-vector-from-ith v i)
    (if (= (+ i 1) (vector-length v))
	(vector-ref v i)
	(max (vector-ref v i) (max-vector-from-ith (v (+ i 1))))))
  (max-vector-from-ith v 0))

(define (vector->list v)
  (define (vector->list-from-ith v i)
    (if (= (+ i 1) (vector-length v))
	(list (vector-ref v i))
	(cons (vector-ref v i) (vector->list-from-ith v (+ i 1)))))
  (vector->list-from-ith v 0))