1. Russian Dolls

A friend of yours was reading an online coding quiz. He is asking for your help in order to solve the following problem.

We are trying to represent russian dolls Matryoshka dolls to be precise. There are many dolls of increasing size. The smallest doll is made of solid wood, all other dolls are hollow in the middle and you can open them. Each size of doll can fit the previous size of doll inside of it.

We are providing you with he following incomplete data definition

(define DOLL 'doll) ;; the smallest sized doll that is not hollow

(define-struct nested-doll (inner))

;; A RussianDoll is one of
;; - 'doll
;; - (make-nested-doll RussianDoll)
;;   A NestedDoll is a (make-nested-doll RussianDoll)
;;   INTERP: represents a one level nesting of a russian doll
Practise Exercises

  • 1) Complete the data definition for RussianDoll. Provide examples and a deconstructor template.

  • 2) Design a function that given a Russian doll, returns the total number of dolls.

2. List of Strings

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

Practise Exercises

  • 3) Provide a complete data definition for a list of strings (LoS).

  • 4) Create some data examples of Lists of Strings

  • 5) Design a function called sizes that given a LoS returns a list that contains the number of characters in each string, e.g., (sizes (cons “a” (cons “aa” (cons “aaa” empty)))) ⇒ (cons 1 (cons 2 (cons 3 empty))). You might find the build in function string-length useful.

  • 6) Design a function called los-contains? that given a LoS and a String returns true if the string exists within the list and false otherwise.

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 NonNegInteger NonNegInteger)
;; INTERP: represents a cartesian coordinate with an x and y coordinate

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


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

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

  • 7) Finish the data definitions for Posn and List of Posns

  • 8) Create some data examples of Lists of Posns

  • 9) Design a function called lop-count that given a List of Posns returns the number of Posns in the list

  • 10) Design a function called lop-move-x that given an LoP and a postive integer n, returns a list of posns with each posn’s x value increased by n

  • 11) Design a function that given a list of posns returns the top most (the posn with the highest y value) in the list. Your function should give an error when given a empty list of posns. To see how you can create an error with an error message lookup the documentation for the function error and check-error for testing errors. If there are more than one posn with the highest y-coordinate returning any one of them is sufficient.

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

  • 12) 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.