#lang racket
(require csc151)

;;; File:
;;;   exam3.rkt
;;; Authors:
;;;   The student currently referred to as 000000
;;;   Charlie Curtsinger
;;;   Fahmida Hamid
;;; Contents:
;;;   Code and solutions for Exam 3 2018F
;;; Citations:
;;;

;; +-----------+------------------------------------------------------
;; | Problem 1 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   read-dictionary
;;; Parameters:
;;;   filename, a string
;;; Purpose:
;;;   Read a file containing a list of words, one per line
;;; Produces:
;;;   word-list, a list of strings
;;; Preconditions:
;;;   filename must refer to a readable text file with words split over lines
;;; Postconditions:
;;;   Every line of text in the file named filename will appear as a string in word-list
;;;   Every string in word-list appears as a complete line of text in the file named filename
(define read-dictionary
  (lambda (filename)
    null)) ; STUB

;;; Procedure:
;;;   backronym
;;; Parameters:
;;;   str, a string
;;;   dictionary, a list of strings
;;; Purpose:
;;;   Select random items from dictionary that start with each of the characters in str and
;;;   combine them into a single "backronym" string
;;; Produces:
;;;   words, a string
;;; Preconditions:
;;;   str must contain only alphabetic characaters
;;;   dictionary must contain at least one item that begins with every character in str
;;; Postconditions:
;;;   For every character in str, there will be a word in the string words that begins with that
;;;     character (case insensitive).
;;;   Reading the first character of each word in words will match the input string str, ignoring
;;;     any differences in case.
(define backronym
  (lambda (str dictionary)
    "")) ; STUB

; Examples/Tests:
#|

|#

;; +-----------+------------------------------------------------------
;; | Problem 2 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   make-pair-accessor
;;; Parameters:
;;;   name, a ???
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;; 
;;; Postconditions:
;;; 
(define make-pair-accessor
  (lambda (name)
    car)) ; STUB

; Examples/Tests:
#|

|#

;; +-----------+------------------------------------------------------
;; | Problem 3 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;   vmap
;;; Parameters:
;;;   proc, a ???
;;;   vec, a ???
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define vmap
  (lambda (proc vec)
    null)) ; STUB

;;; Procedure:
;;;   vmap!
;;; Parameters:
;;;   proc, a ???
;;;   vec, a ???
;;; Purpose:
;;;   
;;; Produces:
;;;   
;;; Preconditions:
;;;   
;;; Postconditions:
;;;   
(define vmap!
  (lambda (proc vec)
    null)) ; STUB

; Examples/Tests:
#|

|#

;; +-----------+------------------------------------------------------
;; | Problem 4 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:

; Solution:

;;; Procedure:
;;;
;;; Parameters:
;;;
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;
;;; Postconditions:
;;;
(define x (lambda (y z) (apply o (make-list y z))))

; Examples/Tests:
#|

|#

;; +-----------+------------------------------------------------------
;; | Problem 5 |
;; +-----------+

; Time Log:
;   Date        Start   Finish  Elapsed Activity

; Time Spent: 

; Citations:
; Binary tree implementation from CSC 151 lab on binary trees (http://curtsinger.cs.grinnell.edu/teaching/2018F/CSC151/labs/binary-trees.html)

; Provided code

;;; Name:
;;;   empty
;;; Type:
;;;   tree
;;; Value:
;;;   The empty tree
(define empty 'empty)

;;; Procedure:
;;;   leaf
;;; Parameters:
;;;   val, a value
;;; Purpose:
;;;   Make a leaf node.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents tree) = val
;;;   (left tree) = empty
;;;   (right tree) = empty
(define leaf
  (lambda (val)
    (node val empty empty)))

;;; Procedure:
;;;   node
;;; Parameters:
;;;   val, a value
;;;   left-subtree, a tree
;;;   right-subtree, a tree
;;; Purpose:
;;;   Create a node in a binary tree.
;;; Produces:
;;;   tree, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (node? tree) holds.
;;;   (left tree) = left-subtree.
;;;   (right tree) = right-subtree.
;;;   (contents tree) = val.
(define node
  (lambda (val left right)
    (vector 'node val left right)))

;;; Procedure:
;;;   contents
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the contents of node.
;;; Produces:
;;;   val, a value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (contents (node val l r)) = val
(define contents
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "contents requires a node, received" nod)]
      [else
       (vector-ref nod 1)])))

;;; Procedure:
;;;   left
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the left subtree of nod.
;;; Produces:
;;;   l, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (left (node val l r)) = l
(define left
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "left requires a node, received" nod)]
      [else
       (vector-ref nod 2)])))

;;; Procedure:
;;;   right
;;; Parameters:
;;;   nod, a binary tree node
;;; Purpose:
;;;   Extract the right subtree of nod.
;;; Produces:
;;;   r, a tree
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (right (node val l r)) = r
(define right
  (lambda (nod)
    (cond
      [(not (node? nod))
       (error "right requires a node, received" nod)]
      [else
       (vector-ref nod 3)])))

;;; Procedure:
;;;   empty?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val represents an empty tree.
;;; Produces:
;;;   is-empty?, a Boolean 
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   is-empty? is true (#t) if and only if val can be interpreted as
;;;   the empty tree.
(define empty? 
 (section eq? <> empty))

;;; Procedure:
;;;   leaf?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val is a tree leaf
;;; Produces:
;;;   is-leaf?, a Boolean
(define leaf?
 (lambda (val)
   (and (node? val)
        (empty? (left val))
        (empty? (right val)))))

;;; Procedure:
;;;   node?
;;; Parameters:
;;;   val, a Scheme value
;;; Purpose:
;;;   Determine if val can be used as a tree node.
;;; Produces:
;;;   is-node?, a Boolean
(define node?
 (lambda (val)
   (and (vector? val)
        (= (vector-length val) 4)
        (eq? (vector-ref val 0) 'node))))

; Solution:

;;; Procedure:
;;;   bst-insert
;;; Parameters:
;;;   tree, a binary search tree
;;;   val, a real number
;;; Purpose:
;;;   Produce a new binary search tree with val added to the input tree
;;; Produces:
;;;   new-tree, a binary search tree
;;; Preconditions:
;;;   tree must be a tree node that implements a binary search tree.
;;;   A binary search tree (BST) is either empty, or a tree node.
;;;   The contents of this node must be greater than all values in the left subtree
;;;   and less than or equal to all values in the right subtree. Both the left and
;;;   right subtrees must also be binary search trees.
;;; Postconditions:
;;;   new-tree must be a BST.
;;;   new-tree must have one additional node with contents equal to val.
(define bst-insert
  (lambda (tree val)
      empty)) ; STUB

; Examples/Tests:
#|

|#