完成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/ |
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