In this module we continue to explore problems with more interesting data definitions such as lists and trees.

  1. Define the term mixed data.
  2. Write a code example of mixed data.
  3. Explain how lists are represented as cons-cells.
  4. Explain what first, rest, and cons do to lists.
  5. Given a specification for information represented as a list, write a data definition that maps the information into a Scheme list.
  6. Given a data definition for a list, write a template.
  7. Use structural decomposition by writing a function that takes a list as input.
  8. Use structural decomposition by writing a function that takes itemized, compound, or mixed data as input.
  9. Write templates for a lists of compound data.
  10. Given a data definition of a list of compound data, write a template.
  11. Use templates by writing a function that takes lists of compound data input.
  12. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  13. Given a data definition for a list, write a template.
  14. Write templates for a lists of compound data.
  15. Given a data definition of a list of compound data, write a template.
  16. Use templates by writing a function that takes lists of compound data input.
  17. Use structural decomposition by writing a function that takes a list as input.
  18. Recognize information that is represented as alternating lists.
  19. Given a specification for information represented as alternating lists, write a data definition that maps the information into Scheme data.
  20. Given a Scheme expression, write down the sequence of steps taken during evaluation.
  21. Given a data definition for tree structured data, write a template.
  22. Given a specification for information represented as a tree, write a data definition that maps the information into Scheme data.
  23. Use structural decomposition by writing a function that takes itemized, compound, or mixed data as input.
  24. Use rackunit to write tests.
  25. Use rackunit to debug a function.
  • DUE DATE: October 16th, 2017 @ 11:59pm

Problem 1

  1. Provide a data definition for a list of list of symbols (LLoS).
  2. Desing a program that consumes an LLoS and returns the total number of symbols in the LLoS.
  3. Design a program that consumes a LLoS and a Symbol and returns the number of times that that symbol is found in lists of LLoS.
  4. Design a program that consumes an LLoS, a symbol s1 and a symbol s2 and replaces all occurrence of s1 with s2 and all occurrences of s2 with s1.

Problem 2

A classmate of yours is starting a small startup company and is asking for your help to evaluate the code that the startup already has. There is a lot of discussion around the implementation of an Integer Binary Search Tree (IBST). Your classmate is asking you to design an IBST with the following operations so that he can have another design from someone outside the company for a comparison.

  • ibst-size should consume an IBST and return the total number of nodes (including leafs) in the tree.
  • ibst-contains? should consume an IBST and a number and return true if the number provided is in the IBST and false otherwise.
  • ibst-add should consume an IBST and a number and return a new IBST with the number provided added to the original IBST
  • ibst-inorder should consume an IBST and return a list of numbers by traversing the IBST inorder.
  • ibst-postorder should consume an IBST and return a list of numbers by traversing the IBST postorder.
  • ibst-preorder should consume an IBST and return a list of numbers by traversing the IBST preorder.
  • is-ibst? should consume any Racket value and return true if and only if the input is a valid IBST and false otherwise.
  • ibst-remove should consume an IBST and a number and return a new IBST with the number provided removed from the original IBST. This function should return a valid IBST.

Problem 3

A friend is trying to write a small game but they are stuck at the moment and they are asking for your help. Here is what code they have so far 



;; a direction is one of
;;  - 'up
;;  - 'down
;;  - 'left
;;  - 'right

(define-struct bullet [location radius direction speed])
;; A Bullet is (make-bullet Posn PosInt Direction PosInt)
;; INTERP: represents a bullet with its current location,
;;         the bullet's radius, the bullet's direction and
;;         the bullet's speed

they are asking for your help in order to

  1. Define a data definition for a list of bullets
  2. Design a function called bullets-draw that consumes a list of bullets and draws the bullets on a 800x500 canvas
  3. Design a function called bullets-move that consumes a list of bullets and returns a list of bullets but each bullet has been updated to move speed units in the direction specified by the field direction inside the bullet structure.
  • DUE DATE: November 13th, 2017 @ 11:59pm

Space Invaders

The purpose of this assignment is to design a version of the Space Invaders game. You can play the original game here.

For your version of the game you will have to represent the following elements

  • one spaceship
  • four rows of invaders with at least 9 invaders in each row
  • spaceship bullets
  • invader bullets

The spaceship must be located at the bottom of the scene. The spaceship is always moving in a steady speed, and, should be allowed to move left and right only. The spaceship will also have the ability to fire bullets in order to hit invaders. Bullets are fired when the space bar is pressed by the user. Spaceship bullets move vertically (bottom to top) at a steady speed. When the spaceship reaches the edge of the scene then the spaceship stops moving until the user changes the spaceships direction and then the spaceship begins to move again.

Invaders are represented in rows, each row must have at least 9 invaders side by side. Invaders in the same row must have some space between them. Invaders do not move at all. At every clock tick a number of invaders get to fire bullets. The choice of which invader gets to fire on each tick is random. Invader bullets are the same as spaceship bullets in that they are the same size and move vertically. Invader bullets however move in the opposite direction as spaceship bullets, i.e., top to bottom.

When a spaceship bullet hits an invader, then the invader is destroyed. Destroyed invaders should no longer be visible on the canvas and should not be able to fire bullets. The spaceship bullet that hits an invader is also removed from the scene.

The game ends when either all invaders have been eliminated, or, when the spaceship has been hit by an invader bullet.

The version of the game you are going to design will be close to the original Space Invaders with some modifications/restrictions.

  1. The space ship moves in a steady speed in a direction. The direction is either left or right. The ship changes direction when the user clicks on the left or right arrow key.
  2. At any given point in time in the game there can only be at most 3 spaceship bullets in flight.
  3. At any given point in time in the game there can only be at most 10 invader bullets in flight.

Recommendations

  1. You are expected to use the Design Recipe for all functions that you design. There is only one exception, big-bang.
  2. Start by designing your data definitions. Pay close attention to the choices that you make when designing your data definitions.
  3. Once you have your data definitions written down, then design your draw functions. 
    
;; world-draw : World -> Image
;; Draw the world on the canvas
    This will allow you to take a World and draw it as an image. Ensure that you have a separate function to draw each component of the world. Here is an example image of the initial world. Here is one example of an initial world
    Space Invaders Inital World

You are strongly advised to also design the following functions 


;; move-spaceship: move the ship in the appropriate direction

;; move-spaceship-bullets : move each spaceship bullet in the list upwards by SPEED units

;; move-invader-bullets : move each bullet in the list downwards by SPEED units

;; invaders-fire :  fire from a random invader to hit the ship

;; remove-hits-and-out-of-bounds: 
;; remove any invaders that have been hit by a spaceship bullet.
;; Remove any bullets that are out of bounds

;; ship-hit : true if a bullet hit the ship, false otherwise

Given the above functions then the on-tick function should perform the following tasks

  1. move the spaceship
  2. move any spaceship bullets
  3. fire any invaders bullets if you can
  4. move any invader bullets
  5. remove any invaders that were hit and any (invader or spaceship) bullets that are out of bounds

Here is another screen shot while playing the game

Space Invaders Inital World

NOTE: if there is any parts of the preceding description that is unclear or you would like clarification you must consult with the course staff before you make a decision. Feel free to use Piazza, office hours and lectures to ask your questions/clarifications.

Space Invaders Extensions

Once you have the basic Space Invaders you are then asked to implement the following extensions.
  1. Your game should keep score. Score should be displayed in the top and middle of the scene. The score is a number. At the start of the game the score is 0. Every time an invader is hit by a space bullet the score should increase by 3 points.
  2. Your game should allow for 3 lives. A player should start the game with a total of 3 lives available. The number of available lives must be displayed at the bottom right corner of the scene. If the spaceship is hit by an invader's bullet the spaceship should be re-drawn in the center and one life must be removed. The games ends when the user loses their 3rd life.
  3. Your game should move all space invaders down every n clock ticks. You are free to choose n. After every n clock ticks all space invaders should move downard towards the spaceship by a fixed amount. The fixed amount moved downwards should be equal to half the height of an invader. With this extension we also add another condition that indicates that the game if over. The game should end under the following conditions
    1. The player has lost all 3 lives, or,
    2. All space invaders have been killed, or,
    3. The lowest invader on the scene has reached the same y-coordinate as the spaceship