1. Binary Trees

A friend missed class this past Monday and is completely clueless when it comes to binary trees. They managed to start the data definitions but got frustrated and gave up. Help them out!

;;  A SBT (String Binary Tree) is one of
;; - ‘leaf
;; - (make-node String SBT SBT)

(define-struct node (val left right))
;; A Node is (make-node String SBT SBT)
;; INTERP: Represents a node in a SBT that has exactly 2 children.
Practise Exercises

  1. Write a template for String Binary Tree

  2. Create some data examples of SBTs

  3. Design a function called count that given a string binary tree returns the number of nodes in the tree

  4. Design a function called sbt-append that given a SBT returns one string that is the result of appending each node in the SBT (any order of appending nodes is ok)

  5. Design a function called contains that given an SBT and a string returns true if the string exists within the binary tree and false otherwise

2. List of Strings

You have another friend who actually attended class on Monday but spent the entire time on Facebook looking at their crush’s profile pictures from 2010. They need help with Lists of Strings. Use the following data definitions:

;; A List of Strings (LoS) is one
;; - empty
;; - (cons String LoS)

;; Template
;; los-fn: LoS -> ???
#;(define (los-fn los)
    (cond
      [(empty? los) ...]
      [(cons? los) ... (first los) ...
                   ... (los-fn (rest los)) ...]))
Practise Exercises

  1. Create some data examples of Lists of Strings

  2. Design a function called sizes that given a LoS returns a list that contains the number of characters in each string

    • ex. (sizes (cons “a” (cons “aa” (cons “aaa” empty)))) ⇒ (cons 1 (cons 2 (cons 3 empty)))

  3. Design a function called contains that given a List of Strings and a string returns true if the string exists within the list and false otherwise

  4. Design the functions snoc that given a LoS and a string, returns the LoS with the string appended at the end of the list

3. List of Posns

The team you are a part of is working on designing a game. In this game, little missiles move across the screen from left to right. You are in charge of keeping track of these missiles and their locations. You decide the best way to do this is to use a List of Posns. You are given the following incomplete data definitions from a previous team member who decided they had enough of Dr.Racket to pursue their passion of ceramics.

;; A Posn is a (make-posn Number Number)

;;; Template
;; posn-fn: Posn -> ???
#; ???


;; A List of Posns (LoP) is one of
;; - empty
;; - ???

;;; Template
;; lop-fn: LoP -> ???
#;???
Practise Exercises

  1. Finish the data definitions for Posn and List of Posns

  2. Create some data examples of Lists of Posns

  3. Design a function called count-posn that given a List of Posns returns the number of Posns in the list

  4. Design a function called posn-equal? that given two LoPs returns true if the lists have the same elements in the same order

Your team has now given you the width and height of the scene of the game (500 x 500). During the game, the missiles that exit the screen should be removed from the List of Posns.

Practise Exercises

  1. Design a function called remove-out-of-scene that given a List of Posns returns the list with all posns located outside of the scene removed

    • You find post-it notes with _ helper functions … HELPER FUNCTIONS … hELpeR fUncTiOnS _ written on them all around the now-ceramicist’s previous office. Maybe they’re trying to send a message…

4. More lists, more structs, and more posns

You are now on a team of graphic designers working on the newest version of Microsoft Paint. The current project involves designing simple shapes for the program. You are put in charge of quadrilaterals. You need to design something to keep track of the coordinates of each corner of the shape. So, you decide to create a struct that contains the four corners of the shape.

(define-struct corners (first second third fourth))
Practise Exercises

  1. Complete the data definitions for corners using Posns to represent the quadrilateral’s corners

  2. Create a template for your structure

  3. Write some data examples of corners structs

  4. Design a function called is-square? that given a corners will return true if all the edges of the quadrilateral are of equal length

    • To calculate distance \(d\) between two points \((x_{1},y_{1})\) and \((x_{2},y_{2})\) use this formula

\[d = \sqrt{(x_{2} - x_{1})^{2} + (y_{2} - y_{1})^{2}}\]

Since you performed so splendidly on the previous task, your team has decided to entrust you with the task of creating a List of Corners!

Practise Exercises

  1. Provide the data definition for a List of Corners (LoC)

  2. Create a … yup! you guessed it! … template for your data definitions

  3. Write some data examples of LoC s

  4. Design a function called squ-exist? that given a List of Corners returns true if there is at least one square in the list

  5. Design a function called all-square? that given a LoC returns true if all elements of the LoC are squares

  6. Design a function called move-shape that given a List of Corners returns the list with every posn of every corners moved down by 5 and to the right by 5

5. Playing with Big Bang

You are now at your 3rd job in 1 year (how fickle you are!). And once again, you are working on developing a game. Because you have so much work experience, your superiors have decided to put you in charge of moving a square around a screen! How exciting! You are given the following data definitions:

(require 2htdp/image)
(require 2htdp/universe)

(define-struct world (pin square))
;; A World is (make-world Posn Corners)
;; INTERP: represents the pin (location) of the center of the square and
;;         the square to draw

(define BACKGROUND (empty-scene 500 500))
(define INIT-WORLD (make-world (make-posn 250 250)
                               (make-corners (make-posn 0 0)
                                             (make-posn 20 0)
                                             (make-posn 0 20)
                                             (make-posn 20 20))))

For this game, you will be using Corners and LoCs. Assume that all Corners in the list are squares.

Practise Exercises

  1. Design a function called draw-world that given a world, will draw the square at the pin on the canvas

    • It is up to you to decide what the color and mode of the square will be

  2. Design a function called move-left that given a world, will return a new world were the pin has shifted to the left by 10

  3. Design the functions move-right, move-up, and move-down that moves the pin to the right, up, and down by 10 units respectively

Now, your team shares with you that they are very indecisive and the speed at which the square moves is probably going to change a couple times.

Practise Exercises

  1. Create a constant for speed and use it in your functions

You are given the following code to test out your functions:

(big-bang INIT-WORLD
          (on-tick move-left 0.1)
          (to-draw draw-world))
Practise Exercises

  1. Using the code above, run your program. Switch the move- functions for on-tick and observe the effects