On this page:
Partner Changes (if needed)
Pet Rock
Stuck In The Middle
Before You Go...
Shaking Things Up (Optional)

3 Structured and Self-Referential Data

home work!

Purpose: The purpose of this lab is to practice designing and programming with structured and self-referential data.

Textbook references:

Chapter 3: How to Design Programs

Chapter 4: Intervals, Enumerations, and Itemizations

Chapter 6: Adding Structure

Chapter 9: Designing with Self-Referential Data Definitions

Partner Changes (if needed)

If your partner has notified you that they are no longer in the course, we will find you a new partner and update the hand-in server teams.

Your TA will tell you more information about selecting a new partner.

Exercise 1 Exchange contact information with your partner: telephone number, latest-greatest social network scheme, whatever-app.

Agree to a first meeting time and meeting place. At that meeting, agree to next meeting time and meeting place.

Exercise 2 Establish your partnership on the handin server. In order to do that you will both need to request the partnership on the handin server. There are instructions here on how to request teammates. Your TAs will approve the team requests as they go through. Once the request is approved you should see your team on the course homepage under "Current teams".

Pet Rock

Goals: Practice processing self-referential data.

Aaron is very protective of his pet rock, "King Paimon". He carefully guards it by placing it in layers of bags of varying colors, each with their own size.

Starter Code: The following data definition encapsulates this psychologically dubious scenario.

; A PRS (PetRockStorage) is one of:
; - "King Paimon"
; - (make-bag String Number PRS)
(define-struct bag [color size contents])
; and represents the pet rock
; or a bag containing it (and possibly other bags)
;   with a specific color and size in cubic centimeters.

Sample Problem Define examples and design a template for a PRS. Note that larger bags can fit inside smaller ones.

; Examples
(define prs-0 "King Paimon")
(define prs-1 (make-bag "red" 10 prs-0))
(define prs-2 (make-bag "blue" 11 prs-1))
(define prs-3 (make-bag "green" 200 prs-2))
; prs-temp : PRS -> ???
(define (prs-temp prs)
    [(string? prs) ...]
    [(bag? prs)
     (... (bag-color prs)
          (bag-size prs)
          (prs-temp (bag-contents prs)))]))

Sample Problem Design a function which gives the size of the largest bag in a PRS (where the pet rock itself has size 0).

; largest-bag-size : PRS -> Number
; Computes the size of the largest bag in the given PRS
(define (largest-bag-size prs)
    [(string? prs) 0]
    [(bag? prs)
       (bag-size prs)
       (largest-bag-size (bag-contents prs)))]))
(check-expect (largest-bag-size prs-0) 0)
(check-expect (largest-bag-size prs-1) 10)
(check-expect (largest-bag-size prs-2) 11)
(check-expect (largest-bag-size prs-3) 200)

Exercise 3 Design a function which determines if a bag of a particular color is in a PRS.

Exercise 4 Design a function which takes a PRS and increases all of its bag sizes by 1.

Exercise 5 Design a function which takes a PRS and a number and discards all bags bigger than that size.

Exercise 6 Design the function well-stored? which ensures a PRS is comprised of successively smaller contents. Hint: break the problem down into English. Doing so shall hopefully show that a previously defined function will help.

Switch pair programming roles before continuing!

Stuck In The Middle

Goals: Use structures to write a simple but engaging game.

We are going to write a "click the midpoint" game. It will begin by showing players two points on a screen. The player is then expected to guess their midpoint by clicking on the screen. Once the player clicks, it will show them how the actual midpoint compares to where they clicked.

Starter Code: Below is a full data definition that will enable us to design this game. Since the game requires different behaviors based on whether or not the user has clicked yet, the data has two clauses.

; A MidpointGame is one of:
; - (make-pre-click Posn Posn)
; - (make-post-click Posn Posn Posn)
(define-struct pre-click [p1 p2])
(define-struct post-click [p1 p2 p-click])
; and represents the two points to be clicked between
; as well as where the player clicked (once they do)
; A Posn is a (make-posn Number Number)
(define posn-0 (make-posn 0 0))
(define posn-10 (make-posn 10 10))
(define posn-click (make-posn 6 6))
(define mpg-pre (make-pre-click posn-0 posn-10))
(define mpg-post (make-post-click posn-0 posn-10 posn-click))
; mg-temp : MidpointGame -> ?
(define (mg-temp mg)
  (cond [(pre-click? mg) (... (posn-temp (pre-click-p1 mg))
                              (posn-temp (pre-click-p2 mg)))]
        [(post-click? mg) (... (posn-temp (post-click-p1 mg))
                               (posn-temp (post-click-p2 mg))
                               (posn-temp (post-click-pclick mg)))]))
; posn-temp : Posn -> ?
(define (posn-temp p)
  (... (posn-x p) (posn-y p)))

Sample Problem Design the function which will be given to this game’s on-mouse handler; it should transition from a pre-click game to a post-click game when the user clicks.

; player-guess : MidpointGame Integer Integer MouseEvent -> MidpointGame
; Handles a user click:
;   if the game is pre-click, transition to a post-click game
;   if the game is post-click, do nothing
(define (player-guess mg x y event)
    [(pre-click? mg)
     (if (string=? event "button-down")
         (pre-click-p1 mg)
         (pre-click-p2 mg)
         (make-posn x y))
    [(post-click? mg) mg]))
  (player-guess mpg-pre 6 6 "button-down")
  (player-guess mpg-pre 6 6 "leave")
  (player-guess mpg-post 6 6 "button-down")
  (player-guess mpg-post 6 6 "leave")

Exercise 7 Design a function, midpoint, which computes the midpoint of two Posns.

Exercise 8 Design a function, game-midpoint, which takes a MidpointGame and determines the midpoint of the two static dots.

Exercise 9 Design a function distance which computes the distance between two Posns. The distance between two points is the square root of the sum of the squares of the differences in their x and y coordinates.

Exercise 10 Define visual constants for your program. A width, a height, a background image, a circle for the initial points, a circle for where the player clicks, and a circle for the midpoint will all come in handy.

Switch pair programming roles before continuing!

Exercise 11 Design a function which takes in an image, a Posn, and another image, and places the first image on the second one at the position given by the Posn.

Exercise 12 Design a function which takes two Posns, a color, and an image, and draws a line between those two points in that color. Hint: scene+line.

Exercise 13 Design a function which takes a MidpointGame and draws it. In a post-click game, a line should connect the two initial points and another line should connect where the player clicked and the actual midpoint. Be sure to use the constants you defined.

Exercise 14 Design a function user-error which takes a MidpointGame and determines the distance from the user’s click to the actual midpoint. The function should error if the user has not clicked yet.

Switch pair programming roles before continuing!

Exercise 15 Design a function random-pre-click which ignores its input (remember, when a function ignores its input we name that input _) and creates a MidpointGame with two randomly placed Posns (within the scene width and height, of course).

But wait! You are about to write a random function, so how can you test it? Turns out we’re in luck; check-random was designed for exactly this purpose.

Exercise 16 Design a main function that launches the game. The input can be ignored and the initial start state is random. The output should be the distance in pixels between where the player clicked and where the actual midpoint of the two initial dots are. The program should stop-when the player clicks.

Hint: we do not need to design a new function to give to the stop-when clause. What function already exists that fits our needs?

Exercise 17 Do you not see the world change after you click? Give your stop-when clause a second input, the function which draws your game, and try again. This tells big-bang to draw the final state of the world before exiting.

Before You Go...

If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance. We love to teach and you will learn. It’s symbiotic!

Shaking Things Up (Optional)

Goals: Make the game more interesting.

Switch pair programming roles before continuing!

Exercise 18 While this is a somewhat fun game, it is currently too easy. People have too much time to fine-tune their midpoint estimation. Design the function next-location which takes a MidpointGame. If the given game is in the pre-click state, produce a new, randomly generated game in the same state. Otherwise, output the given world as-is.

Exercise 19 Add this function to your big-bang’s on-tick clause. Your main function should now take in a number which will dictate the rate of how many seconds until the points switch places (so passing in the number 2 will cause it to change every two seconds, and passing in the number 1/2 will cause it to change twice per second). Be sure to update main’s signature and purpose statement with this new specification.

Switch pair programming roles before continuing!

Exercise 20 Manually starting the game over and over again is a bit tedious. Design a function which takes a MidpointGame and a KeyEvent and launches a new game if the game was already finished, otherwise it leaves it as is.

Exercise 21 Remove the stop-when clause from your world and use the function you just designed for your on-key handler.

Exercise 22 There would be many ways to extend this game, such as reporting the mean distance from the midpoint every time the player clicked instead of just the last one. How would you have to change the data definition of the world to accommodate for such a computation? Would it be possible with our current design paradigms? Give your hypothesis to a course staff member and see what they have to say, and feel free to modify the game to your heart’s content.