lab9-solutions.rkt

; C211 Lab 9

; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 1 Design a function farthest which accepts a posn
; and list of posn and uses either foldl or foldr to find the
; posn farthest from the given posn. You should use local to
; define a local helper function.
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *


; distance : Posn Posn -> Number
; euclidean distance between p1 and p2
(define (distance p1 p2)
  (local [(define x1 (posn-x p1))
          (define y1 (posn-y p1))
          (define x2 (posn-x p2))
          (define y2 (posn-y p2))]
    (sqrt (+ (sqr (- x2 x1))
             (sqr (- y2 y1))))))

(check-expect (distance (make-posn 0 3) (make-posn 4 0)) 5)
(check-within (distance (make-posn 0 1) (make-posn 1 0)) (sqrt 2) .001)

; farthest : Posn [NEListof Posn] -> Posn
; return the most Posn in ps most distant from p
; NOTE: I changed the problem to require a non-empty
; list since, IMHO, there isn't a sensible answer
; for when 'ps' is empty
(define (farthest p ps)
  ; farther-posn : Posn Posn -> Posn
  ; returns whichever posn (p1 or p2)
  ; is farther away from p
  (local [(define (farther-posn p1 p2)
            (if (< (distance p p1)
                   (distance p p2))
                p2
                p1))]
    (foldl farther-posn
           (first ps)
           (rest ps))))

(check-expect (farthest (make-posn 0 0)
                        (list (make-posn 1 1)))
              (make-posn 1 1))
(check-expect (farthest (make-posn 0 0)
                        (list (make-posn 2 2)
                              (make-posn 3 3)
                              (make-posn 1 1)))
              (make-posn 3 3))


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 2 Write a function count which accepts a list
; of numbers and uses either foldl or foldr to count the
; number of items in the list. You may NOT use the built
; in length function in this exercise. You will have to
; write an auxiliary function, which is given to the
; foldl or foldr function, which will perform the counting.
;
; Test the function with a few lists of numbers.
;
; Now abstract this function to work with a list of any
; data type.
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; count : [Listof X] -> Number
; how many X are in xs
(define (count xs)
  (foldl (λ (x count) (add1 count)) 0 xs))

(check-expect (count empty) 0)
(check-expect (count (list 1 2 3)) 3)
(check-expect (count (list "1" "2" "3")) 3)


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 3: Write a function sometimes-hello which randomly
; says hello to some of the people whose names appear in the
; input list of strings but not to others. Use map.
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; maybe-hello : String -> String
; might say hello to name, might not
(define (maybe-hello name)
  (if (zero? (random 2))
      (string-append "Hello, " name)
      name))

; sometimes-hello : [Listof String] -> [Listof String]
; appends "Hello, " to some strings in names
(define (sometimes-hello names)
  (map maybe-hello names))

(check-expect (sometimes-hello empty) empty)
(check-random (sometimes-hello (list "Larry"
                                     "Curly"
                                     "Moe"
                                     "Shemp"))
              (list (maybe-hello "Larry")
                    (maybe-hello "Curly")
                    (maybe-hello "Moe")
                    (maybe-hello "Shemp")))



; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 4: Design function evens-first of one argument, a
; natural number, that returns the list of the first that many
; even numbers starting with 0.
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; evens-first : Natural -> [Listof Even]
; list of first n even naturals
(define (evens-first n)
  (build-list n (λ (x) (* 2 x))))

(check-expect (evens-first 0) empty)
(check-expect (evens-first 1) (list 0))
(check-expect (evens-first 3) (list 0 2 4))

; evens*-first : Natural -> [Listof Even]
; list of first n odd naturals
(define (odds-first n)
  (map add1 (evens-first n)))

(check-expect (odds-first 0) empty)
(check-expect (odds-first 1) (list 1))
(check-expect (odds-first 3) (list 1 3 5))

; evens*-first : Natural -> [Listof Even]
; list of first n even positive integers
(define (evens*-first n)
  (map add1 (odds-first n)))

(check-expect (evens*-first 0) empty)
(check-expect (evens*-first 1) (list 2))
(check-expect (evens*-first 3) (list 2 4 6))

; Obviously we could also define the above each with
; their own appropriate lambda given to build-list.
; (e.g. odds-first could use (λ (x) (add1 (* 2 x))),
;       evens*-first could use (λ (x) (* 2 (add1 x)))))
; I used map instead just for fun =)


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 5: Design a function powers-of-ten of one argument,
; a natural number, that produces the powers of 10 in descending
; order by one, starting from exponent 0 (zero).
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; powers-of-ten : Natural -> [Listof Number]
; return powers of 10 in a list of length n
(define (powers-of-ten n)
  (build-list n (λ (x) (/ 1 (expt 10 x)))))

(check-expect (powers-of-ten 0) empty)
(check-expect (powers-of-ten 5)
              (list 1 0.1 0.01 0.001 0.0001))
(check-expect (powers-of-ten 10)
              (list 1 0.1 0.01 0.001
                    0.0001 0.00001 0.000001 0.0000001
                    0.00000001 0.000000001))


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 6: Design a function diagonal that receives one
; argument, a number, and returns a list of that many lists
; of 0 and 1 in a diagonal arrangement.
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; diagonal : Natural -> [Listof [Listof Number]]
(define (diagonal n)
  (build-list n (λ (row) (build-list n (λ (col) (if (= col row) 1 0))))))

(check-expect (diagonal 0) empty)
(check-expect (diagonal 1) (list (list 1)))
(check-expect (diagonal 10)
              (list
               (list 1 0 0 0 0 0 0 0 0 0)
               (list 0 1 0 0 0 0 0 0 0 0)
               (list 0 0 1 0 0 0 0 0 0 0)
               (list 0 0 0 1 0 0 0 0 0 0)
               (list 0 0 0 0 1 0 0 0 0 0)
               (list 0 0 0 0 0 1 0 0 0 0)
               (list 0 0 0 0 0 0 1 0 0 0)
               (list 0 0 0 0 0 0 0 1 0 0)
               (list 0 0 0 0 0 0 0 0 1 0)
               (list 0 0 0 0 0 0 0 0 0 1)))


; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
; Exercise 7: design a function random-between with
; the following signature and purpose statement:
; * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

; random-between: Number Number Number -> [ListOf Number]
; generates list of how-many numbers randomly chosen
; between low and high
(define (random-between low high how-many)
  (build-list how-many (λ (_) (+ low (random (- high low))))))

(check-expect (random-between 10 20 0) empty)
(check-random (random-between -100 100 10)
              (list (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))
                    (+ -100 (random 200))))