;; file:  hw2pr1.rkt
;; submission site id/login:
;; time spent:
;; other comments?

#lang racket
(require htdp/testing)
(require racket/trace)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; superreverse (be sure to finish this comment - and the others!)
;;   inputs:
;;   output:
;; using higher-order functions (no raw recursion)
(define (superreverse L)
  0)

; provided tests
(check-expect (superreverse '( (1 2 3) (4 5 6) (#\k #\o #\o #\l) (#\a #\m) ))
    '( (3 2 1) (6 5 4) (#\l #\o #\o #\k) (#\m #\a) ) )
(check-expect (superreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
    '( (3 2 1) (9 (7 8) 6 5 4) ) )

; additional tests

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 2
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; using higher-order functions (no raw recursion)
(define (indivisible e L)
  0)

; provided tests
(check-expect (indivisible 3 '( 2 3 4 5 6 7 8 9 10 )) '(2 4 5 7 8 10))

; additional tests

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 3
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; using higher-order functions (no raw recursion)
(define (lotto-winner list-of-tickets winning-numbers)
  0)
  
; provided tests
(check-expect (lotto-winner
    '( (alice 2 4 16 33 42)  (bob 3 4 5 6 7) (cdrthecat 3 15 16 41 42) )
    '(2 3 15 32 42))
              '(cdrthecat 3))

; additional tests

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; BST interface
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; make-BST: BST constructor
;;   inputs: a key, the left sub-BST, and the right sub-BST
;;   output: a new BST, with key as the root
(define (make-BST key left right)
  (list key left right))

;; make-empty-BST: creates an empty BST.
;;   inputs: none
;;   output: an empty BST
(define (make-empty-BST)
  '())

;; make-BST-leaf: creates a BST with one node (aka a leaf).
;;   inputs: a key
;;   output: a new BST, with key as the root
(define (make-BST-leaf key)
      (make-BST key ; key
                (make-empty-BST)   ; left subtree 
                (make-empty-BST))) ; right subtree

;; emptyTree?: checks if a tree is empty
;;   inputs: a BST
;;   outputs: #t if tree is empty; otherwise #f
(define (emptyTree? tree)
  (null? tree))

;; leaf?: - checks if the input is a BST with no children
;;   inputs: a BST
;;   output: #t if tree is a leaf, otherwise #f
(define (leaf? tree)
  (and (null? (leftTree tree))
       (null? (rightTree tree))))
  
;; key: returns the key for the BST
;;   inputs: a BST
;;   output: the key
(define (key  tree)
  (first tree))

;; leftTree: returns the left tree from the BST
;;   inputs: a BST
;;   output: the left subtree
(define (leftTree tree)
  (second tree))

;; rightTree: returns the right tree from the BST
;;   inputs: a BST
;;   output: the right subtree
(define (rightTree tree)
  (third tree))
;; a big binary search tree for testing:
(define BigBST 
  (make-BST 42
            (make-BST 20
                      (make-BST 7
                                (make-BST-leaf 1)
                                (make-BST-leaf 8))
                      (make-BST 31
                                (make-empty-BST)
                                (make-BST-leaf 41)))
            (make-BST 100 
                      (make-BST-leaf 60)
                      (make-empty-BST))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 4
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; define additional BSTs here for testing:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 5
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (height BST)
  0)

; provided tests
(check-expect (height BigBST) 3) ;; using the tree defined above
(check-expect (height (make-empty-BST)) -1)

; additional tests

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 6
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (find-min BST)
  0)

; provided tests
(check-expect (find-min BigBST) 1) ;; using the tree defined above

; additional tests
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 7
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
(define (in-order BST)
  0)

; provided tests
(check-expect (in-order BigBST) '(1 7 8 20 31 41 42 60 100)) ;; using the tree defined above

; additional tests
  
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 8
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (tree-map f BST)
  0)
  
; provided test
(check-expect (tree-map (lambda (x) (+ x 2)) BigBST) 
			  '(44 (22 (9 (3 () ()) (10 () ())) (33 () (43 () ()))) (102 (62 () ()) ())))

; additional tests 
  

  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 9
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (delete e BST)
  0)

; provided tests
(check-expect (delete 20 BigBST)
    '(42
      (31 (7 (1 () ()) (8 () ())) (41 () ()))
      (100 (60 () ()) ())))

(check-expect (delete 42 BigBST)
    '(60
      (20 (7 (1 ()()) (8 ()()))  (31 () (41 () ())))
      (100 ()())))

; additional tests
  
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Problem 10
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (make-change total coin-list)
  0)
           
; provided tests
(check-expect (make-change  0 '(1 4 6 15 25 29 54)) #t)
(check-expect (make-change 29 '(1 4 6 15 25 29 54)) #t)
(check-expect (make-change 11 '(1 4 6 15 25 29 54)) #t)
(check-expect (make-change 76 '(1 4 6 15 25 29 54)) #t)
(check-expect (make-change  9 '(1 4 6 15 25 29 54)) #f)
(check-expect (make-change 77 '(1 4 6 15 25 29 54)) #f)

; additional tests


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; problem 11 uses Java at  CodingBat (http://codingbat.com/)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Extra credit: 20 questions
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(generate-report)