Assignment 3: Airports and Routes
Due Date: Tuesday, April 3 before 9:00pm
Introduction
Update 10:30pm Mon 19 Mar: Please redownload airports.dat and routes.dat; see the read_. The starter code zip file csc108a3.zip has also been updated, so if you start after this was posted you already have the new files.
The purpose of this assignment is to give you practice with
understanding a complicated realworld problem domain. The Python content involves file reading, building and using dictionaries, learning to use sets, designing algorithms, designing functions, and writing unit tests.
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 has you use the 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 the flight data. OpenFlights on GitHub is an open source project.Airports have two types of codes: IATA and ICAO, issued by two different organizations. We will use the IATA code throughout.
Reminder: How to not be interviewed for an academic offence
We are very good at detecting cheating. We hate finding it, though, so we have written this short guide on how to avoid being interviewed by us for an academic offence. Here’s the article we linked to on the Assignment 2 handout, about why we are good at detecting cheating.
Our tips:
Remember that figuring out what code needs to be written is the most important part of the assignment. Typing out code based on steps that someone else gave you is considered cheating, as you are submitting someone else’s ideas as your own.
Don’t search the web for solutions. We’ve already done that and will be comparing what we found with what you submit. It doesn’t help to change variable names and move functions around. Our software will still find you.
Don’t ask your friend for their solution, even if you just want it to “see how to solve it”. Don’t show your friends your solution either.
Don’t get solutions, or partial solutions, from a tutor. They frequently provide the same code or ideas to more than one person. We know because we frequently catch people who do it.
Only ask for detailed help on your code from official CSC108 course staff, including the Help Centre.
If you can’t figure out how to write a function, it’s often because you haven’t fully understood an underlying concept. Review the materials on that topic, experiment in the Python shell, and ask us for help!
Remember that it is better to submit an assignment with a few missing functions than to cheat!
Questions you will answer
Here are the questions that you will write functions to answer: 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 n airports have the most total flights, where n is chosen by the user?
Which airports are reachable from an airport in a particular number of direct flights?
Files to Download
Please download the Assignment 3 Files and extract the zip archive. The following paragraphs briefly explain the files you have been given; more indepth descriptions appear later in this handout.
1.Python Code
- The starter code for your part of this assignment is in the files flight_reader.py and flight_functions.py. These files will be discussed in more detail in the "What to do" section.
- As with previous assignments, we are providing some program code that uses your completed functions in flightdata_program.py. You can read more about this file in the section titled "The main program". This file should not be modified.
- There is also some code for creating new types, data to use in docstrings and the checker, and some constants that will be helpful in flight_types_constants_and_test_data.py. Types, constants, and test data from this file has been imported for you in the starter code. You can use this data in your docstring examples and other tests, if you’d like. This file should not be modified.
- The starter code for the required unittests is in the file test_is_valid_flight_sequence.py. This file will be discussed in more detail in the "What to do" section.
2.Data files
- We have provided airports.dat and routes.dat, which were downloaded from the OpenFlights website. These files will be discussed in more detail in the next section.
checker.py - As with the previous assignments, we have provided a checker. Hopefully you have got into the habit of running it regularly!
- The checker tests two things:
- whether your functions have the correct parameter and return types, and whether your code follows the Python and CSC108 style guidelines.
- Reminder: we use the same style checker for the majority of the style marking of your code!
Understanding the OpenFlights Data Files
The data files you will work with in this assignment come from the free OpenFlights airport and route databases. The files are already 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:
193,”Lester B. Pearson International Airport”,”Toronto”,”Canada”,”YYZ”,”CYYZ”,43.6772003174,-79.63059997559999,569,-5,”A”,”America/Tor
The file contains the following commaseparated information:
In the file flight_types_constants_and_test_data.py, we have defined a dictionary mapping the name to the index:
'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:
AA,24,JFK,3797,YYZ,193,Y,0,CR7
Note that routes are directional, meaning if an airline operates services from A to B and from B to A, then both AB and BA 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:
'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
}```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 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}
set1 = {1, 2, 3}
set1.add(1)
set1
{1, 2, 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.
Airport and Route Dictionaries
You will be working with the following new types. These types describe how you will store the airport and route information. They have been imported for you in the starter code, and you should use them in your type contracts.
What to do
Follow the Function Design Recipe we have been using in class to write the functions in the tables below. 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.
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.
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.
On all functions, we recommend you come up with some small examples to test with before you try testing with the data in
airports.dat and routes.dat.
File flight_reader.py: reading the data files
Write the following functions in flight_reader.py:
File flight_functions.py: answering the questions at the top of this handout
In starter code file flight_functions.py, complete the following function definitions. We recommend that you work on them in this order.
Unittest file: test_is_valid_flight_sequence.py
This file contains a single unit test. Write more tests to thoroughly test function is_valid_flight_sequence, without redundant tests. We will run your tests on flawed versions of this function.
Algorithm: reachable destionations 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.
1. 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.
2. For each distance d between 1 and the n:
1. 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.
2. 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!
3. Append that set to reachable_list.
Top Down Design
As discussed in Week 8 in the worksheets/Rehearse exercise for the random story program, topdown design is an approach to designing and implementing the body of a function.
Topdown 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 topdown design!
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. Once you’ve implemented a function, run it on the examples in your docstring. Here are a few tips:
-
Keep in mind the materials we discussed in Week 9 about choosing tests — how do order, dichotomies, size, and boundaries apply to your functions here?
-
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 flights_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.
When you run the program, it will look like this:
Provided that you have written all the function headers, you can start to use this, although of course the buttons won’t work properly until you have completed the relevant functions.
Additional requirements
- Do not add statements that call print, input, or open. Do not modify or add to the import statements provided in the starter code.
- Do not use any break or continue statements.
- Do not add any code outside of a function definition or the if name == ‘ main ‘ block. Do not use any global variables (other than constants).
- Do not mutate objects unless specified.
- Do not use method sort’s optional argument key. Do not use function sorted.
Marking
These are the aspects of your work that will be marked for Assignment 3:
Correctness (75%): 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. Passing the checker does not mean that your code will earn full marks for correctness.
Testing (5%): We will run the unittests that you submit on a series of flawed (incorrect) implementations we have written. Your testing mark will depend on how many of the flawed implementations your unittests catch, whether they successfully
pass a working (correct) implementation, and whether your test files contain redundant (unnecessary) tests.
Coding style (20%): 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, the checker tests for style are complete, so if your code passes the checker, then it will earn full marks for coding style with two exceptions: docstrings may be evaluated separately, and we may look for use of helper functions. For each occurrence of a PyTA error, a 1 mark (out of 20) deduction will be applied. For example, if a C0301 (linetoolong) error occurs 3 times, then 3 marks will be deducted.
What to Submit
The very last thing you should do before submitting is to run the checker one last time. Otherwise, you could make a small error in your final changes before submitting that causes your code to receive zero for correctness. If your code does not run, you will get a zero for correctness.
You must hand in your work electronically, using the MarkUs online system. Instructions for doing so are posted on the Assignments page of the course website.
For this assignment, you will hand in three files:
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.
test_is_valid_flight_sequence.py: This should contain your unittest test cases for the is_valid_flight_sequence function.
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.
