CSC108: Introduction to Computer Programming - Assignment 3: Airports and Routes
Airports and Routes
In this assignment, we will be working with two types of data:
1. Airport Data
2. Routes Data
Airport Data
Airports connect cities all over the world. Airports have two types of codes: IATA and ICAO, issued by two different organizations. We will use the IATA airport code throughout this assignment. IATA codes are three-letter codes used to quickly differentiate between airports. For example, Los Angeles, USA has the code LAX. In contrast, Los Angeles, Chile has the code LSQ.
Each row of the table contains information about an airport. And each column of the table represents a “feature” of that airport. An example of a feature from the data could be the name of the city that the airport serves. If you would like to take a peek at the data, we recommend opening the files with a spreadsheet program (e.g., Excel) rather than using Wing 101.
Route Data
A route is a direct flight that can take you from one airport to another. The airport that you start from is called the source. The airport that you arrive at is called the destination. Both the source and the destination are expressed as IATA airport codes. For example, a route from Toronto, Canada to New York, USA could be expressed as YYZ to LGA. Note that some cities have multiple airports. For example, New York has two: LGA and JFK.
Depending on several variables (e.g., distance, capacity, airline, etc), different types of planes are used for different routes. Planes are represented as three-character alphanumeric codes (e.g., 787 or CR7). Every route has at least one plane that is typically used to fly between its source and destination. For example, the route from YYZ to LGA uses a CR7 planeLinks to an external site.. But a flight from YYZ to ORD (Chicago’s O’Hare International Airport) could use a CR7, E75Links to an external site., or ER4Links to an external site..
What to do
After you have read this handout, you should start by downloading the starter files. This assignment is divided into four parts. And each part is described in more detail in this handout.
Starter Files
The Assignment 3 Files are available for download on MarkUsLinks to an external site.. Log in to MarkUsLinks to an external site. and click on Assignment3: Assignment 3 Airports and Routes in the list of Upcoming Assessments. Then click on the Download Starter Files button at the bottom of the Assignment3 tab. Extract the files from the zip archive that has been downloaded. (Your browser may have automatically extracted the files.) You may be able to view the files without opening the zip archive, but you will not be able to save anything. Ensure that you can see individual filenames in the folder listing. It is recommend that you make a copy of the Assignment 3 folder outside of your Downloads folder and modify the copied files when doing your work. Keep all of the Assignment 3 Files in the same folder.
After you extract the zip file, you should see a similar directory structure to:
a3/
├─── pyta/
├─── a3_pyta.txt
├─── data/
├─── airports.csv
├─── routes.dat
├─── flight_constants.py
├─── flight_example_data.py
├─── flight_functions.py
├─── flight_reader.py
├─── test_flight_functions.py
The Python files are described below:
· flight_constants.py
This includes constants that are useful across multiple Python files. You will not modify or submit this file.
· flight_example_data.py
This includes functions that return sample data. The sample data can be used in doctest examples. You will not modify or submit this file.
· flight_functions.py
This is one of the files where you will write your solution. Your job is to complete the file by implementing all the required functions.
· flight_reader.py
This is one of the files where you will write your solution. Your job is to complete the file by implementing all the required functions.
· test_flight_functions.py
This is one of the files where you will write your solution. Your job is to complete the file by writing unit tests.
Part 1
In Part 1, you will implement two functions that read and store data.
1. read_airports(TextIO) -> AirportDict
2. read_routes(TextIO, AirportDict) -> RouteDict
Before you start programming, read the rest of Part 1. Here are some useful tips:
· See the Dictionaries in dictionaries section to understand how to use nested dictionaries
· See the Type Annotations section to understand what RouteDict and AirportDict are
· Review the “Reading Files” module from Week 7 on PCRS for help
· Review the “Populating a Dictionary” module from Week 7 on PCRS for help
· Review the “Structured Files” module from Week 7 on PCRS for help
Open flight_reader.py and complete the functions that are missing bodies. We have provided you with the function headers, docstring description, and doctest examples for the functions you need to implement; you do not need to add or change them. The focus of Part 1 is implementing the bodies of these functions and testing them. The rest of this section contains more information to help you implement the two functions.
Reading and storing airport data
The data comes from the file data/airports.csv. Below is a table describing every feature in the data.
Feature Name | Constant to use as Index | Description |
IATA | INDEX_AIRPORTS_IATA | 3-letter airport IATA code. |
Name | INDEX_AIRPORTS_NAME | Name of airport which may or may not contain the City name. |
City | INDEX_AIRPORTS_CITY | Main city served by airport. May be spelled differently from Name. |
Country | INDEX_AIRPORTS_COUNTRY | Country or territory where airport is located. |
Latitude | INDEX_AIRPORTS_LATITUDE | Decimal degrees, usually to at least six significant digits. Negative is South, positive is North. |
Longitude | INDEX_AIRPORTS_LONGITUDE | Decimal degrees, usually to at least six significant digits. Negative is West, positive is East. |
Tz | INDEX_AIRPORTS_TZ | Timezone in tz (Olson) formatLinks to an external site., eg. “America/Los_Angeles”. |
Please note that each value in the csv file is surrounded by the double-quote character ("). You will need to remove these double-quote characters first by, for example, using str.replace. After you have removed the quotes, you can use the str.split method to divide the line up into a list of values. You should not be splitting each line by white space, but rather by comma (hence the “comma” in comma-separated value file). For example:
>>> # let line refer to the data for the YYZ airport in Toronto
>>> line.replace('"', '').strip().split(',')
['YYZ', 'Lester B. Pearson International Airport', 'Toronto', 'Canada', '43.6772003174', '-79.63059997559999', 'America/Toronto']
We will store airport data as a dictionary of dictionaries. The outer dictionary will have keys that are IATA airport codes. Each airport code will map to a dictionary (i.e., the inner dictionary). Each inner dictionary will have keys that are “features” of the airport (e.g., the name of the airport, the city it serves, etc.).
Here is an example airport dictionary with two airports:
handout_airports = {
'GFN': {
'City': 'Grafton',
'Country': 'Australia',
'Latitude': '-29.7593994140625',
'Longitude': '153.02999877929688',
'Name': 'Grafton Airport',
'Tz': 'Australia/Sydney'
},
'JCK': {
'City': 'Julia Creek',
'Country': 'Australia',
'Latitude': '-20.66830062866211',
'Longitude': '141.72300720214844',
'Name': 'Julia Creek Airport',
'Tz': 'Australia/Brisbane'
}
}
In the example, handout_airports is the outer dictionary and it has two keys: 'GFN' and 'JCK'. Each key maps to an inner dictionary. Each inner dictionary has keys: 'City', 'Country', 'Latitude', 'Longitude', 'Name', and 'Tz'.
Reading and storing route data
We will store route data as a dictionary of dictionaries. The outer dictionary will have keys that are IATA airport codes. These keys represent the source of the route. Each source will map to a dictionary (i.e., the inner dictionary). Each inner dictionary will have keys that are IATA airport codes. These keys represent the destination of the route. Each destination will map to a list of strings. Each list contains the three-character alphanumeric code of the planes that can be used for that route.
The data comes from the file data/routes.dat. It is stored as a structured plaintext file. Below is an example of a correctly structured file.
SOURCE: RCM
DESTINATIONS BEGIN
JCK SF3
DESTINATIONS END
SOURCE: TRO
DESTINATIONS BEGIN
GFN SF3
SYD SF3 DH4
DESTINATIONS END
The example above tells us that:
· There is a route where 'RCM' is the source and 'JCK' is the destination. And that route uses an 'SF3' plane.
· There is a route where 'TRO' is the source and 'GFN' is the destination. And that route uses an 'SF3' plane.
· There is a route where 'TRO' is the source and 'SYD' is the destination. And that route can use an 'SF3' or a 'DH4' plane.
The resulting routes dictionary would look like:
handout_routes = {
'RCM': {'JCK': ['SF3']},
'TRO': {'GFN': ['SF3'], 'SYD': ['SF3', 'DH4']}
}
Note that the list of planes appear in the same order as they did in the data.
When reading the data, you can assume that:
· The very first line begins with SOURCE: followed by a three-letter IATA airport code.
· The line after every line that begins with SOURCE: is DESTINATIONS BEGIN
· There are one or more lines between DESTINATIONS BEGIN and DESTINATIONS END
· After every line with DESTINATIONS BEGIN there will be a corresponding line with DESTINATIONS END
· The lines between DESTINATIONS BEGIN and DESTINATIONS END start with a three-letter IATA airport code, which is followed by one or more three-character alphanumeric plane codes. Each code is separated by a space.
· The lines after DESTINATIONS END will begin with SOURCE:, or you will have reached the end of the file.
Part 2
In Part 2, you will design three functions using the Function Design Recipe. We have included the type contract and specification of every function that you are to write below; please read through them carefully.
We will be evaluating your docstrings in addition to your code. Include at least two examples that call the function you are designing in your docstring. The docstring examples must be formatted correctly to be interpreted by the doctest module. You may find the provided examples from Parts 1 and 3 to be a useful reference.
You will need to paraphrase the specifications of the functions to get an appropriate docstring description. Make sure you review the CSC108 Python Style Guidelines for the rules on how to write a docstring description.
Here are some useful tips:
· Follow the Function Design Recipe to complete these functions
· Your docstring description should paraphrase the specification. Do not copy paste it
· Your docstring examples must all be formatted correctly to work with the doctest module
· You must not mutate the arguments of these functions
Open flight_functions.py and design the following functions according to their specification.
(The function numbering is a continuation of the numbering from Part 1.)
3. is_direct_flight(RouteDict, str, str) -> bool
Specification: The first parameter represents route information, the second parameter represents the IATA code for a source airport, and the third parameter represents the IATA code for a destination airport. This function returns whether there is a direct flight from the source airport to the destination airport in the given route information.
If the IATA code for the source airport does NOT appear in the route information, the function should return False.
For Example: Refer to the handout_routes dictionary from Reading and storing route data. There is a direct flight from 'RCM' to 'JCK'. But there is not a direct flight from 'JCK' to 'RCM'.
4. is_valid_flight_sequence(RouteDict, list[str]) -> bool
Specification: The first parameter represents route information and the second parameter represents a list of IATA codes. Determine whether the sequence of IATA codes is valid: that there is a direct flight between each adjacent pair of IATA codes, based on the given route information. Return True if the sequence of flights is a valid route, or False otherwise.
Note that it is possible for one or more of the IATA codes provided in the flight sequence to be invalid (i.e., the code does not appear in the given route information). This is considered an invalid flight sequence.
A valid flight sequence requires at least two IATA codes. Otherwise it is considered an invalid flight sequence.
For Example: Refer to the handout_routes dictionary from Reading and storing route data. There is a valid flight sequence from 'RCM' to 'JCK' because there is a direct flight in handout_routes. There is not a valid flight sequence from 'RCM' to 'JCK' to 'TRO' because there is no direct flight between 'JCK' and 'TRO'. The adjacent pairs in the invalid flight sequence are: 'RCM' and 'JCK'; 'JCK' and 'TRO'.
5. summarize_by_timezone(AirportDict) -> dict[str, int]
Specification: This function’s parameter represents airport information. This function returns a dictionary mapping timezones (i.e., the tz (Olson) format) to the number of airports in that timezone. This function ignores the airports whose timezone is a Null value. See the Missing Data section for help on Null values.
For Example: Refer to the handout_airports dictionary from Reading and storing airport data. There is one airport, 'GFN', in the 'Australia/Sydney' timezone. There is one airport, 'JCK', in the 'Australia/Brisbane' timezone.
Part 3
In Part 3, you will implement two useful algorithms that work with the route data:
6. find_reachable_destinations(RouteDict, str, int) -> list[str]
7. decomission_plane(RouteDict, str) -> list[tuple[str, str]]
You are encouraged to follow the top-down design approach introduced to you in Week 9. You will likely want (or need) to design a helper function for one or both of the algorithms.
Open flight_functions.py and complete the functions that are missing bodies. We have provided you with the function headers, docstring description, and doctest examples for the functions you need to implement; you do not need to add or change them. The focus of Part 3 is implementing the bodies of these functions and testing them.
Finding reachable destinations
Let us expand one of the doctest examples:
>>> find_reachable_destinations(example_routes, 'GFN', 2)
['GFN', 'SYD', 'TRO']
The maximum number of direct flights in this example is 2 and example_routes is:
{
'GFN': {'TRO': ['SF3']},
'JCK': {'RCM': ['SF3']},
'RCM': {'JCK': ['SF3']},
'TRO': {'GFN': ['SF3'], 'SYD': ['SF3', 'DH4']}
}
1. If we start at 'GFN', then there is only one possible direct flight to 'TRO'. So we should accumulate 'TRO' and move on to the next step.
2. If we were to “fly” to 'TRO', then we are now (hypothetically) at the 'TRO' airport. This means, based on example_routes, we can reach two other airports via another direct flight: 'GFN' (where we just came from) and 'SYD'. So we should accumulate both 'GFN' and 'SYD' and move on to the next step.
3. After “flying” to either 'GFN' or 'SYD', we have taken the maximum number of direct flights in the example (i.e., 2). So we should stop and then return what we have accumulated.
Suppose the maximum number of flights was not 2 but 3. Would the result be different? In this specific example (i.e., example_routes), no. The airport 'SYD' is not a source in example_routes, only a destination. And the 'GFN' airport already had its destinations ('TRO') accumulated. Remember that the docstring explicitly says:
The list should not contain an IATA airport code more than once.
In a more complex example, like the large data set loaded from the file, the number of reachable destinations returned would likely be much larger than in our small doctest example.
Decomissioning planes
Sometimes planes have manufacturing defects and need to be grounded until the defect is resolved. Let us expand one of the doctest examples:
>>> decomission_plane(example_routes, 'DH4')
[]
The plane to be decomissioned has code 'DH4' and example_routes is:
{
'GFN': {'TRO': ['SF3']},
'JCK': {'RCM': ['SF3']},
'RCM': {'JCK': ['SF3']},
'TRO': {'GFN': ['SF3'], 'SYD': ['SF3', 'DH4']}
}
We need to check the planes of every source-destination pair in example_routes. Let’s go in the order we see them above:
1. The 'GFN' to 'TRO' flight uses planes: ['SF3']. Because 'DH4' does not appear in the list of planes, the list is not mutated. Because this route’s list of planes is not empty, nothing is accumulated.
2. The 'JCK' to 'RCM' flight uses planes: ['SF3']. Because 'DH4' does not appear in the list of planes, the list is not mutated. Because this route’s list of planes is not empty, nothing is accumulated.
3. The 'RCM' to 'JCK' flight uses planes: ['SF3']. Because 'DH4' does not appear in the list of planes, the list is not mutated. Because this route’s list of planes is not empty, nothing is accumulated.
4. The 'TRO' to 'GFN' flight uses planes: ['SF3']. Because 'DH4' does not appear in the list of planes, the list is not mutated. Because this route’s list of planes is not empty, nothing is accumulated.
5. The 'TRO' to 'SYD' flight uses planes: ['SF3', 'DH4']. Because 'DH4' does appear in the list of planes, the list is mutated so that it becomes: ['SF3']. Because this route’s list of planes is still not empty, nothing is accumulated.
Since nothing was ever accumulated, the list returned is empty. However, we did mutate example_routes. It is now:
{
'GFN': {'TRO': ['SF3']},
'JCK': {'RCM': ['SF3']},
'RCM': {'JCK': ['SF3']},
'TRO': {'GFN': ['SF3'], 'SYD': ['SF3']}
}
Also notice that the length of example_routes is four. But it took us five steps to complete the algorithm. This is because we are not just looking at every source, we are looking at every source-destination pair.
Part 4
In Part 4, you will implement unit tests that test the summarize_by_timezone and is_valid_flight_sequence functions. Open test_flight_functions.py and complete the unit tests.
8. Unit tests for the summarize_by_timezone function.
Notes:
o We have already completed one of the tests, test_no_airports for you. You do not need to change it. But you may use it as a reference.
o We have provided some code to get you started on test_only_null_airports. You must complete this test case according to its description.
o We have provided some code to get you started on test_no_mutation You must complete this test case according to its description.
§ Review the “Testing Functions that Mutate Values” module from Week 8 on PCRS for help
o You do not need to add any additional test cases to TestSummarizeByTimezone.
9. Unit tests for the is_valid_flight_sequence function.
Notes:
o We have already completed one of the tests, test_one_valid_direct_flight for you. You do not need to change it. But you may use it as a reference.
o You must add additional test cases on your own.
o Highly Recommended: Review the “Choosing Test Cases” module from Week 8 on PCRS for help.
Testing Your Solutions
The last step in the Function Design Recipe is to test your function. At the bottom of the flight_reader.py and flight_functions.py file, you will find:
if __name__ == '__main__':
# On A3 we do not have a separate checker but instead include code that
# performs the required checks. This code requires python_ta to be
# installed. See the 'Completing the CSC108 Setup' section in the
# Software Installation page on Quercus for details.
# Uncomment the 3 lines below to have function type contracts checked
# # Enable type contract checking for the functions in this file
# import python_ta.contracts
# python_ta.contracts.check_all_contracts()
# Check the correctness of the doctest examples
import doctest
doctest.testmod()
# Uncomment the 2 lines below to check your code style with python_ta
# import python_ta
# python_ta.check_all(config='pyta/a3_pyta.txt')
This means that, when you uncomment lines and run the file, python_ta will check your type contracts whenever you call one of your function. This includes the function calls made by the doctest module when it automatically runs the examples. Finally, python_ta will also check your code for style.
For example, running the flight_reader.py starter file before you make any changes will result in output similar to the excerpt below. Pay close attention to the AssertionError messages that indicate you have violated a type annotation.
[evaluate flight_reader.py]
**********************************************************************
File "path/to/a3/flight_reader.py", line 51, in __main__.read_airports
Failed example:
actual = read_airports(example_airport_file)
Exception raised:
Traceback (most recent call last):
File "Path\To\Python\Versions/3.11/lib/python3.11/doctest.py", line 1353, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.read_airports[1]>", line 1, in <module>
actual = read_airports(example_airport_file)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "Path\To\Python\Versions/3.11/lib/python3.11/site-packages/python_ta/contracts/__init__.py", line 96, in _enable_function_contracts
raise AssertionError(str(e)) from None
AssertionError: read_airports's return value None did not match return type annotation dict[str, dict[str, str]]
**********************************************************************
File "path/to/a3/flight_reader.py", line 52, in __main__.read_airports
Failed example:
actual == flight_example_data.create_example_airports()
Exception raised:
Traceback (most recent call last):
File "Path\To\Python\Versions/3.11/lib/python3.11/doctest.py", line 1353, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.read_airports[2]>", line 1, in <module>
actual == flight_example_data.create_example_airports()
^^^^^^
NameError: name 'actual' is not defined
**********************************************************************
File "path/to/a3/flight_reader.py", line 69, in __main__.read_routes
Failed example:
actual = read_routes(example_routes_file, example_airports)
Exception raised:
Traceback (most recent call last):
File "Path\To\Python\Versions/3.11/lib/python3.11/doctest.py", line 1353, in __run
exec(compile(example.source, filename, "single",
File "<doctest __main__.read_routes[2]>", line 1, in <module>
actual = read_routes(example_routes_file, example_airports)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "Path\To\Python\Versions/3.11/lib/python3.11/site-packages/python_ta/contracts/__init__.py", line 96, in _enable_function_contracts
raise AssertionError(str(e)) from None 56
57 def read_routes(routes_data: TextIO, airports: AirportDict) -> RouteDict:
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
58 """Return a routes dictionary based on the data in the open file
59 referred to by routes_data and given airports dictionary.
[Line 57] The parameter 'airports' is unused. This may indicate you misspelled a parameter name in the function body. Otherwise, the parameter can be removed from the function without altering the program.
55
56
57 def read_routes(routes_data: TextIO, airports: AirportDict) -> RouteDict:
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
58 """Return a routes dictionary based on the data in the open file
59 referred to by routes_data and given airports dictionary.
[INFO] File: path/to/a3/flight_reader.py was checked using the configuration file: pyta/a3_pyta.txt
[INFO] File: path/to/a3/flight_reader.py was checked using the messages-config file: Path\To\Python\Versions/3.11/lib/python3.11/site-packages/python_ta/config/messages_config.toml
