;; CS61A Summer 2010
;; Midterm 2 - Review Session Solutions

;; We made a correction during the review session:
;; The lists in questions 1 and 2 should be defined with the
;; "list" procedure, not using quotes.  The Scheme standard
;; says that you're not allowed to mutate quoted constants.

;; 1.

+---+---+     +---+---+   +---+---+
| -+| --+---->| | | --+-->| | | | |
+-+|+---+     +-+-+---+   +-+-+-+-+
  x|            v   ^       v   |
  v+-+          b   |       c   |
  a  |          +---+           |
     v          |               v
+---+---+     +-+-+---+   +---+---+
| | | --+---->| | | --+-->| | |   |
+-+-+---+     +-+-+---+   +-+-+---+
  |             x           |
  v             v           v
  1             2           3

((1 (b c 3) 3) b c 3)


;; 2.
;; Original environment diagram:
+---+---+     +---+---+     +---+---+     +---+---+
| | | --+---->| | | --+---->| | | --+---->| | | / |
+-+-+---+     +-+-+---+     +-+-+---+     +-+-+---+
  |             |             |             |
  v             v             v             v
  1             2             3             4


;; Final Environment diagram:
                +---------------------------+
                |                           v
+---+---+     +-+-+---+     +---+---+     +---+---+
| | | --+---->| | | --+---->| | | / +-XX->| | | / |
+-+-+---+  +->+-+-+---+     +-+-+---+     +-+-+---+
  +--------+    x             |             |
  x             v             v             v
  1             2             3             4

(define z (list 1 2 3 4))
(set-car! (cdr z) (cdddr z))

(set-cdr! (cddr z) '()) ;; Missing line

(set-car! z (cdr z))
z -> (((4) 3) (4) 3)


;; 3.
(define-class (smash-character lives)
  (instance-vars (damage 0))
  (method (attack character attack-strength)
    (ask character 'take-damage attack-strength))
  (method (take-damage attack-strength)
    (set! damage (- damage attack-strength))
    (if (>= damage 30)
        (ask self 'lose-life)
        'okay))
  (method (lose-life)
    (if (<= lives 0)
        '(i lost x_x)
        '(i died >_<))))

;; 4.
Class variable: a
Instance variable: c
Instantiation variable: b
Message: g, h
Method: d
Dispatch procedure: f
Method argument: e
Instance: f

;; 5.
;; We recommend using envdraw on the inst machines to determine the
;; answer to this question.
;; To review environment diagrams, check out the rules posted online:
;; http://www-inst.eecs.berkeley.edu/~cs61a/su10/reading/EnvDiagramRules.pdf

;; 6.
(define (link-first! lst)
  (cond ((null? (cdr lst)) lst)
        ((equal? (car lst) (cadr lst))
         (link-first! (cdr lst))
         lst)
        (else (set-cdr! lst (cddr lst))
              (link-first! lst)
              lst)))

;; 7.
In mc-eval:

...
((cases? exp) (eval-cases exp env))
...

(define (eval-cases exp env)
  (let ((variable-value
         (lookup-variable-value (cases-variable exp) env)))
    (define (eval-cases-helper exps) ;; exps is a list!
      (cond ((null? exps) 'okay)
            ((cases-else? (car exps))
             (eval-sequence (cases-actions (car exps)) env))
            ((member? variable-value
                      (map (lambda (exp) (mc-eval exp env))
                           (cases-list-of-choices (car exps))))
             (eval-sequence (cases-actions (car exps)) env))
            (else (eval-cases-helper (cdr exps)))))
    (eval-cases-helper (cases-exps exp))))

(define (cases? exp)
  (tagged-list exp 'cases))
(define (cases-variable exp)
  (cadr exp))
(define (cases-else? exp)
  (tagged-list exp 'else))
(define (cases-exps exp)
  (cddr exp))
(define (cases-actions exp)
  (cdr exp))
(define (cases-list-of-choices exp)
  (car exp))

;; 8.
(define (count v i num)
  (if (< num (vector-length v))
      (if (= i (vector-ref v num))
          (+ 1 (count v i (+ num 1)))
          (count v i (+ num 1)))
      0))

;; Note: vector-remove! is actually a misnomer.
;; You cannot permanently mutate a vector's size.  :-(
;; The procedure should correctly be called "vector-remove".
(define (vector-remove! vec elmtToRemove)
  (let* ((vec-length (vector-length vec))
         (result (make-vector (- vec-length (count vec elmtToRemove 0)))))

    ;; "currLoc" is the current index being observed,
    ;; "insertLoc" is the index of insertion.
    (define (vr-helper currLoc insertLoc)
      (if (>= currLoc vec-length)
          result
          (let ((currElement (vector-ref vec currLoc)))
            (if (equal? currElement elmtToRemove)
                (vr-helper (+ currLoc 1) insertLoc)
                (begin
                  (vector-set! result insertLoc currElement)
                  (vr-helper (+ currLoc 1) (+ insertLoc 1)))))))

    (vr-helper 0 0)))