SHARE
TWEET

Untitled

a guest Mar 26th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (require 2htdp/image)
  2. (require 2htdp/universe)
  3.  
  4. ;;Exercise 1
  5. ; A [Comparator X] is a [X X -> Number] function such that
  6. ; - (f a b) < 0 if a < b
  7. ; - (f a b) = 0 if a = b
  8. ; - (f a b) > 0 if a > b
  9.  
  10. (define COMPARATOR -)
  11.  
  12. (define-struct branch [val left right])
  13. ; A [Tree X] is one of:
  14. ; - "leaf"
  15. ; - (make-branch X [Tree X] [Tree X])
  16. ; and represents a tree that contains data of type X
  17.  
  18. (define TREE-0 "leaf")
  19. (define TREE-1 (make-branch 5 TREE-0 TREE-0))
  20. (define TREE-2 (make-branch 7 TREE-1 TREE-0))
  21. (define TREE-3 (make-branch 3 TREE-0 TREE-2))
  22. (define TREE-4 (make-branch 10 TREE-3 TREE-0))
  23. (define TREE-5 (make-branch 2 TREE-0 TREE-4))
  24.  
  25. ;;tree-template: [X] [Tree X] -> ???
  26. #;(define (tree-template t)
  27.     (cond
  28.       [(string? t)...]
  29.       [(branch? t)...(branch-val t)...
  30.                   ...(tree-template (branch-left t))...
  31.                   ...(tree-template (branch-right t))...]))
  32.  
  33. (define-struct bst [comparator tree])
  34. ; A [BST X] is a (make-bst [Comparator X] [Tree X])
  35. ; and represents a binary search tree that contains data of type X with no repeats
  36. ; For some (make-bst f (make-branch x y z))
  37. ; - x is greater than every element in the tree y according to the comparator f
  38. ; - x is less than every element in the tree z according to the comparator f
  39. ; - y and z are are also ordered according to the comparator
  40. ; Note: (make-branch x "leaf" "leaf") is ordered by any comparator
  41.  
  42. (define BST-0 (make-bst COMPARATOR TREE-0))
  43. (define BST-1 (make-bst COMPARATOR TREE-1))
  44. (define BST-2 (make-bst COMPARATOR TREE-2))
  45. (define BST-3 (make-bst COMPARATOR TREE-3))
  46. (define BST-4 (make-bst COMPARATOR TREE-4))
  47. (define BST-5 (make-bst COMPARATOR TREE-5))
  48.  
  49. ;;Exercise 2
  50. ;;in-bst?: [X] X [BST X] -> Boolean
  51. ;;is the value X in the given binary search tree?
  52. (check-expect (in-bst? 10 BST-5) #true)
  53. (check-expect (in-bst? 3 BST-1) #false)
  54. (check-expect (in-bst? 5 BST-1) #true)
  55. (check-expect (in-bst? 7 BST-0) #false)
  56.  
  57. (define (in-bst? x bst)
  58.   (in-tree? (bst-tree bst) (bst-comparator bst) x))
  59.  
  60. ; in-tree? : [X] [Tree X]  [X X -> Number] X -> Boolean
  61. ; checks if x is in the tree
  62. (check-expect (in-tree? TREE-0 COMPARATOR 0) #false)
  63. (check-expect (in-tree? TREE-4 COMPARATOR 7) #true)
  64. (check-expect (in-tree? TREE-3 COMPARATOR 2) #false)
  65.  
  66. (define (in-tree? tree f x)
  67.   (cond
  68.     [(string? tree) #f]
  69.     [else (or (equal? (f (branch-val tree) x) 0)
  70.               (in-tree? (branch-left tree) f x)
  71.               (in-tree? (branch-right tree) f x))]))
  72.  
  73. ;;Exercise 3
  74. ;;swap-bst: [X] [BST X] -> [BST X]
  75. ;;produces the opposite BST
  76. (check-expect (swap-bst BST-0) (make-bst (swap-comparator (bst-comparator BST-0)) TREE-0))
  77. (check-expect (swap-bst BST-2) (make-bst (swap-comparator (bst-comparator BST-2))
  78.                                          (make-branch 7 TREE-0 TREE-1)))
  79. (check-expect (swap-bst BST-3) (make-bst (swap-comparator (bst-comparator BST-3))
  80.                                          make-branch 3 TREE-2 TREE-0))
  81.  
  82. (define (swap-bst bst)
  83.   (make-bst (swap-comparator (bst-comparator bst)) (swap-tree (bst-tree bst))))
  84.  
  85. ;;swap-tree: [X] [Tree X] -> [Tree X]
  86. ;;swaps the branches of a tree
  87. (check-expect (swap-tree TREE-0) TREE-0)
  88. (check-expect (swap-tree TREE-5) (make-branch 2 TREE-4 TREE-0))
  89.  
  90. (define (swap-tree tree)
  91.   (cond
  92.     [(string? tree) tree]
  93.     [(branch? tree) (make-branch (branch-val tree)
  94.                                  (branch-right tree)
  95.                                  (branch-left tree))]))
  96.  
  97. ;;swap-comparator: [X] [X X -> Number] -> [X X -> Number]
  98. ;;produces the opposite comparator
  99. (check-expect ((swap-comparator -) 4 5) 1)
  100. (check-expect ((swap-comparator -) 10 3) -7)
  101. (check-expect (number? ((swap-comparator -) 3 5)) #true)
  102.  
  103. (define (swap-comparator c)
  104.   (λ (x y) (c y x)))
  105.  
  106. ;;Exercise 4
  107. ;;place-in-bst: [X] [BST X] X -> [BST X]
  108. ;;places the value x in the appropriate branch of the tree if it is not already in the tree
  109.  
  110. #;;(define (place-in-bst bst x)
  111. ;  (cond
  112.  ;   [(in-bst? x bst) bst]
  113.   ;  [else (if ()
  114.    ;           ()
  115.     ;          ())
  116.  
  117.  
  118. ;;Exercise 5
  119. ; An Ending is a (make-ending String Boolean)
  120. (define-struct ending [text good?])
  121. ; and represents an ending to the story with some text and whether it was a happy ever after
  122.  
  123. ;ending-temp: Ending -> ???
  124. #;(define (ending-temp e)
  125.     (...(ending-text e)...(ending-good? e)...))
  126.  
  127. ; An [NEList-of X] (Non-Empty List) is one of:
  128. ; - (cons X '())
  129. ; - (cons X [NEList-of X])
  130.  
  131. ;nelist-temp: [X] [NEList-of X] -> ???
  132. #;(define (nelist-temp nel)
  133.     (cond
  134.       [(empty? (rest nel))...]
  135.       [(cons? (rest nel))...(first nel)...
  136.                          ...(nelist-tempp (rest nel))...]))
  137.  
  138. ; A Choice is a a (make-choice String Section)
  139. (define-struct choice [text result])
  140. ; and represents the blurb shown to the reader and the resulting section if that is the
  141. ; choice they make
  142.  
  143. ;choice-temp: Choice -> ???
  144. #;(define (choice-temp c)
  145.     (...(choice-text c)...(choice-result c)...))
  146.  
  147. ; A Chapter is a (make-chapter String [NEList-of Choice])
  148. (define-struct chapter [text choices])
  149. ; and represents a chapter in a choose-your-own adventure book with a body
  150. ; and a list of choices at the end
  151.  
  152. #;(define (chapter-temp ch)
  153.     (...(chapter-text ch)...(nelist-temp (chapter-choices ch))...))
  154.  
  155. ; A Section is one of:
  156. ; - Ending
  157. ; - Chapter
  158. ; and represents a section in a choose your own adventure book
  159.  
  160. ;section-temp: Section -> ???
  161. #;(define (section-temp s)
  162.     (cond
  163.       [(ending? s)...(ending-temp s)...]
  164.       [(chapter? s)...(chapter-temp s)...]))
  165.  
  166. (define MY-STORY
  167.   (make-chapter
  168.    "You are alone in a room. There is a door before you."
  169.    (list
  170.     (make-choice
  171.      "Stay in the room."
  172.      (make-ending "You stay in the room. Nothing happens. Nothing ever will again." #f))
  173.     (make-choice
  174.      "Open the door."
  175.      (make-chapter
  176.       "You open the door. On the other side lays an eternity of nothingness."
  177.       (list
  178.        (make-choice
  179.         "Scream."
  180.         (make-ending
  181.          "You scream into the void. There is no response. There never will be." #f))
  182.        (make-choice
  183.         "Accept your fate."
  184.         (make-ending
  185.          "You accept the simple beauty of the void. You achieve nirvana." #t))))))))
  186.  
  187. ;;Exercise 6
  188. ;;possible-endings: Section -> Natural
  189. ;;produces the total number of possible endings to the story
  190. (check-expect (possible-endings MY-STORY) 3)
  191.  
  192. (define (possible-endings s)
  193.   (cond
  194.     [(ending? s) 1]
  195.     [(chapter? s) (count-endings (chapter-choices ch))]))
  196.  
  197. ;count-endings: [X] [NEList-of Choice] -> Natural
  198.  
  199. (define (count-endings-loc nel)
  200.     (cond
  201.       [(empty? (rest nel)) (if (choice-ending? (first nel)) 1 0)]
  202.       [(cons? (rest nel)) (if (choice-ending? (first nel))
  203.                               (add1 (count-endings (rest nel)))
  204.                               (count-endings (rest nel)))]))
  205.  
  206. ;;choice-ending?: Choice -> Boolean
  207. ;;does the choice result in an ending?
  208.  
  209. (define (choice-ending? ch)
  210.   (ending? (choice-result ch)))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top