March 1998 Programmer's Challenge

 Help Peter Get Home

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Sunday, 1 March 1998

Last summer, while he was on his way back to Perth from MacHack, Peter Lewis suggested a Challenge based on airline schedules. His idea was to select the quickest route from an origin to a destination, given a schedule of flights between pairs of cities. This month's Challenge is based on Peter's suggestion, but embellished to capture the "probabilistic" nature of airline travel these days.

Your job is to write a routine FindQuickestRoute that will route Peter from his departureAirport to his arrivalAirport in as few simulated flight hours as possible. Peter's trip begins on startDay at startTime. He has a list of airports to which he can fly, and an airlineSchedule of flights between pairs of those airports. The airlineSchedule consists of a flightNumber that will take him from a fromAirport to a toAirport, nominally departing at a scheduledDepartureTime, and nominally taking nominalFlightDuration seconds to get there. The scheduledDepartureTime is expressed in the local time zone of the fromAirport, which is provided as a timeOffset from Universal Time associated with each of the airports. Some of the flights in the airlineSchedule operate only on particular days, described in the operatingDays associated with each flightNumber.

Each of the airports has a minConnectTime, which is the minimum amount of time following one's arrival at the airport before one can catch a connecting flight. This applies to the initial flight, which must be scheduled to leave at least minConnectTime after the startTime of Peter's adventure. Each subsequent connecting leg must also be scheduled to leave at least minConnectTime after the actual arrival time of the preceding leg.

Sounds simple enough so far, right? Except that airplanes seldom depart or arrive on time. So we have introduced a little randomness in our simulated airline operations. The actual departure time of each flight is modeled as a random variable with an exponential distribution, governed by the parameter lambdaDeparture. The duration of each flight is also modeled as an exponential distribution, governed by lambdaDuration. When you decide to take a flight, the callback routine myGetFlightTime will roll the exponential dice for you and return the number of minutes the flight actually took, measured from the scheduledDepartureTime, taking into account the departure delay and the duration delay. A few facts for those whose probability theory is a little rusty: an exponential distribution with parameter t has a probability density function of t*exp(-tx), an expected value of (1/t), and a variance of 1/t^2.

The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef char FlightNum[8],AirportName[64];

typedef enum {
Sunday=0, Monday, Tuesday, Wednesday, Thursday, Friday,
Saturday} DayOfWeek;

typedef struct MyTime {
long hour; /* 0-23, 0==midnight */
long min; /* 0-59 */
} MyTime;

typedef struct {
AirportName name; /* airport name */
MyTime timeOffset; /* local time offset relative to Universal Time */
/* 0 == Greenwich, {-5,0}==Eastern Time, etc. */
MyTime minConnectTime; /* minimum time to make a connection at this airport */
} Airport;

typedef struct {
FlightNum flightNumber;
AirportName fromAirport;
AirportName toAirport;
MyTime scheduledDepartureTime; /* local departure time from fromAirport */
MyTime nominalFlightDuration; /* nominal flight duration */
float lambdaDeparture; /* parameter for actual flight departure (mins) */
float lambdaDuration; /* parameter for actual flight duration (mins) */
Boolean operatingDays[7]; /* if operatingDays[d], flight valid on day d */
} Flight;

typedef long (*GetFlightTime) (
/* returns actual flight duration from scheduledDepartureTime in minutes */
FlightNum flightNumber /* flight number taken */
);

long FindQuickestRoute( /* return travel time in seconds */
AirportName departureAirport, /* origin airport */
AirportName arrivalAirport, /* destination airport */
DayOfWeek startDay, /* day the adventure begins (local time) */
MyTime startTime, /* time the adventure begins (local time) */
Airport airports[], /* places to fly from/to */
long numAirports, /* number of entries in airports[] */
Flight airlineSchedule[], /* flights to choose from */
long numFlights, /* number of entries in airlineSchedule[] */
GetFlightTime myGetFlightTime /* callback that provides actual flight duration */
);

#if defined(__cplusplus)
}
#endif

My test code will keep track of the flights you choose in the myGetFlightTime routine. It will ensure that operatingDays and minConnectTime constraints are met, that the fromAirport for travel leg n+1 is the same as the toAirport for travel leg n, etc. Violations of these constraints will result in a 24 hour simulated time penalty.

Test cases will include several trials for each departure/arrival pair to average out randomness. The winner will be the solution that routes Peter to his destinations in the least amount of time, where time is calculated as cumulative simulated travel time plus a penalty of 1 simulated hour for every second of execution time required by your FindQuickestRoute solution.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Thanks to Peter Lewis for inspiring this Challenge - he wins two Challenge points for the suggestion.