CSci 150: Foundations of computer science
Home Syllabus Readings Projects Tests

Project 1: Airfares

Due: 5:00pm, Thursday, May 1. Value: 40 pts.

Collaboration policy

The class exercises have a liberal policy, where you are allowed to freely discuss the concepts with your teammate. This is not allowed for projects, however. You are to work on your own. From the syllabus:

Discussing or viewing others' solutions to projects is officially out of bounds, as is discussing or showing your own solution to others. In practice, I realize, you may help other students; this presents a problem only when your help leads to another student's solution having some substantial similarity to your own. Any correlation between your solution and a classmate's solution constitutes evidence of cheating.

Except… you are permitted to choose one classmate with whom you will collaborate for this project. You and your partner will jointly submit your solution on your own. Only one of you should submit a solution; be sure to include a comment at the beginning of the solution that identifies both people participating in the project.

Assignment

The file fares.txt contains several lines representing airfares, each containing three tab-separated values: the abbreviation for the starting airport, the abbreviation for the destination airport, and the fare for a flight from the first to the second. (These are actual airfares collected from Kayak Explore.) The file contains all pairs of the 12 busiest U.S. airports.

ATLAtlanta    LASLas Vegas
CLTCharlotte    LAXLos Angeles
DENDenver    MIAMiami
DFWDallas-Fort Worth (International)    ORDChicago (O'Hare)
IAHHouston (Bush Intercontinental)    PHXPhoenix
JFKNew York City (John F. Kennedy)    SFOSan Francisco

Sometimes it's cheaper to buy two tickets via an intermediate airport than to a direct ticket. For instance, based on the file, a ticket from Las Vegas to Denver costs $365, but you can save $165 by getting a ticket from Las Vegas to Los Angeles ($64) and from there to Denver ($136).

Your job is to write a program finding itineraries for which buying two tickets via an intermediate point would save $50 or more off the fare. (If there are multiple such intermediate points, your program should display the one saving the most.) There are seven such cases for this specific file; below are three of the desired output lines.

CLT-DEN: $375 direct; $321 via DFW; save $54
CLT-LAX: $348 direct; $296 via LAS; save $52
LAS-DEN: $365 direct; $200 via LAX; save $165

The order in which the lines are displayed is not significant, but the format of each individual line should match what is above. Of course, your program should work for similarly formatted files, even if the file deals with different sets of airports.

Hint

I would accomplish this by creating two structures:

  1. The first identifies what airports are mentioned in the file. It would be a dictionary whose keys are the individual airport names; the value associated with each key would be unimportant, so personally I'd use True.
  2. The second would store all the airfares. Each key would be a tuple of two strings — the source airport and then the destination airport — whose corresponding value would be the airfare.

After processing the whole file to build these two structures completely, I'd have a set of three nested loops: The first might iterate through all possible source airports, the second the possible destination airports, and the third the possible intermediate stops we might use. Going through the innermost loop (over intermediate stops), you would want a best-so-far variable identifying which intermediate stop results in the best total fare between the current source and destination.

Installing Python

While you could accomplish this project through Hydra, I recommend developing the program on your own computer. To do this, navigate to Python.org's Downloads page. Be sure to download and install a version of the form 3.x.y.

(The older versions 2.x.y are not entirely compatible with what we've studied in this course, though Python still maintains it since many older programs continue to use it. For this class, though, programs written for 2.x.y are considered wrong.)

The install program will include a program named IDLE, which allows you to develop a Python program interactively.

(By the way, if you want something more sophisticated than IDLE, you might consider PyCharm. Installation is more complex, though, so I'm recommending IDLE myself.)

Once you have completed your program, you can submit your solution via copy-and-paste to Hydra.