Project 1

Updates:

• Feb 1 - Added project zip archive, reference output for Part 3, and submission instructions.
• Jan 30 - Clarified there should be an extra newline after the flight duration in part 3.
• Jan 28 - The project is now due Fri, Feb 11.
• Jan 27 - Clarified times in validate need to be 24-hour times.
• Jan 26 - Fixed sort order for nonstop command; clarified that flight numbers have no leading zeros.

Introduction

Among other things, Ruby and similar languages are very useful for writing ad hoc scripts to process and analyze data such as web logs (e.g., to find what pages are the most requested on your web site), operating system logs (e.g., to look for alerts that might signal ongoing problems), network traffic logs (e.g., to detect attacks from remote entities), and so on. In this project, you will write a program that works with airline timetable data to carry out a variety of tasks.

The timetable data is stored in a text file in which each line represents the information about one flight. The information is a list of comma-separated values that are, from left to right: the flight number, the departure airport code, the arrival airport code, the departure time, and the arrival time. For example, here are two lines from the sample data file included in the project:

424,IAD,BOS,1221,1350
49,IAD,LAX,1220,1807

In this project, you will write one script, schedule.rb, that performs a variety of tasks depending on the the command-line arguments. We will invoke your script as

Where timetable-file-name is the name of the file containing the timetable, feature-name is the name of the features, and args... are the arguments needed for that particular feature, if any. The various features that you need to implement are listed below.

Getting Started

Download the following zip archive p1.zip. It should include the following files:

• Your Ruby program - schedule.rb
• A sample timetable - flights.csv
• Test inputs directory - inputs
• Test outputs directory - outputs
• Scripts used in public tests - public_*.rb test*.rb

You should do all of your work in schedule.rb. You could use each public_*.rb to run the same public tests as on the submit server. Your outputs will be store in student_outputs. For example:

% ruby public_validate.rb
test validate on correct-empty PASSED
test validate on correct-flights PASSED
test validate on correct-small PASSED
test validate on wrong-empty-line PASSED

Part 1: Validating the data file

The first part of this project is to add a feature to your Ruby script to validate that an input file is in fact an airline timetable and not, e.g., the professor's grocery list. We will invoke this feature by running your program as

In response, your script should output exactly one line of text and then exit. That line should either contain the three letters yes followed by a newline if the log file is valid, or the two letters no followed by a newline otherwise.

A valid timetable contains zero or more lines of text, each of which ends in a newline. (Hint: There are Ruby methods to read in a single line of text at a time.) Each line must contain the following fields from left-to-right, with each field separated from the previous field with a comma and no whitespace. The left-most field has nothing in front of it, and the right-most field is followed only by the newline that ends the line:

• The first field is a flight number, expressed as an integer between 1 and 9999, inclusive, with no leading zeros.
• A flight number must either be unique across the entire timetable, or it could be used for exactly two flights such that the arrival airport of one flight matches the departure airport of the other, e.g.,

  18,LAX,DEN,0900,1122
  18,DEN,BWI,1207,1528
  

• The second and third fields are three-letter airport codes drawn from the following list: ATL, BOS, BWI, DCA, DEN, DFW, IAD, JFK, LAX, ORD, SEA, SFO. (Airport codes are always all-caps.)
• The departure and arrival airports must not be the same.
• The fourth and fifth fields are each made up of four digits, representing a 24-hour time between 0000 and 2359, inclusive.

Any file whose lines do not conform to these rules is invalid.

Part 2: Displaying useful information

The next part of the project is to implement a range of simple but useful queries on the timetable. For all of these queries, we will only test your program with valid inputs, e.g., the airport names will be in the list given above in the discussion for validation (but there *might* be no flights between two cities)

Non-stop flights between cities

Implement a feature nonstop start end that lists all the nonstop flights that originate at airport start and end at airport end. For each such flight, print out one line containing the flight number, start time, and end time, each separated by a tab. The flights should be listed in order from earliest departure time to latest. If two flights depart at the same time, they can be listed in any order. If there are no such flights, print a single line containing none. For example:

% ruby schedule.rb flights.csv nonstop SFO BOS
180	0140	0705
226	0900	1438
172	1124	1700
788	1410	1952
892	1640	2225
% ruby schedule.rb flights.csv nonstop SFO ATL
none

All destinations

Implement a feature destinations start that lists all airports that can be reached from start with a nonstop flight, along with the number of daily nonstop flights to that airport from start (separated with a tab, as above). The airport codes should be listed one per line, in alphabetical order. For example:

% ruby schedule.rb flights.csv destinations DCA
BOS	15
DEN	1
ORD	15

Balance

Implement a feature balance that lists all the airports in the timetable along with the difference (number of daily arrivals - number of daily departures), separated again with a tab. Sort the list alphabetically by airport. For example:

% cat test.csv
1,ATL,BOS,1234,1235
2,ATL,DEN,1234,1235
3,BOS,ATL,1234,1235
% ruby schedule.rb test.csv balance
ATL	-1
BOS	0
DEN	1

Part 3: Multi-hop flights

Since not all airport pairs have nonstop flights between them, next you will implement a feature connecting start end num-connects that lists itineraries that fly from start and end that use exactly num connections. There will be many such itineraries, of course; rather than display them all, use the following rules to pick the ones to show:

• Travelers cannot go back in time, so a connecting flight must leave after an arriving one.
• Connections must take at least one hour but no more than 4 hours, inclusive. For example, if a flight gets in to ORD at 1003, then a connecting flight at 1102 is invalid; at 1103 is valid; at 1403 is valid; at 1404 is invalid. The one exception to this rule is that if a connection is via the same flight number, the connection is valid even if it doesn't fall into the 1-4 hour range.
• Some flights, especially from the west coast to the east coast, arrive the next day. You can tell what these flights are because their arrival time appears to be earlier than their departure time (e.g., flight 754 departs at 2320 and arrives at 0516). Don't forget to take this into account when computing connections.
• All flights last less than 24 hours. So a flight that leaves at 1400 and arrives at 1600 must arrive on the same day.
• For each itinerary, compute its duration, which is the number of hours and minutes between the first departure time and the final arrival time. Sort the itineraries from shortest to longest duration, and display the 5 shortest itineraries according to duration. If there are fewer than 5 itineraries, show them all.
• Print none if there are no connecting itineraries.
• The itineraries should not include any cycles, e.g., no flights from SFO to DEN to SFO to ...

% ruby schedule.rb flights.csv connecting SFO ATL 1
756	0900	1126	DEN
6604	1234	1527	ATL
Duration 0627

134	1158	1605	ORD
7560	1705	1858	ATL
Duration 0700

830	1428	1838	ORD
566	1945	2141	ATL
Duration 0713

158	0138	0540	ORD
7592	0701	0853	ATL
Duration 0715

664	0904	1305	ORD
7493	1427	1620	ATL
Duration 0716

Part last: Random questions to think about

The data file we gave you is (barring typos) the real timetable data for a major airline. For fun, try to answer the following questions using your script (or extending it); there's nothing to turn in for this part.

• What is the balance for the flights.csv file? Do you think that if we included all flights for the entire airline system, the balance would have been 0 for all airports?
• Do nonstop flights between the same pair of airports always take the same amount of time? If not, why not?
• Can you solve the traveling salesman problem for this set of airports, i.e., can you find an itinerary that visits all 12 airports? What is the shortest such itinerary?
• What airline is the timetable for?

Submission

Next, use the submit dialog to submit your schedule.rb file directly.

Select your file using the "Browse" button, then press the "Submit project!" button. You do not need to put it in a Jar or Zip file.

Hints and Tips

• This project could consume a lot of time because you will probably be writing in Ruby for the first time. So be sure to start early so you'll have opportunities to ask questions on the class forum or come to office hours if you get stuck.
• Follow good program development practices: Test each part of your program as you develop it. Start developing a simplified solution and then add features as you are sure that earlier parts work. Test early and often, and re-run your tests as you add new features to be sure you didn't break anything.
• Before you get too far, review the Ruby class reference, and look for classes and methods that might be helpful. For example, the Array and Hash classes will come in handy. Finding the right class might save you a lot of time and make your program easier to develop.
• If you write methods that should return a true or false value, remember that a Ruby 0 is not false.
• Ruby has an integrated debugger, which can be invoked by running Ruby with the -rdebug option. The debugger's p command may be helpful for viewing the values of variables and data structures. The var local command prints all of the local variables at the current point of exclusion. The chapter "When Trouble Strikes" of The Pragmatic Programmer's Guide discusses the debugger in more detail.
• To thoroughly debug your program, you will need to construct test cases of your own, based on the project description. If you need help with this, please come to TA office hours.
• Remember to save your work frequently---a power failure, network failure, or problem with a phone connection could cost many hours of lost work. For the same reason, submit your project often. You can retrieve previously-submitted versions of your program from the submit server should disaster strike.
• Be sure you have read and understand the project grading policies in the course syllabus. Do this well in advance of the project due date.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.