;; 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 review2) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
;; Fundies 1 Exam 2 Review
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; 2009 Q.7
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; (foldr cons '(7) '(1 3 5 7)) => (cons 1 (cons 3 (cons 5 (cons 7 '(7)))))

;; snoc: X [Listof X] -> [Listof X]
;; adds an element to the end of the list
;; Examples: (snoc 7 '(1 3 5)) => '(1 3 5 7)
;; (snoc 7 empty) => (list 7)
(define (snocs el lst)
  (foldr cons (list el) lst))

(check-expect (snocs 7 empty) (list 7))
(check-expect (snocs 7 '(1 3 5)) '(1 3 5 7))


;; 2009 Q.6
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(define-struct node (left right))
;; A [BT X] is one of:
;; - an X
;; - (make-node [BT X] [BT X])

;; fold-tree: [Y Y -> Y] [X -> Y] [BT X] -> Y
;; folds a tree
(define (fold-tree comb proc bt)
  (cond [(not (node? bt)) (proc bt)]
        [else (comb 
               (fold-tree comb proc (node-left bt))
               (fold-tree comb proc (node-right bt)))]))

;; height: [BT X] -> Number
;; produces the height of the given tree
;; Examples: (height 5) => 0
;; (height (make-node 1 2)) => 1
;; (height (make-node (make-node 2 5) 5)) => 2
;; (height (make-node (make-node 2 5) (make-node 42 5))) => 2
(define (height bt)
  (fold-tree (lambda (x y) (add1 (max x y)))
             (lambda (_) 0)
             bt))

(check-expect (height 5) 0)
(check-expect (height (make-node 1 2)) 1)
(check-expect (height (make-node (make-node 2 5) 5)) 2)
(check-expect (height (make-node (make-node 2 5) (make-node 42 5))) 2)


;; 2009 Q. 8
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A NumTree is a [BT Number]

;; same-shape?: [BT Number] [BT Number] -> Boolean
;; do the two trees have the same shape?
;; Examples: (same-shape? 3 4) => true
;; (same-shape? (make-node 3 4) (make-node 5 6)) => true
;; (same-shape? (make-node (make-node 4 2) 4)
;;              (make-node 5 (make-node 4 2))) => false
;; (same-shape? (make-node (make-node 4 2) 4)
;;              (make-node (make-node 4 2) 5)) => true
(define (same-shape? bt1 bt2)
  (cond [(and (not (node? bt1)) (not (node? bt2))) true]
        [(and (node? bt1) (node? bt2))
         (and (same-shape? (node-left bt1)
                           (node-left bt2))
              (same-shape? (node-right bt1)
                           (node-right bt2)))]     
        [else false]))

(check-expect (same-shape? 3 4) true)
(check-expect (same-shape? (make-node 3 4) (make-node 5 6)) true)
(check-expect (same-shape? (make-node (make-node 4 2) 4)
                           (make-node 5 (make-node 4 2))) false)
(check-expect (same-shape? (make-node (make-node 4 2) 4)
                           (make-node (make-node 4 2) 5)) true)

;; 2009 Q. 1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; cons: X [Listof X] -> [Listof X]
;; (cons [Listof Number] [Listof [Listof Number]] -> [Listof [Listof Number]]
(define a '(1 2))
(define b '((3 4) (5 6)))

(check-expect (append a b) '(1 2 (3 4) (5 6)))
(check-expect (list a b) '(( 1 2) ((3 4) (5 6))))
(check-expect (cons a b) '((1 2) (3 4) (5 6)))
(check-expect (apply append a b) '(1 2 3 4 5 6))

;; 2009 Q. 3
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; andmap2500: [X -> boolean] [Listof X] -> boolean
;; does the procedure hold true for all the elements in the list
;; Examples: (andmap2500 positive? '(1)) => true
;; (andmap2500 positive? empty) => true
;; (andmap2500 positive? '(1 3 523 -1)) => false
(define (andmap2500 proc lst)
  (cond [(empty? lst) true]
        [else (and (proc (first lst))
                   (andmap2500 proc (rest lst)))]))

(check-expect (andmap2500 positive? '(1)) true)
(check-expect (andmap2500 positive? empty) true)
(check-expect (andmap2500 positive? '(1 3 523 -1)) false)

;; 2010 Q. 4
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; do-while: [Listof Y] [Y -> Boolean] [Y -> X] -> [Listof X]
(define (do-while ys go what)
  (cond [(empty? ys) empty]
        [(not (go (first ys))) empty]
        [else
         (cons (what (first ys))
               (do-while (rest ys) go what))]))

;; 2010 Q. 3
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; weaver: [Listof X] [Listof X] -> [Listof X]
;; weaves two lists into a single list by alternating elements
(define (weaver lst1 lst2)
  (cond [(empty? lst1) lst2]
        [(empty? lst2) lst1]
        [else (append (list (first lst1) (first lst2))
                      (weaver (rest lst1) (rest lst2)))]))

(check-expect (weaver empty (list 1)) (list 1))
(check-expect (weaver (list "Hi" "Lo") empty) (list "Hi" "Lo"))
(check-expect (weaver (list 1 2) (list 3 4))
              (list 1 3 2 4))
(check-expect (weaver (list 'R 'C 'R) (list 'A 'E))
              (list 'R 'A 'C 'E 'R))

;; 2010 Q. 5
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;my-filter: [X -> Boolean] [Listof X] -> [Listof X]
;; returns a list with all the elements that the procedure returns true for
(define (my-filter pred lst)
  (cond [(empty? lst) empty]
        [(pred (first lst)) (cons (first lst) 
                                  (my-filter pred (rest lst)))]
        [else (my-filter pred (rest lst))]))

(check-expect (my-filter positive? '(1 2 3 -4 7 -3))
              '(1 2 3 7))
(check-expect (my-filter odd? '(1 2 3 4 5))
              '(1 3 5))

;; A [SnocListof X] is one of:
;; - empty
;; - (make-snoc [SnocListof X] X)
(define-struct snoc (front last))

;; snoc-filter: [X -> Boolean] [SnocListof X] -> [SnocListof X]
;; filters a snoc list
(define (snoc-filter pred sn)
  (cond [(empty? sn) empty]
        [(pred (snoc-last sn)) 
         (make-snoc (snoc-filter pred (snoc-front sn)) (snoc-last sn))]
        [else (snoc-filter pred (snoc-front sn))]))

(define slst (make-snoc (make-snoc (make-snoc empty 1) 2) 3))
(check-expect (snoc-filter odd? slst)
              (make-snoc (make-snoc empty 1) 3))
(check-expect (snoc-filter even? slst)
              (make-snoc empty 2))

;; 2009 Q. 2
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;; A [Setof X] is a [Listof X].
;;; Repetitions not allowed


;;; abs=? : Number Number -> Boolean
;;; Do the two numbers have the same absolute value?
(define (abs=? x y) (= (abs x) (abs y)))
(check-expect (abs=? 0 0) true)
(check-expect (abs=? 3 3) true)
(check-expect (abs=? 3 -3) true)
(check-expect (abs=? -3 3) true)
(check-expect (abs=? -3 -3) true)
(check-expect (abs=? 3 0) false)


;; contains?: [Setof X] Y [X Y -> boolean] -> boolean
;; Does the set contain some element?
(define (contains? set el proc)
  (ormap (lambda (x) (proc x el)) set))

(check-expect (contains? '(5 1 7) 1 abs=?) true) ; Should produce true.
(check-expect (contains? '(5 1 7) -1 abs=?) true) ; Should produce true, too.
(check-expect (contains? '(5 1 7) 8 abs=?) false) ; Should not produce true.

;; 2010 Q. 6 Extra Credit
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; A CodeTree is one of
;; - String
;; - (make-node CodeTree CodeTree)
(define-struct bin-node (zero one))

;; decode: Number CodeTree -> String
;; decode the number based on the given CodeTree
(define (decode num tree)
  (cond [(not (bin-node? tree)) tree]
        [(even? num) (decode (floor (/ num 2)) (bin-node-zero tree))]
        [else (decode (floor (/ num 2)) (bin-node-one tree))]))

;; message: [Listof Number] CodeTree -> String
;; decodes the list of numbers based on the code tree
(define (message nums tree)
  (foldr (lambda (x y) 
           (string-append (decode x tree) y))
         "" nums))


(define t-1 (make-bin-node "m" "o"))
(define t-2 (make-bin-node (make-bin-node "w" "t")
                           (make-bin-node "e" "s")))
(check-expect (decode 0 t-1) "m")
(check-expect (decode 0 t-2) "w")
(check-expect (decode 3 t-2) "s")
(check-expect (message '(0 1 0) t-1) "mom")
(check-expect (message '(0 1 1) t-1) "moo")
(check-expect (message '(3 0 1 1 2) t-2) "sweet")
(check-expect (message '(2 0 1 1 2) t-2) "tweet")
(check-expect (message '(0 7 3 1 6 2 0 5)
                       (make-bin-node
                        (make-bin-node "c" (make-bin-node "i" "w"))
                        (make-bin-node (make-bin-node "d" "k")
                                       (make-bin-node "a" "h"))))
              "chadwick")