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

  1. Copy your q2.rkt program of Problem Set 06 to a file named set07/q1.rkt. Create a plain text file named set07/q1.txt as well. Modify your q1.rkt program as necessary to respect the abstraction barrier associated with the UTC and Flight abstract data types, without changing any of the provide 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 the flight.rkt file given to you for this assignment. When your q1.rkt program respects the abstraction barrier of the UTC and Flight ADTs, that program should run with either one of the two flight.rkt files: the one you wrote for Problem Set 06 and the one given to you by the course staff for this assignment.

  2. After you have modified your set07/q1.rkt program as necessary to respect abstraction barriers, make a copy of it in set07/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
          

For debugging: Click here to validate.