Homework 3

Please read chapter 8: Lists and chapter 9: Designing with Self-Referential Data Definitions in the textbook. Also read section 7 Advanced types in the Typed Racket Notes. We've skipped section 5 and 6 for now, but we'll come back to them.

Be sure to include type, purpose, definition and tests for all functions.

Include the following at the top of your homework:

#lang typed/racket

(require typed/test-engine/racket-tests)
(require typed/2htdp/image)
(require typed/2htdp/universe)

And include (test) at the bottom of your homework.

Problem 1

We will be creating a scene with three bouncing balls.

First, we will define three structures.

Create a structure Point with an x and a y, as we did in class.

Create a structure Ball to represent balls. Each ball has a position, velocity, radius, and a color. Use the Point structure to represent position and velocity. The x position of a ball is the distance from left edge to the center of the ball, and y position is distnace from top edge to the center of the ball. Larger x are farther right. Larger y are father down. I choose this interpretation of x and y so that drawing the scene will be easier later on.

Create a World structure. Our world has 3 balls and a width and a height.

Write a function move-ball : Ball -> Ball that moves a ball by it's velocity. It creates a new ball with the position equal to the old position plus the velocity.

Write a function bounce-if-needed : Ball World -> Ball that will handle bounces off the sides of the scene. If the ball position is past either the left or right edge of the scene, then the new ball has the opposite x-velocity of the old ball. Similarly, if the ball position is past either the top or bottom of the scene, the new ball velocity has the opposite y-velocity of the old ball.

Write a function update-ball : Ball World -> Ball that first moves a ball (using move-ball) and then updates the velocity (using bounce-if-needed).

Balls do not bounce off eachother.

Write a funciton update-world : World -> World that will update all three balls.

Write a function draw-world : World -> Image that will create an image of the world. Try using the scene functions in 2htdp/image. Start by looking at empty-scene and place-image.

Define a variable initial-world : World. Use some trial and error to pick interesting starting conditions for your world. There are lots of correct answers.

Try to run big bang:

(big-bang initial-world : World
          [to-draw draw-world]
          [on-tick update-world])

Problem 2

The Padovan sequence is defined as follows:

P(1) = 1
P(2) = 1
P(3) = 1
P(n) = P(n-2) + P(n - 3)

Define a function padovan that takes an Integer n as input and outputs a number which is the nth number in the Padovan sequence.

Problem 3

Euclid's algorithm is well known recursive algorithm for computing the greatest common divisor of two numbers. It is defined as follows:

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)

Write a function euclid that takes two nonnegative integers as input and computes their greatest common divisor using the above algorithm. You may not use the built in gcd function as part of your implementation. You will need to use the built in modulo function.

Problem 4

Write a function aspect-radio that takes two nonnegative integers as input. Those numbers are the width and height of an image. It should create a string representing the aspect ratio of that image. For example, an image that has width 20 and height 10 has aspect ratio "2:1". An image that has width 15 and height 25 has aspect ratio "3:5".

Hint: consider using the gcd function you write and the built-in functions number->string and string-append.

Submit your work in your repository in hw5/hw5.rkt by noon Friday, June 30.