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.
|