July 1998 Programmer's Challenge
Elevator Control
Mail solutions to:
<mailto:progchallenge@mactech.com>,
and copy
<mailto:bob_boonstra@mactech.com>
Due Date: 11:59PM, ET, 1 July 1998
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)
extern "C" {
#endif
#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 */
} CarAction;
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] */
} CarState;
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 fo 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 enter an elevator headed in the wrong
direction.
You are free to run your elevators anyway you see fit, except that
a car declared to be kGoingUp (or kGoingDown) needs to continue going
up (or down) until all passengers headed in that direction have
exited. You can designate elevators to be express elevators by
setting stopsAtFloor[i] to be FALSE for floors where this elevator
does not stop. Passengers will only enter cars that will stop at
their intended destination. You can change the stopsAtFloor values at
any time, but you need to be careful not to strand passengers - you
can command the car to stop at any time, but the door will only open
at floor i if stopsAtFloor[i] is TRUE.
The objective of this Challenge is to deliver passengers to their
destinations as expeditiously as possible. You incur a cost of one
point for each passenger for each time step from the time s/he
presses the call button until the time s/he exits the elevator. You
also incur one point for each 10 milliseconds of execution time,
including the time spent by AdvanceTime. Stranding a passenger inside
an elevator or not responding to an elevator call button results in
disqualification of your solution. The solution that incurs the
fewest points wins the Challenge. There are no storage constraints
for this Challenge, except that it must execute on my 96MB 8500/200.
The Challenge will simulate a normal workday in our simulated
skyscraper. People arrive at the beginning of the day either by
entering the parking garage at floor 0 or by walking into the main
entrance at floor 1. They work in approximately equal numbers on
floors 2 through numFloors-1. During the day, they move about the
building as necessary. Somewhere in the middle of the day, most of
them take a lunch break, either at the cafeteria on floor 2 or by
leaving the building. Nearly everyone leaves the building at the end
of the day. However, as advanced as our elevators are, they don't
have a clock, so you'll have to establish your strategy without
knowing the time of day.
This will be a native PowerPC Challenge, using the latest
CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.
Ernst Munter wins two Challenge points for suggesting this problem,
way back in November, 1996.
|