CS 5010: Problem Set 07
Out: Monday, 27 February 2017
Due: Monday, 13 March 2017 at 6pm
This is a pair programming assignment. You are required to complete this problem set in collaboration with your assigned partner, but neither of you are 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.
As in previous problem sets, you and your partner are required to push your files at the end of every work session. (You may push your files several times during a work session, but we do not require you to do so.)
At the end of every work session, you are required to update your log file to record the time you spent in that work session. (Please do not include the time you spent in any previous work sessions, as those times will already have been recorded in previous versions of your log file.) If both of you work together during a work session, both of you must update your log files, recording only the time you spent working. Do not include your partner's time in your log file, but be sure to push the updated versions of both log files.
This problem set has two purposes. One is to give you some appreciation for abstract data types. Another is to give you some practice with invariants and contexts.
You must use the HtDP Intermediate Student Language + Lambda for this problem set. You should use HOFs wherever appropriate.
As in previous problem sets, you must download a copy of
extras.rkt
and push it to the set07
directory with your solutions.
Then import that library by including the line
(require "extras.rkt")
at the top of your files with your other require
declarations. Following those require
declarations,
write provide
declarations that provide all of
the functions you are required to provide, without providing any
functions you are not required to provide.
That will allow our testing framework to import your files
and do automated testing on them.
You can use check-location
to double-check that your
files are in the right place.
For the first question in this problem set,
you must also download a copy of
flight.rkt
and use that implementation of flight.rkt
instead of the flight.rkt
file you wrote
for Problem Set 06.
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.
Problem Specification
-
Copy your
q2.rkt
program of Problem Set 06 to a file namedset07/q1.rkt
. Create a plain text file namedset07/q1.txt
as well. Modify yourq1.rkt
program as necessary to respect the abstraction barrier associated with theUTC
andFlight
abstract data types, without changing any of theprovide
declarations, contracts, or purpose statements from Problem Set 06.Record all of the changes that were necessary in your
q1.txt
file; when you're done, that file will tell you some of the things you did wrong on Problem Set 06. Test your program using theflight.rkt
file given to you for this assignment. When yourq1.rkt
program respects the abstraction barrier of theUTC
andFlight
ADTs, that program should run with either one of the twoflight.rkt
files: the one you wrote for Problem Set 06 and the one given to you by the course staff for this assignment. -
After you have modified your
set07/q1.rkt
program as necessary to respect abstraction barriers, make a copy of it inset07/q2.rkt
. Modify that program as necessary to work without the preconditions that say there are no non-trivial round trips.In other words: Define and
provide
the three functions specified below.;;; can-get-there? : String String ListOfFlight -> Boolean ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight that describes all of the flights a ;;; traveller is willing to consider taking ;;; RETURNS: true if and only if it is possible to fly from the ;;; first airport (ap1) to the second airport (ap2) using ;;; only the given flights ;;; fastest-itinerary : String String ListOfFlight -> ListOfFlight ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight that describes all of the flights a ;;; traveller is willing to consider taking ;;; WHERE: it is possible to fly from the first airport (ap1) to ;;; the second airport (ap2) using only the given flights ;;; RETURNS: a list of flights that tells how to fly from the ;;; first airport (ap1) to the second airport (ap2) in the ;;; least possible time, using only the given flights ;;; NOTE: to simplify the problem, your program should incorporate ;;; the totally unrealistic simplification that no layover ;;; time is necessary, so it is possible to arrive at 1500 ;;; and leave immediately on a different flight that departs ;;; at 1500 ;;; travel-time : String String ListOfFlight -> NonNegInt ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight that describes all of the flights a ;;; traveller is willing to consider taking ;;; WHERE: it is possible to fly from the first airport (ap1) to ;;; the second airport (ap2) using only the given flights ;;; RETURNS: the number of minutes it takes to fly from the first ;;; airport (ap1) to the second airport (ap2), including any ;;; layovers, by the fastest possible route that uses only ;;; the given flights