exam4-rubric.rkt

;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname exam-solns) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
;; 23:11

; Problem 1

; A SplitTree is one of:
;  - Number
;  - (make-no-points)
;  - (make-split Number SplitTree SplitTree)
(define-struct no-points ())
(define-struct split (middle left right))
(define st1
  (make-split 5 (make-split 1.5 1 (make-split 2.5 2 3)) 10))

(define st2 (make-split 2.5
                        (make-split 0
                                    (make-no-points)
                                    (make-split 1.5 1 2))
                        (make-split 5 3 10)))

; [2 points]
(define st3 (make-split 50 (make-split 6
                                       (make-split 0 -1 5)
                                       10)
                        100))
(define st4 (make-split 50
                        (make-split 2 -1
                                    (make-split 8 5 10))
                        100))

; [1 pt header]
; [1 pt template]
; [1 pt examples]
; [1 pt correct]
; count-points : SplitTree -> Number
; count how many points
(define (count-points st)
  (cond [(number? st) 1]
        [(no-points? st) 0]
        [else (+ (count-points (split-left st))
                 (count-points (split-right st)))]))
(check-expect (count-points 2) 1)
(check-expect (count-points (make-no-points)) 0)
(check-expect (count-points st1) 4)
(check-expect (count-points st4) 4)


; add-point: SplitTree Number -> SplitTree
; add the given number to the tree
(define (add-point st n)
  (cond [(number? st) (make-split (min st n) (avg st n) (max st n))]
        [(no-points? st) n]
        [else (make-split (avg n (split-middle st)) st n)]))

; avg: Number Number -> Number
; the point between the numbers
(define (avg n1 n2)
  (+ (min n1 n2) (/ (abs (- n1 n2)) 2)))



; closest: SplitTree Number -> Maybe[Number]
; find the closest number in the tree to the given number, or false if
; the tree is empty
(define (closest st n)
  (cond [(no-points? st) false]
        [(number? st) st]
        [else (cond [(<= n (split-middle st))
                     (closest (split-left st) n)]
                    [else (closest (split-right st) n)])]))

; closer : Number Maybe[Number] Maybe[Number] -> Maybe[Number]
; the closer of a and b to n
(define (closer n a b)
  (cond [(false? b) a]
        [(false? a) b]
        [(< (abs (- n a)) (abs (- n b))) a]
        [else b]))
(check-expect (closer 5 4 10) 4)
(check-expect (closer 9 4 10) 10)
; [2 points for correct tests]
(check-expect (add-point (make-split 1 0 2) 5) (make-split 3 (make-split 1 0 2) 5))
(check-expect (add-point (make-split 1 0 2) 15) (make-split 8 (make-split 1 0 2) 15))
;; the bad example
; [2 points for a bad example]
(check-expect (add-point-fixed (make-split 1 0 3) 2) (make-split 1 0 (make-split 2.5 2 3)))


; [1 points header]
; [1 point template]
; [1 points compares n with midpoint]
; [1 point recurs on the correct side]
; [2 points correctness]
; [It's ok if they just change `add-point` to be fixed]
(define (add-point-fixed st n)
  (cond [(number? st) (make-split (min st n) (avg st n) (max st n))]
        [(no-points? st) n]
        [(< n (split-middle st))
         (make-split (split-middle st) (add-point (split-left st) n) (split-right st))]
        [else
         (make-split (split-middle st) (split-left st) (add-point (split-right st) n))]))


; 23:22

; [1 point signature/purpose]
; [2 points examples]
; [1 point termination statment explains why it gets smaller]
; [1 point termination statement explains why it stops]
; subdivide : [Listof Number] -> [Listof [Listof Number]]
; split the list into groups of equal numbers
; termination: remove-= always removes at least the first element, so
; the resulting list is always at least one shorter. when it gets to empty it stops
(define (subdivide l)
  (cond [(empty? l) empty]
        [else (cons (take-= l (first l))
                    (subdivide (remove-= l (first l))))]))
(check-expect (subdivide empty) empty)
(check-expect (subdivide (list 1 2 2 3)) (list (list 1) (list 2 2) (list 3)))

; take-= : [Listof Number] Number -> Number
; produce the prefix that is = to n
(define (take-= l n)
  (cond [(empty? l) empty]
        [(= (first l) n) (cons (first l) (take-= (rest l) n))]
        [else empty]))
(check-expect (take-= (list 1 1 1 2 3) 1) (list 1 1 1))

; remove-= : [Listof Number] Number -> Number
; remove the prefix that is = to n
(define (remove-= l n)
  (cond [(empty? l) empty]
        [(= (first l) n) (remove-= (rest l) n)]
        [else l]))
(check-expect (remove-= (list 1 1 1 2 3) 1) (list 2 3))


; [1 point signature/purpose]
; [2 points examples, must include interesting accum]
; [1 point sensible accumulator statment for sum]
; [1 point sensible accumulator statment for count]
; more-even/a : [Listof Number] Number Number -> Boolean
; determine if there are more evens than odds in the list
; evens: how many even numbers have been seen
; odds: how many odd numbers have been seen
(define (more-even/a l evens odds)
  (cond [(empty? l) (> evens odds)]
        [(even? (first l))
         (more-even/a (rest l)
                      (+ evens 1)
                      odds)]
        [else (more-even/a (rest l)
                           evens
                           (+ odds 1))]))
(check-expect (more-even/a (list 1 2) 0 0) false)
(check-expect (more-even/a (list 1 2) 5 0) true)
(check-expect (more-even/a (list 1 2) 5 6) false)

(define (more-evens l)
  (more-evens/a l 0 0))


; 23:28

; [1 point signature/purpose]
; [2 points examples]
; [1 point follows NEListof template]
; [1 point comparison between calls to log]
; [1 point correctness]
; smallest-log : [NEListof Number] -> Number
; find the element with the smallest log
(define (smallest-log l)
  (cond [(empty? (rest l)) (first l)]
        [else (if (< (log (first l))
                     (log (smallest-log (rest l))))
                  (first l)
                  (smallest-log (rest l)))]))
(check-expect (smallest-log (list 1)) 1)
(check-expect (smallest-log (list 1 3)) 1)
(check-expect (smallest-log (list  2 1)) 1)
(check-expect (smallest-log2 (list 1)) 1)
(check-expect (smallest-log2 (list 1 2)) 1)
(check-expect (smallest-log2 (list  3 1)) 1)

; color-dist : Color Color -> Number
(define (color-dist c1 c2)
  (+ (- (color-green c1) (color-green c2))
     (- (color-blue c1) (color-blue c2))
     (- (color-red c1) (color-red c2))))
(check-expect (color-dist (make-color 1 1 1)
                          (make-color 0 0 0))
              3)

; [1 point signature/purpose]
; [2 points examples]
; [1 point follows NEListof template]
; [1 point comparison between calls to color-dist]
; [1 point correctness]
; similar: [NEListof Color] Color -> Color
; find the color closest to the given color
(define (similar-color l c)
  (cond [(empty? (rest l)) (first l)]
        [else (if (< (color-dist (first l) c)
                     (color-dist (similar-color (rest l) c) c))
                  (first l)
                  (similar-color (rest l) c))]))


; [1 point signature with function in it]
; [1 point signature correct]
; [1 point follows the previous functions]
; [1 point calls the provided function]
; [2 point correctness]
; minimize : [X] [X -> Number] [NEListof X] -> X
; find the element of the list that minimize f
(define (maximize f l)
  (cond [(empty? (rest l)) (first l)]
        [else (local [(define d (minimize  f (rest l)))]
                (if (< (f (first l))
                       (f d))
                  (first l)
                  (minimize  f (rest l))))])
  #;
  (minimize/a f (rest l) (first l))
  #;
  (cond [(empty? (rest l)) (first l)]
        [else (if (< (f (first l))
                     (f (minimize  f (rest l))))
                  (first l)
                  (minimize f (rest l)))]))


(define (minimize/a f l least)
  (cond [(empty? l) least]
        [else (minimize/a f (rest l)
                          (if (> (f (first l))
                                 (f least))
                              (first l)
                              least))]))

; [2 points slow example]
; [1 point uses local correctly]
; or
; [2 points slow example]
; [1 point uses an accumulator or a helper function and recurs only once]
(time (minimize add1 (build-list 50 add1)))

; [1 point uses color-dist]
; [1 point correctness]
(define (similar-color2 l p)
  (minimize (lambda (p2) (color-dist p p2)) l))
; [1 point correctness]
(define (smallest-log2 l)
  (minimize log l))

; [1 point copies examples]

; 23:41


; A Expression is one of
; - (make-add Expression Expression)
; - (make-multiply Expression Expression)
; - Number
; - (make-read-write Expression)
(define-struct add (left right))
(define-struct multiply (left right))
(define-struct read-write (expr))

; [1 point purpose/signature]
; [1 point examples]
; [1 point template with correct recursion]
; [1 point correctness]
; evaluate : Expression -> Number
; evaluate the expression
(define (evaluate e)
  (posn-x (evaluate/a e 0))
  #;
  (cond [(add? e) (+ (evaluate (add-left e))
                     (evaluate (add-right e)))]
        [(multiply? e) (* (evaluate (multiply-left e))
                          (evaluate (multiply-right e)))]
        [(number? e) e]))


; [6 points, assign as you see fit]
(define (evaluate/a e state)
  (cond [(number? e) (make-posn e state)]
        [(read-write? e)
         (local [(define a
                   (evaluate/a (read-write-expr e) state))]
           (make-posn state (posn-x a)))]
        [(add? e)
         (local [(define a
                   (evaluate/a (add-left e) state))
                 (define b
                   (evaluate/a (add-right e) (posn-y a)))]
           (make-posn (+ (posn-x a)
                         (posn-x b))
                      (posn-y b)))]
        [(multiply? e)
         (local [(define a
                   (evaluate/a (multiply-left e) state))
                 (define b
                   (evaluate/a (multiply-right e) (posn-y a)))]
           (make-posn (* (posn-x a)
                         (posn-x b))
                      (posn-y b)))]))

(check-expect (evaluate 1) 1)
(check-expect (evaluate (make-add (make-multiply 2 3) 5)) 11)

(check-expect (evaluate (make-read-write 5)) 0)
(check-expect (evaluate (make-add (make-read-write 5)
                                  (make-read-write 6)))
              5)

; 23:54