Home
Syllabus
Assignments
Tests
Due: 9:00am, Monday, April 12. Value: 30 pts. Submit to Sauron.
The file fares.txt contains several lines, each containing the abbreviation for the starting airport, the abbreviation for the destination airport, and the fare for a direct flight. (These are not real air fares, but rather randomly generated — which is at least reasonably realistic.) As it happens, the file contains all pairs of the 12 busiest U.S. airports, mapped at right.
ATL Atlanta JFK New York City John F. Kennedy DEN Denver LAS Las Vegas DFW Dallas-Fort Worth International LAX Los Angeles DTW Detroit MSP Minneapolis-Saint Paul EWR Newark ORD Chicago O'Hare IAH Houston PHX Phoenix
Sometimes it's cheaper to go through an intermediate airport than to fly direct. For instance, based on the file, a direct flight from Atlanta to Denver costs $293, but it's $88 cheaper to go to Los Angeles ($103) and from there to Denver ($102).
Your job is to find itineraries for which going through an intermediate airport saves you $60 or more off the direct-flight fare. There are eight such itineraries. For each itinerary, display the starting airport, intermediate airport, destination airport, the cost for that itinerary, and the cost for a direct flight.
You don't need to worry about itineraries with two or more intermediate airports. Also, don't worry about finding the best intermediate airport: If you could also save lots of money going through Dallas on the way from Atlanta to Denver, you'd show that, too. (As it happens, you don't save money going through Dallas.) However, you shouldn't display the Atlanta-Los Angeles-Denver itinerary more than once.
I did this by reading the file and creating a dictionary, where each key is a pair of airport abbreviations in a single string, which is mapped to the direct-flight fare. I also created a list of the airport abbreviations:
ports = "ATL DEN DFW DTW EWR IAH JFK LAS LAX MSP ORD PHX".split()To iterate through all possible itineraries, I created three loops, checking to ensure that no two of the airports are the same:
for start in ports:
for inter in ports:
for dest in ports:
if start != dest and start != inter and inter != dest:And from there I used the dictionary to compute the direct-flight cost and the intermediate-flight cost.