Mar 98 Challenge
Volume Number: 14
Issue Number: 3
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Help Peter Get Home
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/t2.
The prototype for the code you should write is:
#if defined(__cplusplus)
typedef char FlightNum[8],AirportName[64];
Sunday=0, Monday, Tuesday, Wednesday, Thursday, Friday,
long hour; /* 0-23, 0==midnight */
long min; /* 0-59 */
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 */
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 */
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.
Three Months Ago Winner
If the number of entries to the December Challenge is any indication, many
Programmer's Challenge readers are also avid crossword puzzle-ists. Congratulations
to Mat Hostetter (location unknown) for submitting the fastest of 14 entries
Clueless Crosswords Challenge. The problem was to solve (or actually, to generate) a
crossword puzzle given the pattern of open and blocked cells, along with a dictionary of
words from which to choose. The dictionary contained up to ten extra words for each
word in the crossword puzzle solution, making multiple solutions were possible.
The evaluation is based on the time required to solve each of five crossword puzzles
three times, each time with the dictionary sorted differently. I used each puzzle three
times because a number of contestants reported that execution time varied
significantly depending on the sort order of the dictionary, a fact that was borne out in
my tests. Some of the entries took two orders of magnitude more time to solve a puzzle
for one sort order than for the same puzzle with a different sort order. The winning
entry exhibited significantly less variability, ranging from a 4% difference for one
crossword puzzle to a 63% difference for another puzzle.
Like many of the entries submitted, Mat's solution has a recursive component. To
accommodate recursion, I gave each entry 512K of stack space.
The key to efficient solution of this Challenge was propagating the constraints imposed
by puzzle squares where an "across" word intersected a "down" word. The style of
crossword puzzle provided in the test code and used to evaluate this Challenge contained
many blocks of cells that were 4x4 or larger, resulting in many such intersections.
Mat uses a set of filter_for_length_N routines to efficiently propagate constraints
imposed by the intersections. When reading the modestly commented code, pay
particular attention to the create_placements routine used to identify possible word
locations, and to the tighten_constraints routine used to eliminate conflicting word
placements.
Five of the entries had not solved one or more test cases after ten minutes or more,
exceeding my ability to wait for an answer. In these cases, a test time of 10 minutes
was assessed.
The table below lists the total execution time in seconds for the fifteen test cases, code
size, data size, and programming language for each entry. The number in parentheses
after the entrant's name is the total number of Challenge points earned in all
Challenges to date prior to this one. The entries marked with an asterisk are those
which did not complete one or more test cases in the 10 minutes mentioned above.
Name Time Code Data Language
Mat Hostetter 0.37 14196 200 C
Brad Smith 1.36 7532 61835 C
Tom Saxton (12) 1.42 4132 8 C
Jens Martin Bengaard 9.76 4108 16628 C++
Xan Gregg (114) 23.73 4536 224584 C
Randy Boring (73) 74.56 4260 35158 C
Ernst Munter (310) 107.81 5824 16460 C++
Sebastian Maurer (10) 389.23 3968 112 C++
Rainer Brockerhoff 606.03 4609 165577 C
(*) ACC Murphy (34) 2400.29 6528 10212602 Pascal
(*) Mike Miller 2433.70 10052 428 C++
(*) Eric Kenninga 5599.22 6076 188 C++
(*) Steve Wozniac 5925.92 2836 64 C
(*) H.L. 9000.00 6780 1732 C++
Top 20 Contestants
Here are the Top Contestants for the Programmer's Challenge, including everyone who
has accumulated more than 10 points during that the past two years. The numbers
below include points awarded over the 24 most recent contests, including points
earned by this month's entrants.
Rank Name Points
1. Munter, Ernst 200