**Out:** Monday, January 25, 2016

**Due:** Monday, February 1, 2016
at 500pm EST

The goal of this problem set is to help you design functions that deal with finite data.

You must use the HtDP Beginning Student Language to solve the problems.

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 requires. Then, for each problem, put in lines that say

(providefor each deliverable function. Thus, for problem 1, the top of yourfunction)

`editor.rkt`

file should say
(require rackunit) (require 2htdp/universe) ; needed for key=? (require "extras.rkt") (provide make-editor editor-pre editor-post editor? edit)

This will allow our testing framework to import your file and do automated testing on it.

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, code, and tests. Be sure to follow our coding conventions. This will make the TA's job much easier.

Be sure to sync your work and fill
out a Work Session Report at the end of every work session. Use the
Work Session Report for
PS02. Remember to include `extras.rkt`

and any other local
files you need (such as a `fsm.jpg`

or `fsm.png`

file) in your repository folder.

- (Tiny Text Editor)

Do exercise 84 (the function "edit") from Part I, section 5.10 of HtDP/2e.You are to write a file called

`editor.rkt`that`provide`

s the following functions:make-editor editor-pre editor-post editor? edit

Note: for our purposes, we will consider

`KeyEvent`

to be a scalar data type, which can be decomposed using the Cases strategy.`KeyEvent`

and`key=?`are defined in the`2htdp/universe`

module. Look in the Help Desk for details. You will need to require`2htdp/universe`to import`key=?`.We will be doing automated testing of your solution, so be sure your solution is in the right place (

`set02/editor.rkt`in your private`cs5010sp16/pdp-`repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:*YOURUSERNAME*(check-location "02" "editor.rkt")

- (Finite State Machine)

This exercise is loosely based on Exercise 111 in HtDP/2e, but you willcreate any displays.*NOT*As in Exercise 111, you are to design a set of functions that illustrate the workings of a finite-state machine. Your machine will accept a sequence of letters (with each letter represented as a

`1String`

) if and only if that sequence exactly matches the regular expression((a | b)* r (a | c | d)*)*

The empty sequence matches that regular expression, as do the sequences

`r`,`arc`,`bard`, and`abracadabra`, but the sequences`a`,`card`, and`bcr`do not match.The legal inputs that can be passed as a second argument to your "next-state" function are precisely the strings "a", "b", "c", "d", and "r". Any other inputs violate that function's contract; its behavior on illegal inputs is unspecified.

First perform an information analysis and design the data representation for the states of your machine. Your information analysis and design should include a state-transition diagram (like the ones here) that shows the meaning of your machine states. Keep your state transition diagram as simple as possible. Submit your state-transition diagram either as ascii art in your

`fsm.rkt`

file, or in JPEG or PNG format as a separate file named`fsm.jpg`

or`fsm.png`

, which you can create using a graphics program or by drawing your state transition diagram on a piece of paper and taking a good picture of it.After you have done your data design, continue using the design recipe to design and

`provide`the following functions in a file named`fsm.rkt`initial-state : Number -> State GIVEN: a number RETURNS: a representation of the initial state of your machine. The given number is ignored. next-state : State MachineInput -> State GIVEN: a state of the machine and a machine input RETURNS: the state that should follow the given input. accepting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff the given state is a final (accepting) state rejecting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff there is no path (empty or non-empty) from the given state to an accepting state

Please note that some of your states are likely to be neither accepting nor rejecting.

You will need to provide data definitions for State and for MachineInput. Be sure to write an interpretation for each state. There is no need to write an interpretation for MachineInput, since the problem is already phrased in terms of strings.

Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (

`set02/fsm.rkt`in your private`cs5010sp16/pdp-`repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:*YOURUSERNAME*(check-location "02" "fsm.rkt")

- (Perpetual Goofball)

The physics marketing department at a nearby university has hired you to help produce an animation of the amazing Perpetual Goofball they hope to make into a consumer product or military weapon.Once created and set in motion, the Perpetual Goofball moves forever while its center maintains a perfectly constant speed.

For safety reasons, the Perpetual Goofball's motion is confined to the floor of a specially constructed square arena that measures 4 metres (400 cm) on each side.

The Perpetual Goofball is circular, with a normal radius of 20cm. Whenever the Perpetual Goofball touches any side of the arena, however, its radius automatically contracts to match the distance from the Perpetual Goofball's center to the nearest side of the arena.

The Perpetual Goofball's radius never becomes less than zero. When its radius reaches zero, the Perpetual Goofball rebounds via a

*perfect bounce*.A perfect bounce is defined as follows. Consider a Cartesian coodinate system in which the x and y axes are parallel to the sides of the arena, and let vx and vy be the Perpetual Goofball's components of velocity in the x and y directions. If its radius reaches zero because it is touching a side of the arena that runs parallel to the y axis, then its velocity in the x direction changes from vx to -vx. If its radius reaches zero because it is touching a side of the arena that runs parallel to the x axis, then its velocity in the y direction changes from vy to -vy.

We will use graphics-style coordinates instead of mathematical coordinates, with the walls of the arena parallel to the x and y axes and the exact center of the arena at the origin. That implies the northernmost wall of the arena is at y = -2m = -200cm and the eastern wall is at x = 2m = 200cm.

You will simulate a prototype of the Perpetual Goofball whose direction of travel is constrained to the following eight directions:

- north (with negative velocity in the y direction)
- south (with positive velocity in the y direction)
- east (with positive velocity in the x direction)
- west (with negative velocity in the x direction)
- northeast
- southwest
- northwest
- southeast

The prototype's velocity is also constrained by requiring each of its vx and vy components to be -1, 0, or +1.

Your job is to write a file called

`goofball.rkt`

that provides the following functions:goofball-at : Integer Integer Integer Integer -> Goofball GIVEN: an x-coordinate and a y-coordinate in cm, and velocity components vx and vy in cm/s WHERE: the x and y coordinates lie within the bounds of the arena, and both vx and vy have absolute value less than or equal to 1 RETURNS: a Perpetual Goofball with its center at the x and y coordinates, velocity components vx and vy, and radius determined by its distance from the nearest arena wall up to a maximum of 20cm goofball-radius : Goofball -> Integer GIVEN: a Goofball RETURNS: its radius, in cm goofball-x : Goofball -> Integer goofball-y : Goofball -> Integer GIVEN: a Goofball RETURNS: its corresponding x or y coordinate, in cm goofball-vx : Goofball -> Integer goofball-vy : Goofball -> Integer GIVEN: a Goofball RETURNS: its corresponding vx or vy velocity component, in cm/s goofball-one-second-later : Goofball -> Goofball GIVEN: a Goofball RETURNS: a Goofball like the given Goofball would become one second later, following the Goofball's laws of motion (and interaction with the arena)

Note: When a specification uses a single purpose statement to describe a related group of functions, as was done above with

`goofball-x`

and`goofball-y`

, and with`goofball-vx`

and`goofball-vy`

, you need only write down the purpose statement once. If your design strategy is the same for all of the functions in a group, then you only have to write that design strategy down once. Your examples and tests, however, must cover all of the functions.As before, remember that we will be doing automated testing of your solution, so be sure it is in the right place with the correct file name.

Last modified: Mon Jan 25 2016