Assignment 15
Due Date Monday 03/25 at 9pm
Purpose To process mutually-recursive data.
You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions. Failure to submit a .rkt file will result in a 0.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
Your code MUST conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
You must follow all the steps of the design recipe when completing this assignment.
Please be sure to look at the feedback for assignment 11 before submitting, as we will be grading you more harshly on things we have warned you about before.
You must submit this assignment with your partner. Please make sure you can submit with your partner before 5pm on Monday or we cannot guarantee that you will be able to submit your homework before the deadline. If the course staff are unable to assist you after 5pm and this causes your homework to be late we will not grant an extension.
(define-struct bst [comparator tree]) ; A [BST X] is a (make-bst [Comparator X] [Tree X]) ; and represents a binary search tree that contains data of type X with no repeats ; For some (make-bst f (make-branch x y z)) ; - x is greater than every element in the tree y according to the comparator f ; - x is less than every element in the tree z according to the comparator f ; - y and z are are also ordered according to the comparator ; Note: (make-branch x "leaf" "leaf") is ordered by any comparator ; A [Comparator X] is a [X X -> Number] function such that ; - (f a b) < 0 if a < b ; - (f a b) = 0 if a = b ; - (f a b) > 0 if a > b (define-struct branch [val left right]) ; A [Tree X] is one of: ; - "leaf" ; - (make-branch X [Tree X] [Tree X]) ; and represents a tree that contains data of type X
Exercise 1 Provide examples of the data definitions given.
Exercise 2 Design the function in-bst? which, given a [BST X] and a value X returns #true if the value is in the tree and #false otherwise. You should not traverse more elements than necessary. HINT: How can you use the properties of a binary search tree to avoid having to look at all the elements?
Exercise 3 Design the function swap-bst which, given a [BST X] produces its opposite. In other words, everything on the left is now on the right, and vice versa. The resulting tree should look like a mirror image of the tree in the inputted BST. REMEMBER: The resulting BST should have all the properties described in the BST definition. In order for this to work you will need to update more than just the tree itself.
Exercise 4 Design the function place-in-bst which, given a [BST X] and a value X, produces a [BST X] where the value X is placed in the correct location in the tree according to its comparator. If the value is already in the tree you should return the tree unchanged.
Choose Your Own Adventure
; A Section is one of: ; - Ending ; - Chapter ; and represents a section in a choose your own adventure book ; An Ending is a (make-ending String Boolean) (define-struct ending [text good?]) ; and represents an ending to the story with some text and whether it was a happy ever after ; A Chapter is a (make-chapter String [NEList-of Choice]) (define-struct chapter [text choices]) ; and represents a chapter in a choose-your-own adventure book with a body ; and a list of choices at the end ; An [NEList-of X] (Non-Empty List) is one of: ; - (cons X '()) ; - (cons X [NEList-of X]) ; A Choice is a a (make-choice String Section) (define-struct choice [text result]) ; and represents the blurb shown to the reader and the resulting section if that is the ; choice they make (define MY-STORY (make-chapter "You are alone in a room. There is a door before you." (list (make-choice "Stay in the room." (make-ending "You stay in the room. Nothing happens. Nothing ever will again." #f)) (make-choice "Open the door." (make-chapter "You open the door. On the other side lays an eternity of nothingness." (list (make-choice "Scream." (make-ending "You scream into the void. There is no response. There never will be." #f)) (make-choice "Accept your fate." (make-ending "You accept the simple beauty of the void. You achieve nirvana." #t))))))))
Exercise 5 Provide the templates for the above data definition.
Exercise 6 Design a function which, given a Section, produces the total number of possible endings to the story.
Exercise 7 Design a big-bang program which takes in a Section and allows the player to move through the story.
For chapters, it shows the player the text of the section, and beneath it, a list of the choices they have. The player can use the arrow keys (up/down) to tab through the choices available and then use enter (KeyEvent "\r") to move on to the selected result. Choices should be displayed in the order they are given and should not be rotated to select a choice. Instead the selected choice should be displayed in a different color from the other choices.
Be sure to handle up/down arrow keys at the beginning/end of the list of choices; pressing up at the top of the list should allow you to select the last choice and pressing down at the bottom of the list should allow you to select the first choice.
The game is over when the player reaches an ending. The program should display the text of the ending in blue if it is a happy ever after and in red if it is not. The program should output the text of the last section shown when the game ends or when the user exits.
Be sure to provide your stop-when clause your drawing function as a second argument so the ending is displayed when the program stops.