Assignment 2: D airfares
Due: 5:00pm, Friday, October 4. Value: 30 pts.
D language links:
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 actual airfares collected from Kayak Explore.) The file contains all pairs of the 12 busiest U.S. airports.
ATL Atlanta LAS Las Vegas CLT Charlotte LAX Los Angeles DEN Denver MIA Miami DFW Dallas-Fort Worth (International) ORD Chicago (O'Hare) IAH Houston (Bush Intercontinental) PHX Phoenix JFK New York City (John F. Kennedy) SFO San 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; below are four 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
I started this by creating a list of the airport abbreviations:
ports = split("ATL CLT DEN DFW IAH JFK LAS LAX MIA ORD PHX SFO");
Then I read the file and created
an associative array of type uint[string]
,
where each key is a pair of airport abbreviations in a single string.
(You can append strings together using the binary ~
operator:
“src ~ dst
”.) The below illustrates how you
can read through a file using the File
type from
std.stdio
.
fin = File("fares.txt", "r");
foreach (line; fin.byLine) {
writeln(line.length);
}
fin.close();
Finally, I created three nested loops to iterate through all possible itineraries. Here is pseudocode written in Python.
for start in ports:
for dest in ports:
if start != dest:
# direct = fare from start to dest
# best = direct
for interm in ports:
if interm != start and interm != dest:
# see if going through interm is better than best
if best <= direct - 50:
# display output line
To execute a D program on the lab computers, you can enter
“rdmd filename.d
”.