;; Solutions for Midterm 1
;; CS 61A: Spring 1998

;; -----------------------
;; QUESTION 1 & 2 versions ABC
;; (in order)

;; Q1:
;; error
;; 20
;; (hip1 hip2 hip3 hurrah)
;; 21
;; error
;; error
;; 5

;; Q2:
;; F
;; F
;; T
;; F
;; F

;; -----------------------
;; QUESTION 1 & 2  versions XYZ

;; 1a. (1 point)
;; ERROR: Invalid argument to WORD:  (+ 2 3)

;; 1b. (1 point)
;; 20

;; 1c. (1 point) (I was case insensitive.)
;; (HIP1 HIP2 HIP3 HURRAH)

;; 1d. (1 point)
;; 21

;; 1e. (1 point)
;; ERROR: unbound variable:  a

;; 1f. (1 point)
;; 25

;; 1g. (1 point)
;; 6

;; ----
;; 2a. (1 point)
;; False

;; 2b. (1 point)
;; False

;; 2c. (1 point)
;; False

;; 2d. (1 point)
;; False

;; 2e. (1 point)
;; True

;; ----------------------------------
;; QUESTION 3 versions ABC   5 points
;; There were basically 2 ways to do this problem: one good,
;; one not-so-good.  The best, most straight-forward way of
;; doing this problem was in the following recursive manner:

(define (subsequence f sen)
	(if	(empty? sen)
		'()
		(se (f sen) (subsequence f (bf sen)))))

;; But because of the unique nature of the sentence function,
;; this iterative solution was also OK:

(define (subsequence f sen)
	(define (iter sen result)
		(if	(empty? sen)
			result
			(iter	(bf sen)
				(se result (f sen)))))
	(iter sen '()))


;; This takes advantage of se's unusual property that
;; (se '() 5) gives (5), and (se '(5 6) 7) gives
;; (5 6 7), etc.  Once you get used to cons, car, cdr, etc.,
;; you'll notice that they won't do this like se does.

;; Most other correct answers were merely convoluted variations
;; on the above.

;; Some common errors:

;; Using (apply f sen) instead of (f sen): -2
;; Wrong base case (it's not zero!!): -1
;; Poor syntax, grossly incorrect parens, extra lambda: -1
;; No recursive call, but hints at it: -2
;; No recursive call, and has no clue: -5
;; Incorrect args passed to subsequence: -2
;; Incorrect algorithm, with shades of correctness: -2
;; Incorrect algorithm, with no clue: -5

;; ----------------------------------
;; QUESTION 3 versions XYZ   5 points
;; Count down to zero version.
(define (li-nth n lst)
  (cond ((empty? lst) '())
	((= n 0) (first lst))
	(else
	 (li-nth (- n 1) (bf lst)))))

;; Count up to n version.
(define (li-nth n lst)
  (define (li-nth-helper count lst)
    (cond ((empty? lst) '())
	  ((= count n) (first lst))
	  (else
	   (li-nth-helper (+ count 1) (bf lst)))))
  (li-nth-helper 0 lst))

;; -1 if your base cases were out of order
;; -2 missing base case
;; -3 made the solutions a linearly recursive process rather
;;    than a linearly iterative process
;; -4 you had a base case and some sense of recursion

;; ------------------------
;; QUESTION 4 versions ABC   

;; 4A.  Yes, this is a function.  The let statement creates a variable "a"
;; that supercedes the "a" value (+ 54 x) received by the lambda statement.
;; (random a) returns a random integer in the range [0, a-1].  Since "a" has
;; been bound to 1, we have the range of [0, 0], so (random a) always returns
;; 0.  Given an input, a function always returns one specific output.  Our
;; program always returns 0 for any input, so we meet this criterion.

;; -----------------------
;; QUESTION 4 versions XYZ

;; 4Z.  No, this is not a function.  In this case, we do use the (+ 54 x)
;; passed into the lambda, so (random a) returns a value in the interval of
;; [0, x+53] at random.  Therefore, given an input of anything other than
;; -53 (or possibly less), we have nondeterministic output; this is not
;; functional behavior.

;; ------------------------------------------
;; QUESTION 5  (ALL TESTS W/ MINOR VARIATION)
;;  ........... polynomial question
;; ADDPOLYS:  This is approximately what people had.
;; If yours is much longer, figure out why you did unnecessary things.
;; If you used helper functions, wrote iterative versions, or computed
;;                               ^^^^^^^^^^^^^^^^^^^^^^^^                  
;; the length of p1 or p2, you were wasting your time and probably
;; computed it wrong.  You use helper functions when you NEED HELP, not
;; just for fun!

;; you got partial credit if you got parts of this right.  critical
;; parts: testing for empty, adding first terms and recursion. 4 pts max.

(define (add-polys p1 p2)
  (cond ((empty? p1) p2)
        ((empty? p2) p1)
        (else (sentence (+ (first p1) (first p2))
       		        (add-polys (bf p1) (bf p2))))))

;; a slight shorter, clever version
 
(define (add-polys p1 p2)
  (if (or (empty? p1) (empty? p2))
      (se p1 p2)  ;; why does this work?
      (sentence (+ (first p1) (first p2)) (add-polys (bf p1) (bf p2)))))
 
;; a really correct version, few people got.. 'cause  (0 0 0) is illegal. it
;; should be ()  for the zero polynomial.
;; There are various ways of doing this, but here is one.
;; (if you don't follow this, try adding x+1  to -x-1 .  )
 
(define (add-polys-better  p1 p2)
  (drop-leading-zeros (add-polys p1 p2)))
 
(define (drop-leading-zeros p)
 (cond ((empty? p) '())
       ((equal? (first p) 0) (drop-leading-zeros (bf p)))
       (else p)))
 
;; multiplication this is the kind of answer we expected...
;; 5 pts max
 
(define (term-multiply-poly p1 coef expon)
  (shift-by expon (tm1 p1 coef)))
 
(define (shift-by expon p)
  (if (equal? expon 0) p(sentence 0 (shift-by (1- expon) p))))
 
(define (tm1 p c)(if (empty? p)'()
		     (sentence (* (first p) c)(tm1 (bf p) c))))

;;;ALTERNATIVES

;; some people did 

(define (term-multiply-poly p1 coef expon)
  (tm1 (shift-by expon p1) coef))
;; which gets the same answer, but slower  (why?)

;;some people did
 
(define (term-multiply-poly p1 coef expon)
  (cond ((equal? 0 expon) (tm1 p c))
	(else (sentence 0 (term-multiply-poly p1 coef (1- expon))))))

;; some people used as many as 4 helper functions.  You should NOT
;; introduce "counters" or extra variables unless you need them.
;; Pascal programmers are sometimes told to  do stuff like
;; setting up a variable and setting it to a parameter, and not
;; changing the value of a parameter. Whatever slight justification
;; this might have in Pascal, it is NOT something to do in scheme.
 
;; Extra and not required:: you can multiply two polynomials this way.
;; we didn't ask, but considering how many people got this
;; right up to here, we might have gotten many good solutions.

(define (mult-poly p1 p2)
  (mp1 p1 p2 0 '(0)))

(define (mp1 p1 p2 deg sofar)
  (cond ((empty? p2) sofar)
	(else (mp1 p1 (bf p2) (1+ deg)
		 (add-polys sofar (term-multiply-poly p1 (first p2) deg))))))


;; ----------------------------------
;; QUESITON 6 versions ABC   6 points

;; The most common (correct) answer was the following:

(define (interleave s1 s2)
  (cond ((and (null? s1) (null? s2)) '())
	((null? s1)
	 (se 0 (first s2) (interleave '() (bf s2))))
	((null? s2)
	 (se (first s1) 0 (interleave (bf s1) '())))
	(else
	 (se (first s1) (first s2) (interleave (bf s1) (bf s2))))))

;; The idea used by the above definition is:
;; If s1 or s2 have atleast one element each (the final case in the
;; cond), make a sentence of the first elements of s1 & s2 followed by
;; the interleave of the rest of s1 & s2.

;; There were several variations of this solution which differed in the
;; way the second & third clauses in the 'cond' were handled. The one
;; that was particularly interesting is the following:

(define (interleave s1 s2)
  (cond ((and (null? s1) (null? s2)) '())
	((null? s1)
	 (interleave '(0) (bf s2)))
	((null? s2)
	 (interleave (bf s1) '(0)))
	(else
	 (se (first s1) (first s2) (interleave (bf s1) (bf s2))))))

;; This I felt was elegant since it handled the special cases in terms
;; of a different recursive call.

;; Some students also gave a variation os this solution with an
;; iterative helper function.

;; There were a class of solutions which looked like the following:

(define (interleave s1 s2)
  (interleave-helper s1 s2 #t))

(define (interleave-helper s1 s2 toggle)
  (cond ((and (null? s1) (null? s2))
	 '())
	(toggle
	 (if (null? s1)
	     (se 0 (interleave-helper '() s2 #f))
	     (se (first s1) (interleave-helper (bf s1) s2 #f))))
	(else
	 (if (null? s2)
	     (se 0 (interleave-helper s1 '() #t))
	     (se (first s2) (interleave-helper s1 (bf s2) #t))))))

;; The idea here is to pull out elements of s1 & s2 in alternate
;; order. However, there is a slight bug in the above solution. Can you
;; find it? Here is the fixed version.

(define (interleave s1 s2)
  (interleave-helper s1 s2 #t))

(define (interleave-helper s1 s2 toggle)
  (cond (toggle
	 (if (and (null? s1) (null? s2))
	     '()
	     (if (null? s1)
		 (se 0 (interleave-helper '() s2 #f))
		 (se (first s1) (interleave-helper (bf s1) s2 #f)))))
	(else
	 (if (null? s2)
	     (se 0 (interleave-helper s1 '() #t))
	     (se (first s2) (interleave-helper s1 (bf s2) #t))))))

;; Grading scheme

;; 6: Any fully correct solution gets a 6. You get the following number
;;    of points taken off for the corresponding errors listed below.

;; -1 Solutions with subtle bugs like the one above get a 5. Some
;;    students used car/cdr/append instead of first/bf/se which is
;;    strictly a data abstraction violation. But no points were taken off
;;    for this (since data abstraction had not yet been taught) - but only
;;    if the solution worked.

;; -2 if the solutions tried to take the first or bf of an empty
;;    sentence.

;; -4 if there is no base case in the solution

;; -4 if the special cases are not considered. i.e. the solution works
;;    only if the two sentences are of equal length.

;; -5 if the solution has no base case & no special case handling.

;; -6 if you had misunderstood the question.

;; -----------------------
;; QUESTION 6 versions XYZ

;; For question 6XYZ, it's exactly the same, except that the sentences were
;; interleaved in the reverse order (first element from the second sentence,
;; then the first element from the first sentence, etc...)

;; -----------------------
;; QUESTION 7 versions ABC


(define (decapitate f)
	(lambda (x) (butfirst (f x))))


(define (decapitate-and-keep-head f)
	(lambda (x) (first (f x))))

;; We took off points for
;; -5	No lambda

;; -5   For an answer that works just for the example in the question.

;; -2	Giving the lambda the wrong parameters
;;	Having the first/butfirst outside of the lambda
;;	Possible cheating (as in having the first/butfirst that did not
;;		belong with your test)
;;	Invoking the lambda

;; -1	Wrong number of left parentheses
;;	Other minor errors