CS 5010: Problem Set 04

Out: Monday, 2 October 2017
Due: Monday, 9 October 2017 at 6pm local time

This is an individual assignment. You are not allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

The main purposes of this problem set are to give you practice designing functions that deal with lists, and to get you started using the System Design Recipe.

You must use Racket's Intermediate Student Language (ISL) for this problem set.

For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line

      (require "extras.rkt")

at the top of your file with the other require declarations. Then, for each problem, put in lines that say

      (provide function)

for each deliverable function, as you have done on previous problem sets. This will allow our testing framework to import your file and do automated testing on it. You can use check-location to double-check that your solutions are in the right place.

Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.

Be sure to fill out a work session report at the end of each work session. Tell git to add it to the files you will commit, and then commit and push (sync) that report in addition to committing and pushing your entire set04 directory. Do this at the end of every work session.

Remember to include a copy of extras.rkt racket in your set04 directory along with your q1.rkt and q2.rkt files.

For question 1, you should require "extras.rkt" and rackunit but nothing else.

For question 2, you should require "extras.rkt", rackunit, 2htdp/image, and 2htdp/universe, but nothing else.

Note: For all universe programs, you may assume the mouse is never dragged or moved outside the canvas. Once the mouse enters the canvas, if the mouse ever leaves the canvas, then the behavior of your system is unspecified.

(ListPractice1)

For this first part of Problem Set 04, you will not need to do any data design because the List data type, and all specific instances of that data type such as IntList and IntListList, are predefined by the lessons for Module 04.

The inner product of two sequences of real numbers x₁, ..., x_n and y₁, ..., y_n is defined as the sum of the pairwise products of corresponding numbers; in standard mathematical notation: ∑_i x_i y_i

You are to deliver a file named q1.rkt that defines and provides all 4 of the following functions:

          ;;; inner-product : RealList RealList -> Real
          ;;; GIVEN: two lists of real numbers
          ;;; WHERE: the two lists have the same length
          ;;; RETURNS: the inner product of those lists
          ;;; EXAMPLES:
          ;;;     (inner-product (list 2.5) (list 3.0))  =>  7.5
          ;;;     (inner-product (list 1 2 3 4) (list 5 6 7 8))  =>  70
          ;;;     (inner-product (list) (list))  =>  0
          
          ;;; permutation-of? : IntList IntList -> Boolean
          ;;; GIVEN: two lists of integers
          ;;; WHERE: neither list contains duplicate elements
          ;;; RETURNS: true if and only if one of the lists
          ;;;     is a permutation of the other
          ;;; EXAMPLES:
          ;;;     (permutation-of? (list 1 2 3) (list 1 2 3)) => true
          ;;;     (permutation-of? (list 3 1 2) (list 1 2 3)) => true
          ;;;     (permutation-of? (list 3 1 2) (list 1 2 4)) => false
          ;;;     (permutation-of? (list 1 2 3) (list 1 2)) => false
          ;;;     (permutation-of? (list) (list)) => true
          
          ;;; shortlex-less-than? : IntList IntList -> Boolean
          ;;; GIVEN: two lists of integers
          ;;; RETURNS: true if and only either
          ;;;     the first list is shorter than the second
          ;;;  or both are non-empty, have the same length, and either
          ;;;         the first element of the first list is less than
          ;;;             the first element of the second list
          ;;;      or the first elements are equal, and the rest of
          ;;;             the first list is less than the rest of the
          ;;;             second list according to shortlex-less-than?
          ;;; EXAMPLES:
          ;;;     (shortlex-less-than? (list) (list)) => false
          ;;;     (shortlex-less-than? (list) (list 3)) => true
          ;;;     (shortlex-less-than? (list 3) (list)) => false
          ;;;     (shortlex-less-than? (list 3) (list 3)) => false
          ;;;     (shortlex-less-than? (list 3) (list 1 2)) => true
          ;;;     (shortlex-less-than? (list 3 0) (list 1 2)) => false
          ;;;     (shortlex-less-than? (list 0 3) (list 1 2)) => true
          
          ;;; permutations : IntList -> IntListList
          ;;; GIVEN: a list of integers
          ;;; WHERE: the list contains no duplicates
          ;;; RETURNS: a list of all permutations of that list,
          ;;;     in shortlex order
          ;;; EXAMPLES:
          ;;;     (permutations (list))  =>  (list (list))
          ;;;     (permutations (list 9))  =>  (list (list 9))
          ;;;     (permutations (list 3 1 2))
          ;;;         =>  (list (list 1 2 3)
          ;;;                   (list 1 3 2)
          ;;;                   (list 2 1 3)
          ;;;                   (list 2 3 1)
          ;;;                   (list 3 1 2)
          ;;;                   (list 3 2 1))

We will be doing automated testing of your solution, so be sure your solution is in the right place (set04/q1.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after your require declarations:

          (check-location "04" "q1.rkt")

(SquashPractice3)

For this second problem, your job is to improve the simulation specified by Problem Set 03 by changing the definition of ball-racket collisions and by adding a new feature that allows expert squash players to challenge themselves by trying to keep multiple balls in play at once.

To make it easier to keep multiple balls in play, the definition of a collision between ball and racket is changed to:
- The ball collides with the racket if and only if all of the following are true:
  1. The ball's position in the previous tick does not lie on the 47-pixel line segment of the racket in the previous tick.
  2. The vy component of the ball's tentative velocity is either zero or negative positive.
  3. The line that connects the ball's position in the previous tick with the first tentative position calculated for the ball in this tick intersects the 47-pixel line segment that represents the racket's new position for this tick.
The other changes are:
- When the simulation is in a rally state, pressing the b key creates a new ball with position components (330,384) and velocity components (3,-9). This new ball behaves like the original ball, as specified by Problem Set 03.
- When the simulation is not in a rally state, pressing the b key does nothing.
- If a ball collides with the back wall, it disappears from the simulation. If its disappearance leaves no more balls within the simulation, the rally state ends as though the space bar had been pressed. The rally state does not end until all balls have disappeared or the space bar is pressed.
- Balls never collide with each other, even if they have the same position coordinates. (In the three-dimensional real-world, two balls with the same x and y components are likely to be at different altitudes, which your simulation does not model.)
As in Problem Set 03, there is initially one ball, both in the ready-to-serve state and in the rally state.

You are to deliver a file named q2.rkt that defines appropriate data types Ball, Racket, and World, defines and provides the fifteen functions specified in part 1 of Problem Set 03 except for world-ball, defines and provides all three functions specified in part 2 of Problem Set 03, and also defines and provides the world-balls function specified below:
```
          ;;; world-balls : World -> BallList
          ;;; GIVEN: a world
          ;;; RETURNS: a list of the balls that are present in the world
          ;;;     (but does not include any balls that have disappeared
          ;;;     by colliding with the back wall)
	
```
Note that functions defined by define-struct are not automatically provided; you must include explicit provides for these functions.

We recommend you practice the Iterative Design Recipe by making a copy of your (corrected) q2.rkt file from Problem Set 03 and placing that copy and a copy of extras.rkt in a new set04 directory. Then, before you forget it, delete the provide for world-ball and add a provide for world-balls. Then change set04/q2.rkt as necessary so it implements the simulator as specified for this problem set.

Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (set04/q2.rkt in your private cs5010f17/pdp-YOURUSERNAME repository), and that it provides all of the functions listed above. To see if your file is in the right place, insert the following line at the top of your file but after your require declarations:
```
          (check-location "04" "q2.rkt")
```