完成Python基础作业，对 OpenFlights
的数据进行处理运算。
Introduction
In Assignment 3, you will be implementing several functions that explore the
airport and flight data on OpenFlights - “a tool that lets you map your
flights around the world, search and filter them in all sorts of interesting
ways, calculate statistics automatically, and share your flights and trips
with friends and the entire world (if you wish).” OpenFlights on GitHub is an
open-source project. This handout explains the problem being solved and the
tasks to complete for the assignment. Please read it carefully and in its
entirety.
Goals of this Assignment
The purpose of this assignment is to give you practice with understanding a
complicated real-world problem domain. The programming concepts you will
practice are:
- You will be able to write functions that involve dealing with data read from files, including learning how to add docstring examples for them.
- You will be able to build, use and manipulate dictionaries.
- You will learn how to use a new data structure called ‘sets’.
- You will design algorithms and functions using the Function Design Recipe.
- You will use helper functions to help organize your program and reduce repetitive code.
- You will debug your code and use doctests for testing.
OpenFlights
OpenFlights is “a tool that lets you map your flights around the world, search
and filter them in all sorts of interesting ways, calculate statistics
automatically, and share your flights and trips with friends and the entire
world (if you wish).” This assignment utilizes airport and flight data from
OpenFlights, so we recommend that you go try it out for 10 minutes. It should
make understanding the rest of this assignment much easier. You don’t need to
create an account, just try these things:
- Find the PUQ airplane icon at the bottom of South America. It represents an airport. Click it. A chat bubble appears with information in it, including the name of the airport, the abbreviation (PUQ), the city and country, and the number of flights.
- Click the blue splat icon (looks like a paw with 4 fingers) in the bottom right of the chat bubble. This zooms you in on the airport, displays the city information at the top of the window, and shows you direct flights connected to PUQ.
- Click on the icon next to “7 routes” in the city information. This displays a table of flights from PUQ to various cities. What do the columns all mean?
- Continue to explore the website. What happens when you click on the various pieces of information in the table?
In this assignment, you will be implementing several functions that explore
flight data. OpenFlights on GitHub is an open-source project.
Preliminary Knowledge
Airport Codes
Airports have two types of codes: IATA and ICAO, issued by two different
organizations. We will use the IATA code throughout. IATA codes are three-
letter codes used to efficiently identify airports (e.g. the IATA code for
Toronto Pearson International Airport is YYZ).
Python sets
So far in this course, you’ve seen lists, tuples, and dictionaries. Lists and
tuples are ordered, but dictionaries are not. For example, {1: 2, 3: 4} and
{3: 4, 1: 2} are equal.
Another related type is set. A set is an unordered collection of unique items.
We use curly braces: {1, 2, 3, 4}is a set. As with dictionaries, the order of
elements does not matter: {1, 2, 3, 4} == {3, 4, 2, 1}.
To add and remove items from sets, you use methods set.add and set.remove. You
can iterate over sets using for item in set. You can check the number of items
using the function len. To test for set membership, use item in set.
Each set item is unique:
>>> set1 = {1, 2, 3}
>>> set1.add(1)
>>> set1
{1, 2, 3}
You can also do math with sets!
>>> set1 = {1, 2, 3}
>>> set2 = {2, 1, 4}
>>> set1 - set2
{3}
Those are all the methods and functions that you need for this assignment, but
you can see the full list by typing help(set) in the Python shell.
Our Custom Data Types
You will be working with the following custom data types for this assignment.
These types describe how you will store the airport, route and flight
information. They have been imported for you in the starter code, and you
should use them in your type contracts.
Starter Files
Please download the Assignment 3 Files Download Assignment 3 Files and extract
the zip archive. After you extract the zip file, you should see a similar
directory structure to:
- a3/
- flight_functions.py
- flight_program.py
- flight_reader.py
- flight_types_constants_and_test_data.py
- airports.dat
- routes.dat
- flights.dat
The following paragraphs briefly explain the files you have been given; more
in-depth descriptions appear later in this handout.
Data files
We have provided airports.dat and routes.dat, which were downloaded from the
OpenFlights website though the format has been modified for our assignment.
These files will be discussed in more detail in the “Understanding the
OpenFlights Data Files” section.
Python files you will modify
- flight_reader.py, flight_functions.py
The starter code for your part of this assignment is in these files. These are
the files you will be writing all your assignment code in, and each of these
files will be discussed in more detail in the “What to do ] Part 1” and “What
to do ] Part 2” sections respectively.
Python files you will NOT modify
- flight_types_constants_and_test_data.py
This file should NOT be modified. This file includes the code for creating new
types, data to use in docstrings, and some constants that will be helpful as
you write your code. Types, constants, and test data from this file have
already been imported for you in the starter code. You can use this data in
your docstring examples and other tests if you’d like. - flightdata_program.py
This file should NOT be modified. As with Assignment 1, we are providing some
program code that uses your completed functions so you can see your program in
action. More information about this is in the “The main program” section.
Understanding the OpenFlights Data Files
The data files you will work with in this assignment come from the free
OpenFlights airport and route databases, although they have been modified for
the assignment. The files are included in the starter code as airports.dat and
routes.dat.
Airport Data File: airports.dat
Each line in airports.dat represents one airport. Here is an example line:
1,”Goroka Airport”,”Goroka”,”Papua New Guinea”,”GKA”,”AYGA”,-6.081689834590001,145.391998291,5282,10,”U”,”Pacific/Port_Moresby”,”airport”,”OurAirports”
The file contains the following comma-separated information:
| Name | Index | Description |
|---|---|---|
| Airport ID | 0 | Unique airport identifier (set by OpenFlights) |
| Name | 1 | Name of the airport which may or may not contain the City name. |
| City | 2 | The main city served by the airport. May be spelled differently |
| from Name. | ||
| Country | 3 | Country or territory where the airport is located. |
| IATA | 4 | 3-letter airport IATA code. Null if not assigned/unknown. (Your |
| program will ignore entries that have a Null IATA code: skip those lines as | ||
| you read the file.) | ||
| ICAO | 5 | 4-letter airport ICAO code. Null if not assigned. |
| Latitude | 6 | Decimal degrees, usually to six significant digits. |
| Negative is South, positive is North. | ||
| Longitude | 7 | Decimal degrees, usually to six significant digits. |
| Negative is West, and positive is East. | ||
| Altitude | 8 | In feet. |
| Timezone | 9 | Hours offset from UTC. Fractional hours are expressed as |
| decimals, eg. India is 5.5. | ||
| DST | 10 | Daylight savings time. One of E (Europe), A (US/Canada), S |
| (South America), O (Australia), Z (New Zealand), N (None), or U (Unknown). | ||
| Tz | 11 | Timezone in “tz” (Olson) format, eg. “America/Los_Angeles”. |
| Type | 12 | Type of airport. It could be “airport” for air terminals, |
| “station” for train stations, “port” for ferry terminals, and “unknown” if not | ||
| known. You will be working only with type=airport. | ||
| Source | 13 | Source of this data. You will be working only with |
| source=OurAirports, which comes from [ http://ourairports.com/airports/ | ||
| ](http://ourairports.com/airports/) | ||
| Note that the \N is used for “NULL” (similar to None) to indicate that no | ||
| value is available. | ||
| In the file flight_types_constants_and_test_data.py, we have defined a | ||
| dictionary mapping the name to the index: |
AIRPORT_DATA_INDEXES = { 'Airport ID': 0, 'Name': 1, 'City': 2, 'Country': 3, 'IATA': 4, 'ICAO': 5, 'Latitude': 6, 'Longitude': 7, 'Altitude': 8, 'Timezone': 9, 'DST': 10, 'Tz': 11, 'Type': 12, 'Source': 13 }
Route Data File: routes.dat
routes.dat contains airline routes between airports, one route per line. Here
is an example line:
2B,410,AER,2965,KZN,2990,,0,CR2
| Index | Name | Description |
|---|---|---|
| Airline | 0 | 2-letter (IATA) or 3-letter (ICAO) code of the airline. |
| Airline ID | 1 | Unique airline identifier(set by OpenFlights) |
| Source airport | 2 | 3-letter (IATA) or 4-letter (ICAO) code of the source |
| airport. | ||
| Source airport ID | 3 | Unique OpenFlights identifier for source airport |
| (matches that in airports.dat) | ||
| Destination airport | 4 | 3-letter (IATA) or 4-letter (ICAO) code of the |
| destination airport. | ||
| Destination airport ID | 5 | Unique OpenFlights identifier for destination |
| airport (matches that in airports.dat) | ||
| Codeshare | 6 | “Y” if this flight is a codeshare (that is, not operated |
| by Airline, but by another carrier), and is “\N”, or an empty string | ||
| otherwise. | ||
| Stops | 7 | Number of stops on this flight (“0” for direct) |
| Equipment | 8 | 3-letter codes for plane type(s) generally used on this |
| flight, separated by spaces | ||
| Note that routes are directional, meaning if an airline operates services from | ||
| A to B and from B to A, then both A-B and B-A are listed. And as with | ||
| airports.dat, the special value \N is used for “NULL” to indicate that no | ||
| value is available. | ||
| In the file flight_types_constants_and_test_data.py, we have defined a | ||
| dictionary mapping the name to the index: |
ROUTE_DATA_INDEXES = { 'Airline': 0, 'Airline ID': 1, 'Source airport': 2, 'Source airport ID': 3, 'Destination airport': 4, 'Destination airport ID': 5, 'Codeshare': 6, 'Stops': 7, 'Equipment': 8 }
Flight Data File: flights.dat
flights.dat contains all scheduled flights, one flight per line. Here is an
example line:
1,JFK,YYZ,10.00,4.00
The departure time and duration time are represented as floats e.g. 10.00 =
10:00 AM, 13.50 = 1:30 PM, 0.00 = 12:00 AM
| Index | Name | Description |
|---|---|---|
| Flight ID | 0 | Unique flight identifier represented as an integer. |
| Source airport | 1 | 3-letter (IATA) or 4-letter (ICAO) code of the source |
| airport. | ||
| Destination airport | 2 | 3-letter (IATA) or 4-letter (ICAO) code of the |
| destination airport. | ||
| Departure Time | 3 | The time that the flight is scheduled to depart, in |
| 24 hour time. Assume that timezones are accounted for, i.e. a non-issue. | ||
| Duration | 4 | The time of the flight from the source airport to the |
| destination airport. | ||
| In the file flight_types_constants_and_test_data.py, we have defined a | ||
| dictionary mapping the name to the index: |
FLIGHT_DATA_INDEXES = { "Flight ID": 0, "Source airport": 1, "Destination airport": 2, "Departure time": 3, "Duration": 4, }
Writing Functions
For each function you write in this assignment, remember to follow the
Function Design Recipe Download Function Design Recipe we have been using in
class to write the functions for this assignment.
Docstrings
All functions should have docstrings - you will need to write your own for the
functions we have not provided them for. We will mark some of your docstrings
in addition to your code, so we expect the docstrings to contain a type
contract, a description, and two examples, where appropriate. Include
preconditions when you think they are necessary.
Function input
You can assume all the functions will receive input that satisfies their type
contracts. The files that you will need to read will be properly formed, as
described in this handout. The dictionaries and other inputs to the other
functions will be valid inputs however your functions should deal with
receiving IATA codes for airports that do not appear in your dictionaries as
specified below.
Top Down Design
The top-down design is an approach to designing and implementing the body of a
function. Top-down design has you write down, in English, what the major steps
are to solving the function.
After that, repeatedly select one of the steps. If you know how to directly
translate the English into Python, do so. Otherwise, write a call on a
function (that doesn’t exist yet!) that will do what the English says to do.
Then use the Function Design Recipe to design and write that new function.
When it’s time to write the body of the new function, use top-down design!
Grading
We will be testing and marking each of these functions individually. So, even
if you can’t complete them all, you can earn marks for correctly implementing
some of the functions.
What NOT to do
Before we get started, as you’re working on the assignment, keep these things
in mind:
- Do not add statements that call print, input, or open. (You can use print statements for testing if you want, but you MUST remove unnecessary prints before submitting your assignment because otherwise they will cause our test cases to FAIL.)
- Do not modify or add to the import statements provided in the starter code.
- Do not add any code outside of a function definition.
- Do not use any global variables (other than constants).
- Do not mutate objects unless specified.
What to do
Let’s get started! At a high-level, your next steps are to: - PART 1:
- Open the file flight_reader.py.
- Make sure that the file is in the same directory as all the other starter files provided.
- Complete the three functions in flight_reader.py as specified in the section labeled “Part 1” below.
- Test your Python file by using the Python shell or using the doctests.
- PART 2: Repeat the above for flight_functions.py (complete and test the functions specified in the section below). For this part, we have not provided you with the function docstrings – it is up to you to write these in based on the specifications below. Your docstrings will be graded.
PART 1: flight_reader.py
The purpose of this file’s functions is to read and parse the data files.
Write the function body for the following functions in flight_reader.py.
PART 2: flight_functions.py
The purpose of this file’s functions is to write functions that can be used to
answer the following questions:
- Is there a direct flight from one airport to another?
- Is a sequence of airports a valid way to fly from the first airport in the sequence to the last?
- How many outgoing flights are there for an airport?
- How many incoming flights are there for an airport?
- Which airports are reachable from an airport in a particular number of direct flights?
- How long would it take to go from one airport to another when taking a specific set of flights?
In the starter code file flight_functions.py, complete the following function
definitions. Remember to write complete docstrings for all functions that need
it as well. We recommend that you work on them in the following order.
Helpful algorithm tips
Algorithm: reachable destinations in a maximum number of flights
Use this algorithm to find the reachable airports from a source airport. This
builds a list of sets, where a set at index i represents the airports that are
reachable in i direct flights.
Definitions:
- iata_src
The IATA code for the source airport. - routes
The RouteDict to use. - n
The maximum number of direct flights that the algorithm should consider. - reachable_list
The resulting list.
- Create variable reachable_list with a single set containing iata_src. Notice that iata_src is reachable in 0 direct flights, and the set that contains it is at index 0 in the list.
- For each distance d between 1 and the n:
* Get the set of airports at distance d - 1. Find the set of destinations that are reachable in a direct flight from any of those airports.
* Once you have that set, subtract any destinations that are already reachable: the ones in reachable_list[0:d-1]. Remember that you can subtract one set from another. You’re left with exactly the set of airports that are reachable in distance d!
* Append that set to reachable_list.
Algorithm: Calculating Trip Time
Use this algorithm to calculate the trip time when travelling from a source
airport to a destination airport on a provided path.
Definitions:
- iata_src
The IATA code for the source airport. - iata_dst
The IATA code for the destination airport. - flight_walk
A list representing the path of the trip, containing IATA codes representing
airports. - flights
A FlightDir object, as described in “Our Custom Data Types” section above.
- Verify the inputs
- Create variable time and current_src to keep track of the total time elapsed and the airport from which we’re travelling from.
- For each airport in flight_walk between index 1 and the end:
* Calculate the current time of day
* Get the earliest flight from current_src and airport during the same day (based on current time)
* If there is none, get the earliest flight tomorrow.
* Adjust the time and current_src after taking that flight
Testing your Code
It is strongly recommended that you test each function as you write it. This
will make your life easier if you write 2-3 lines of code, then test, you know
where to look for your bug! If you wait until you’ve written a whole lot of
code, it’s harder to figure out where to look.
As usual, follow the Function Design Recipe Download Function Design Recipe.
Once you’ve implemented a function, run it on the examples in your docstring.
Here are a few tips:
- Can you think of any special cases for your functions? Will each function always work, or are there special cases to consider? Test each function carefully.
- Once you are happy with the behaviour of a function, move to the next function, implement it, and test it.
The main program
We provide a main program flight_program.py that you can optionally use to
visualize the information returned by some of your functions. You will not
submit this file, and you do not have to make any changes to it.
You can run this file once you have written all the function headers. Keep in
mind that the buttons won’t work properly until you have completed the
relevant functions.
Marking
Your functions should perform as specified. Correctness, as measured by our
tests, will count for the largest single portion of your marks. Once your
assignment is submitted, we will run additional tests, not provided in the
checker.
Make sure that you follow Python style guidelines that we have introduced and
the Python coding conventions that we have been using throughout the semester,
although we don’t provide an exhaustive list of style rules. Docstrings may be
evaluated separately, and we may look for use of helper functions.
Your program should be broken down into functions, both to avoid repetitive
code and to make the program easier to read. If a function body is more than
about 20 statements long, introduce helper functions to do some of the work –
even if they will only be called once.
All functions, including helper functions, should have complete docstrings
including preconditions when you think they are necessary.
Also, your variable names and names of your helper functions should be
meaningful. Your code should be as simple and clear as possible.
No Remark Requests
No remark requests will be accepted. A syntax error could result in a grade of
0 on the assignment. Before the deadline, you are responsible for running your
code and the checker program to identify and resolve any errors that will
prevent our tests from running.
What to Submit
The very last thing you should do before submitting is to run the files to
make sure they run without errors. Otherwise, you could make a small error in
your final changes before submitting that causes your code to receive zero.
After submitting, please check the submitted files to make sure you have
submitted the correct files.
For this assignment, you will hand in two files on MarkUs:
- flight_reader.py: This should contain your implementations of the two required functions for reading files, and any helper functions that you have written for them.
- flight_functions.py: This should contain implementations of the remaining required functions, and any helper functions that you have written for them.
Once you have submitted, be sure to check that you have submitted the correct
version; new or missing files will not be accepted after the due date.
Remember that spelling of filenames, including case, counts. If your file is
not named exactly as above, your code will receive zero for correctness
