MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001 – Structure and Interpretation of Computer Programs
Spring Semester, 2004
Project 1 – Going Bananas
- Issued: Friday, February 6
- To Be
Completed By: Friday, February 13,
- Note:
A “star” will be recorded with the grade for your project1 if
it is turned in early – by Thursday, February 12,
- Code to load for this project:
- A link to the code file banana.scm is provided from the Projects link on the course web page. This file contains the skeleton of the procedures described here, and some utility procedures you will need.
Purpose
The purpose of Project 1 is for you to gain experience with writing and testing relatively simple procedures. You should create a file with your project solutions for uploading to the 6.001 on-line tutor. For each problem below, include your code (with identification of the problem number being solved), as well as comments and explanations of your code, and demonstrate your code’s functionality against a set of test cases. On occasion, we may provide some example test cases, but you should always think about and include additional meaningful test cases to ensure that your code works not only on typical inputs, but also on “boundary” or difficult cases. Get in the habit of writing and running these test cases after every procedure you write – no matter how trivial the procedure may seem to you.
Additional guidelines for project submission are available under the “How to write up a project” link off of the main course web page.
Scenario
Back in the day, when the PC was young and frivolous, there was a game written in QBasic called Gorillas. Picture, if you will, a vast cityscape, with many tall buildings. Atop a building on the left and a building on the right stand two massive gorillas. Each gorilla has a bulging sack of bananas. In this arena, they duel by throwing these explosive bananas at the base of each other’s building until only one gorilla remains standing. You will help bring this classic game back to life.
Figure 1. A screen shot from the original QBasic Gorillas game.
Problem 1: Basic Physics
We need a physical model for a flying explosive banana. For the moment, we'll model it as a particle with some initial position u, initial velocity v, and some acceleration a, as pictured in Figure 2 below. The equation for the position of the banana at time t, given a, v, and u is ut = ½ a t2 + v t + u. Later, we can apply this equation to either the horizontal (x) component of banana motion, or the vertical (y) component of banana motion.
Figure 2: Motion of a banana in a generic direction.
Write a procedure that takes in a, v, u, and t
and returns the position of the banana at time t.
(define
position
(lambda (a v u t)
YOUR-CODE-HERE))
Test your position code for at least the following cases:
(position 0 0 0 0) ; -> 0
(position
0 0 10 0) ; -> 10
(position
0 5 5 5) ; ->
30
(position
1 1 1 1) ;
-> 2.5
(position
10 10 10 10) ; -> 610
The template code file banana.scm will have these tests, and other test cases for other procedures, which you should run (you can add/show your output values). In addition, you should add some test cases of your own to these to cover other boundary and typical conditions.
Problem 2: Basic Math
In order to compute when the banana hits the ground, we'll want to find when the y coordinate of the banana's position reaches zero. This can be discovered by finding the roots of the y position equation, and selecting the one that is larger (later in time). The proper tool for this is the quadratic formula. Given the coefficients of the quadratic equation az2 + bz + c = 0, write a procedure to find one of the roots (call this root1), another procedure to find the other root (call this root2), and finally a procedure larger-root that returns the largest root of the equation.
(define
root1
(lambda (a b c)
YOUR-CODE-HERE))
(define root2
(lambda (a b c)
YOUR-CODE-HERE))
(define larger-root
(lambda (a b c)
YOUR-CODE-HERE))
Problem 3: Flight Time
Given an initial upward velocity (in meters per second, or
m/s) and initial elevation or height (in meters, or m), write a procedure that computes
how long the banana will be in flight. Remember that gravity is a downward
acceleration of 9.8m/s2.
(define flight-time
(lambda
(vertical-velocity elevation)
YOUR-CODE-HERE))
Problem
4: Flight Distance
Suppose the banana is thrown with some velocity v, at a starting angle alpha relative to the horizontal (in degrees), and from an initial elevation (in meters). We wish to compute the distance in the horizontal direction the banana will travel by the time it lands. Remember that some of the velocity vector goes into the x direction, and some into the y, as pictured in Figure 3 below.
Figure 3: Motion of a banana in two dimensions, acting under gravitational acceleration a.
Checking the Scheme manual, you will find procedures sin and cos. To use these (which require angles in radians rather than degrees), you may also find the procedure degree2radian useful. It is provided in banana.scm, and is given below:
(define degree2radian
(lambda (deg)
(/ (* deg pi) 180.)))
Write a procedure distance which returns the lateral distance the banana thrown with given velocity, angle, and initial elevation will travel before hitting the ground.
(define distance
(lambda (angle velocity elevation)
YOUR-CODE-HERE))
Problem 5: What’s a Hit?
In
order for a thrown banana to hit the target, it must land within some proximity
of the target. Write a procedure hit? which returns #t when a throw comes
within burst-radius of the target and #f otherwise.
(define hit?
(lambda (angle
velocity elevation burst-radius target-distance)
YOUR-CODE-HERE))
With the procedures from problems 1 through 5, we now have
enough to resurrect the game. A procedure called play has been provided for you in the banana.scm file. Try it out by evaluating
the play procedure definition, and then evaluating (play 10 3 1 2), for example. When running, you enter
values for velocity and range (in the *scheme*
buffer) to try to hit the other target. You can ctrl-c ctrl-c to terminate the game.
Problem 6: Angle Targeting
You
are merrily playing the game, when the gorilla on the left reaches out and
captures you. He wants you to write some procedures to help him in targeting
his throws.
The
gorilla will tell you his elevation, the magnitude of the velocity vector he
will use to throw the banana, and the target-distance. The gorilla wants a find-angle procedure in order to
know at what angle relative to the horizontal, in degrees, to throw the banana
to hit the target. The gorilla will also tell you how close the banana needs to
be to the target in order for the burst to destroy the target (i.e. the burst-radius).
Write the procedure find-angle
which returns the desired angle, between 0 and 90 degrees, to hit the target. If
no angle works in this range, find-angle
should return #f .
Hint: a possible strategy is to try all angles from an
initial angle (which might be 0 degrees by convention) to 90 degrees looking
for one which lands the banana within burst-radius of the target-distance. A
common structure involving a “helper” procedure is suggested as
shown below. The main procedure find-angle
calls find-angle-helper to get
the search started.
(define find-angle
(lambda
(velocity elevation burst-radius target-distance)
(find-angle-helper
0 velocity elevation burst-radius target-distance)))
(define find-angle-helper
(lambda (angle
velocity elevation burst-radius target-distance)
YOUR-CODE-HERE))
Problem 7: Angle and Velocity Targeting
Sometimes the gorilla finds that no angle works, for the set velocity magnitude he has been using. This makes him quite upset. The gorilla has come to trust his pet programmer (you), and would like you to suggestion not only the angle to use, but also the velocity (in the range from 1 to 50 m/s) needed to hit the desired target.
Write a procedure find-throw that determines both an angle and a velocity that hits the target. In this case, because you have to find and communicate two values to the gorilla (which is a little tricky given the Scheme we have so far covered), you should use a procedure (tell-gorilla angle velocity) from inside your procedure to finally communicate your answer to the gorilla. If no angle and velocity combination works, you can return (tell-gorilla #f #f) . The tell-gorilla procedure is already defined for you in the banana.scm file, and an example use of tell-gorilla is shown below.
; A bogus find-throw
procedure that
; simply
refuses to find a correct solution, but
; instead
just tells the gorilla anything (not a
; smart
thing for a pet programmer to do!)
;
(define
find-throw
(lambda
(elevation burst-radius target-distance)
(tell-gorilla 45 10)))
You want to survive longer than the rather unwise programmer above. Implement a working find-throw procedure.
Hint: your procedure might try all velocities (in range 1-50) in an attempt to
find an angle that works, and then tell-gorilla
a throw that comes within burst-radius of target-distance.
Problem 8: Bouncing Bundles of Bananas
Your gorilla has an innovation: he has just acquired a bouncing banana bundle that he is very excited about. The banana bundle consists of some number (num) of the usual explosive bananas. The gorilla throws the bundle in the usual way, but when a bundle hits the ground, half of the bananas explode and thus propel the remaining smaller bundle (consisting of the other half of the bananas) at twice the velocity, as illustrated in Figure 4. At each bounce, the smaller bundle leaves the ground at the same angle to the horizontal as the original bundle was thrown at.
Figure 4. How a bundle of five bananas bounces. A smaller bundle of two bananas survives the first bounce and launches with twice the velocity. One banana survives the next bounce and launches with another doubling in velocity.
The utility procedure num-survive can be used to calculate the number of bananas which survive any given bounce (when there are num bananas in the bundle at the time it contacts the ground).
; How many bananas in a bundle survive a bounce
;
(define num-survive
(lambda (num)
(if (even? num)
(/ num 2)
(/ (- num 1) 2))))
Write a procedure bundle-bounces that returns the number of times the bundle bounces before the last banana explodes. Note that the last banana hitting the ground does not count as a bounce, as illustrated in Figure 4.
(define bundle-bounces
(lambda (num)
YOUR-CODE-HERE))
Problem 9: If a Bundle of Bananas Could Bounce, How Far Would It Go?
Write a procedure bundle-distance that returns the total distance the last banana in a bundle with num bananas, thrown at some velocity, some angle, and from initial elevation, will have traveled. For example, in Figure 4 the bundle-distance of the original bundle thrown by the gorilla would include the distance traveled before the first bounce, the distance from the first to the second bounce, and the distance from the second bounce to the final explosion.
(define bundle-distance
(lambda (num
angle velocity elevation)
YOUR-CODE-HERE))
Comment on the similarity and differences between your implementation of this bundle-distance procedure and the bundle-bounces procedure.
Problem 10: Banana Bundle Targeting
Now that you can calculate the total distance a banana bundle will go, your gorilla agrees to set you free if you can provide a procedure find-bundle-throw that tells him the angle and velocity at which to throw the bundle such that the final banana hits the target. He will specify the number of bananas in the bundle, as well as the initial elevation and the distance to the target, and the burst radius as before.
You are now an experienced programmer in all things related to bananas. Based on your experience, implement this new capability. Note that you may need to implement several additional utility procedures, or variants of other existing procedures, in order to solve this problem – and thus ultimately be freed from gorilla banana land to find a warm cozy bed and get some sleep.
(define find-bundle-throw
(lambda (num elevation burst-radius target-distance)
YOUR-CODE-HERE))
Problem 11: The Conscientious Programmer
Your gorilla is happy and sets you free. You try to sleep, but something is bothering you about the code you have written. You finally put your finger on it: you have multiple pieces of code in your implementation that do almost exactly the same thing. You realize this will create maintainability problems in the future for your gorilla or his next programmer. As a conscientious programmer, you return to your long lost gorilla friend and offer to clean up your code.
Write a new (very short!) version of find-throw that uses find-bundle-throw. Comment on any other places you might suggest further changes to clean things up (you do not need to actually implement these).
Submission
Once you have completed this project, your file should be submitted electronically on the tutor, using the Submit Project Files button. Remember that this is Project 1; when you are have completed all the work and saved it in a file, upload that file and submit it for Project 1.