Jul 98 Prog Challenge
Volume Number: 14
Issue Number: 7
Column Tag: Programmer's Challenge
Jul 97 Programmer's Challenge
by Bob Boonstra, Westford, MA
Going Up?
Welcome to the Programmer's Challenge Skyscraper. Your Challenge this month is to
assume control of our skyscraper's elevators and efficiently move a dedicated crew of
simulated employees up and down the building.
The prototype for the code you should write is:
#if defined(__cplusplus)
#define kMaxFloors 500
#define kMaxElevators 100
#define kElevatorCapacity 16
typedef enum { /* commanded action for elevator car */
kGoingUp=1, /* send car up one floor */
kGoingDown, /* send car down one floor */
kStoppedGoingUp, /* stop car at an intermediate floor, car going
up */
kStoppedGoingDown, /* stop car at an intermediate floor, car going
down */
kStoppedIdle /* stop car, car in idle state */
typedef struct CarState {
long atFloor; /* current location of car */
long goingToFloor[kMaxFloors];
/* goingToFloor[i] is the number of passengers in the car is going
to floor [i] */
typedef Boolean (*AdvanceTimeProc) (
/* return value of TRUE means Elevator should
exit */
CarAction action[kMaxElevators], /* direction you move each
elevator */
CarState newState[kMaxElevators], /* returns new state of each
elevator */
Boolean stopsAtFloor[kMaxFloors],
/* stopsAtFloor[i]==TRUE means elevator stops at floor i */
Boolean callGoingUp[kMaxFloors],
/* callGoingUp[i]==TRUE means a passenger on floor i wants to go
up */
Boolean callGoingDown[kMaxFloors]
/* callGoingDown[i]==TRUE means a passenger on floor i wants to
go down */
);
void Elevator(
long numFloors, /* number of floors in our building, <
kMaxFloors */
long numElevators, /* number of elevators in our building, <
kMaxElevators */
AdvanceTimeProc AdvanceTime /* callback to get new state */
);
#if defined(__cplusplus)
}
#endif
Your Elevator routine will be called with the number of floors (numFloors) in our
simulated skyscraper, the number of elevators (numElevators) at your command, and
a callback routine (AdvanceTime). You should repeatedly call AdvanceTime,
commanding an action and a set of constraints (stopsAtFloor) for each elevator car and
receiving back the newState of each car. AdvanceTime will also provide an indicator of
whether any prospective passengers on floor i have called an elevator to take them
higher (callGoingUp[i]) or lower (callGoingDown[i]).
The newState returned by AdvanceTime provides the location of each car and the
number of occupants. atFloor is the floor at which the car is now located. Our elevator
passengers are extraordinarily cooperative -- on entering, they all indicate their
destination by pressing the button corresponding to their floor, whether or not that
floor has already been selected, allowing AdvanceTime to give you an accurate count of
the passengers going to floor i (goingToFloor[i]). Our passengers are also
extraordinarily swift --they exit and enter in such an orderly fashion that the
passenger exchange takes place in one time step.
Each call to AdvanceTime will move all the elevators one floor in the direction you
indicate. If you stop the car by setting action to kStoppedGoingUp, kStoppedGoingDown,
or kStoppedIdle, passengers headed for the current floor will exit and new passengers,
up to kElevatorCapacity, will enter. Almost always, passengers headed to higher (or
lower) floors will only enter elevators that are kStoppedGoingUp
(kStoppedGoingDown) or kStoppedIdle, but occasionally someone will be confused and