TweetFollow Us on Twitter

Oct 98 Prog Challenge

Volume Number: 14 (1998)
Issue Number: 10
Column Tag: Programmer's Challenge

October 98 Programmer's Challenge

by Bob Boonstra, Westford, MA

Hearts

A number of past Challenges have been based on games where one player competed against another player. This month the Challenge is based on the four-handed game of Hearts. Hearts is a card game where one attempts to avoid taking tricks containing hearts or the queen of spades.

The prototype for the code you should write is:

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

#pragma enumsalwaysint on

typedef enum {kNoSuit=0, kSpade, kHeart, kDiamond,
                                 kClub} Suit;
typedef enum {kNoSpot=0, k2, k3, k4, k5, k6, k7, k8, k9, k10, 
            kJack, kQueen, kKing, kAce} Spot;
typedef enum {kPassLeft=0, kPassRight, kPassAcross,
                                 kNoPass} Pass;
typedef struct Card {
   Suit suit;
   Spot spot;
} Card;

pascal void InitTournament(
   const UInt16 numPlayers,
           /* number of players in the tournament, indexed by seat */
   const UInt16 gameEndingScore
           /* game is over when one player reaches this score */
);
pascal void InitGame(
   const Uint32 playerID[4],   /* Identifier for players in this hand, indexed
                                  by seat */
   const UInt16 yourSeat       /* your seat at the table, 0..3 */
);
pascal void SelectPass(
   const Card dealtHand[13],   /* cards you are dealt */
   const Pass passDirection,
      /* direction you are passing, rotates kPassLeft, kPassRight,
      kPassAcross, kNoPass */
   UInt16 passedCards[3]   /* index in dealtHand of cards you choose to pass */
);
pascal void PlayTrick(
   const UInt16 trickNumber,   /* 13 tricks per hand, 0..12 */
   const UInt16 trickLeader,   /* which player leads this trick */
   const Card yourHand[13],    /* your cards at the beginning of this trick */
   const Card cardsPlayed[4],
                     /* cards already played this trick, indexed by seat */
                     /* entries from [trickLeader] to [yourSeat-1 (mod 4)] are
                        valid */
   UInt16 *yourPlay  /* index into yourHand of the card you choose to play */
);
pascal void TrickResults(
   const Card lastTrick[4],   /* cards played on previous trick, indexed by
                                 seat */
   const UInt16 trickWinner   /* which player won this trick */
);
pascal void HandResults(
   const SInt16 pointsThisHand[4],
                        /* points earned by each player this hand, -26 .. 25 */
   const SInt32 cumPoints[4]
                        /* cumulative points earned by each player this game */
      /* both pointsThisHand and cumPoints are indexed by seat number */
      /* your points are pointsThisHand[yourSeat] */
);

#if defined(__cplusplus)
}
#endif

At the beginning of the tournament, your InitTournament routine will be called with the number of participating players (numPlayers) and the gameEndingScore. Before each game, your InitGame routine will be called to provide you with the playerID identifiers of the players involved in this game and your position at the table (yourSeat) relative to the other players. A game consists of a sequence of hands, each of which consists of 13 tricks. At the end of a hand, each player is awarded points based on the cards in the tricks he has taken, one point for each heart taken and 13 points for the queen of spades, with the objective being to take the fewest points. A player who captures all the hearts and the queen of spades, however, is said to "shoot the moon" and receives -26 points. At the end of each hand, your HandResults routine will be called to confirm the number of points received by each player (pointsThisHand) and the cumulative number of points earned by each player during this game (cumPoints).

At the beginning of a hand, each player is dealt 13 cards (dealtHand) and selects three cards to pass to another player. The passDirection rotates from passing left (kPassLeft, where player [i] passes to player [i+1], mod 4), to passing right (kPassRight, player [i] passes to player [i-1]), to passing across (kPassAcross, player [i] passes to player [i+2]), to not passing (kNoPass). Your SelectPass routine is called at the beginning of each hand with your dealtHand and the passDirection; you select the cards to be passed and return in passedCards the index in dealtHand of the cards you want to pass.

Each trick, your PlayTrick and TrickResults routines will be called. PlayTrick provides you with the seat index of the player leading this trick, the cards in your hand at the beginning of this trick, and the cards already played on this trick. On the first trick, yourHand will be the same as dealtHand, except that the cards you passed will be replaced by the cards that were passed to you. On subsequent tricks, yourHand will be unchanged except to remove the card you played on the previous trick (by changing the suit and spot fields to kNoSuit and kNoSpot, respectively). When PlayTrick is called, you select the card you wish to play and return in yourPlay its index in yourHand. After all four players have played, your TrickResults routine will be called to identify the winner of the trick (trickWinner) and all of the cards played on the lastTrick.

The two of clubs is led on the first trick of each hand - the test code will ensure that the PlayTrick routine of the player who has the two of clubs is called first on that trick. The player who won the previous trick leads the next trick. Hearts may not be led until a point card has been played on an earlier trick, unless a player has only hearts left in his hand. The queen of spades may be led at any time.

If the number of entries is reasonable, the tournament will have each player compete against every combination of other players in all possible seat arrangements. If the number of entries is large, the best four entries will be selected in some fair way, after which those entries will compete against one another in a final tournament. If fewer than four entries are submitted, I will round out the table with a simple-minded player that tries to avoid taking any points.

The winner will be the solution that wins the tournament by achieving the lowest score. The score will be the sum of the tournament points earned and a time penalty of one point per millisecond of execution time. The execution time of all of your routines (InitTournament, InitGame, SelectPass, PlayTrick, TrickResults, and HandResults) will count toward the time penalty.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. Thanks to Jim Lloyd for suggesting this Challenge.

Three Months Ago Winner

Congratulations to Tom Saxton for winning his second consecutive Challenge, this time by efficiently controlling the elevators in the Programmer's Challenge Skyscraper. Entries in the Elevator Challenge were required to deliver passengers to their destinations during a simulated workday, starting with their arrival at the lower floors at the beginning of the day, continuing with conduct of their jobs in the morning, through the lunch hour, during another period of roaming during the afternoon, and concluding with their departure at the end of the day. Tom won the Challenge by requiring passengers to spend the least amount of time in elevators waiting to be delivered to their destinations.

One of the keys to the success of Tom's solution was his management of express elevators. Express elevators in our Skyscraper are somewhat unusual, in that they can be dynamically converted between express and non-express status. Tom allocates 80% of the elevators to be of the express type, where each express elevator stops at the bottom three floors (the parking garage, the ground floor, and the cafeteria floor) and an equally divided share of the remaining floors. This efficiently delivered passengers at the beginning and end of the day, as well as during lunch. Tom converts an express elevator into a normal elevator under a number of conditions, including when the express elevator is closest to a call from a floor outside of its range, and while on the way to delivering passengers to higher or lower floors.

The second and third place solutions of JG Heithcock and Dave Nebinger did not attempt to use the express elevator option, nor did the solution of Gregory Sadetsky. Ernst Munter and Ludovic Nicolle used express elevators, but with less success than the winning solution.

Here are the statistics for all entries to the Elevator Challenge. Solutions were evaluated using a simulated skyscraper of 100 floors, with 50 elevators, and 20000 building occupants. The Points column lists the number of passenger-timesteps required to deliver passengers to their destinations. The Elevator execution time in milliseconds is also listed, although the execution time penalty turned out to be too small to affect the results. The Score column is the sum of the passenger-timestep points and the time penalty of one point per ten milliseconds. Also listed are the code and data sizes for the entries, along with the programming language used. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

Name Points (x 10^6) Time (msecs) Score (x 10^6) Code Size Data Size Lang
Tom Saxton (39) 87.9 49228 87.9 4824 8 C
JG Heithcock (27) 173.4 52831 173.4 1496 251552 C
Dave Nebinger 221.3 89020 221.3 1920 254780 C
Ernst Munter (384) 226.1 144501 226.1 6664 269457 C++
Gregory Sadetsky 237.3 105669 237.3 2296 305684 C
Ludovic Nicolle (48) 265.7 78193 265.7 1952 258988 C

Top Contestants

Here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

  1. Munter, Ernst 174
  2. Boring, Randy 76
  3. Mallett, Jeff 50
  4. Saxton, Tom 49
  5. Rieken, Willeke 47
  6. Cooper, Greg 44
  7. Heithcock, JG 37
  8. Nicolle, Ludovic 34
  9. Lewis, Peter 31
  10. Maurer, Sebastian 30
  11. Murphy, ACC 24
  12. Gregg, Xan 22
  13. Hart, Alan 21
  14. Antoniewicz, Andy 20
  15. Day, Mark 20
  16. Higgins, Charles 20
  17. Hostetter, Mat 20
  18. Studer, Thomas 20

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

  • 1st place 20 points
  • 2nd place 10 points
  • 3rd place 7 points
  • 4th place 4 points
  • 5th place 2 points
  • Finding bug 2 points
  • Suggesting Challenge 2 points

Here is Tom's winning Elevator solution:

Elevator.c
Copyright © 1998 Tom Saxton

#include "Elevator.h"
#include <stdlib.h> // for malloc and free
enum
{
   fFalse = 0,
   fTrue = 1
};
#define DIM(a)      (sizeof(a)/sizeof(a[0]))

// disable debug assert code
#define Assert(f)
#define AssertSz(f,sz)

typedef struct EFLOOR EFLOOR;
struct EFLOOR
{
   int celevUp;
   int celevDown;
   int fCallUp;
   int fCallDown;
   int fUpBusy;
   int fDownBusy;
   int cuserLoadUp;
   int cuserLoadDown;
   int cuserDest;
};

typedef struct ELEV ELEV;
struct ELEV
{
   int       fExpectLoad;
   int       cuser;
   int       cuserUnload;
   int       cuserLoaded;
   int       floorNextStop;
   
   int       fWantExpress;
   int       fExpress;
   int       fNeverExpress;
   
   int       floorHigh;
   int       floorLow;
   CarAction actionPrev;
};

typedef enum
{
   dirUpward,
   dirDownward,
   dirMixed
} DIR;

static void _SetElevAction(int ielev, CarAction action,
            CarAction mp_ielev_action[], CarState mp_ielev_state[],
      int cfloor);
static void _SendElevToFloor(int ielev, int floorWant, 
            CarAction actionDft, CarAction mp_ielev_action[], 
            CarState mp_ielev_state[]);
static void _UpdateElev(int ielev, ELEV aelev[], CarAction action, 
            CarState *pstate, int cfloor, EFLOOR dnfloor[]);
static int _IelevFindNearest(int floorWant, CarAction mp_ielev_action[],
            CarState mp_ielev_state[], int celev);
static void _ClearFloorStats(int cfloor, EFLOOR dnfloor[]);
static void _ClearExpressElev(int ielev, ELEV *pelev, Boolean 
stopsAtFloor[kMaxElevators][kMaxFloors], int cfloor);
static void _SetOneExpressElev(int ielev, ELEV aelev[], Boolean
stopsAtFloor[kMaxElevators][kMaxFloors], int cfloor, int floorMin,
             int floorMac, int i, int c);
static void _SetExpressElevators(int celev, ELEV aelev[], 
             CarState mp_ielev_state[], int cfloor, Boolean
             stopsAtFloor[kMaxElevators][kMaxFloors]);

// set the action of the specified elevator to the specified value
// (the debug version did sanity checking)
#define _SetElevAction(ielev, action, mp_ielev_action, mp_ielev_state, cfloor) \
   (mp_ielev_action)[ielev] = action

// parameters to AdvanceTime
//
// static CarAction   mp_ielev_action[kMaxElevators];
//      /* direction you move each elevator */
// static CarState      mp_ielev_state[kMaxElevators];
//      /* returns new state of each elevator */
// static Boolean      stopsAtFloor[kMaxElevators][kMaxFloors];
//      /* stopsAtFloor[i]==TRUE means elevator stops at floor i */
// static Boolean      callGoingUp[kMaxFloors];
//      /* callGoingUp[i]==TRUE means a passenger on floor i wants to go up */
// static Boolean      callGoingDown[kMaxFloors];
//      /* callGoingDown[i]==TRUE means a passenger on floor i wants to go down */

Elevator
void Elevator(
  long cfloor, /* number of floors in our building, < kMaxFloors */
  long celev,  /* number of elevators in our building, < kMaxElevators */
  AdvanceTimeProc pfnAdvanceTime  /* callback to get new state */
)
{
   int         ielev;
   int         floor;
   DIR         dir;
   
   /* direction you move each elevator */
   CarAction *   mp_ielev_action = 
                 malloc(sizeof(CarAction) * kMaxElevators);
   /* returns new state of each elevator */
   CarState *   mp_ielev_state = 
                malloc(sizeof(CarState) * kMaxElevators);
   /* stopsAtFloor[i]==TRUE means elevator stops at floor i */
   Boolean    (*stopsAtFloor)[kMaxFloors] = 
   malloc(sizeof(Boolean)*kMaxElevators*kMaxFloors);   
   /* callGoingUp[i]==TRUE means a passenger on floor i wants to go up */
   Boolean *   callGoingUp = malloc(sizeof(Boolean) * kMaxFloors);
   /* callGoingDown[i]==TRUE means a passenger on floor i wants to go down */
   Boolean   *   callGoingDown = malloc(sizeof(Boolean) * kMaxFloors);
   
   EFLOOR *   dnfloor = (EFLOOR *)malloc(sizeof(EFLOOR) * cfloor);
   ELEV *     aelev = (ELEV *)malloc(sizeof(ELEV) * celev);
   
   Assert(mp_ielev_action != NULL);
   Assert(mp_ielev_state != NULL);
   Assert(stopsAtFloor != NULL);
   Assert(callGoingUp != NULL);
   Assert(callGoingDown != NULL);
   Assert(dnfloor != NULL);
   Assert(aelev != NULL);

   for (ielev = 0; ielev < celev; ++ielev)
   {
      ELEV *      pelevT = &aelev[ielev];
      CarState *   pstateT = &mp_ielev_state[ielev];
      
      mp_ielev_action[ielev] = kStoppedGoingUp;

      pstateT->atFloor = 0;
      for (floor = 0; floor < cfloor; ++floor)
      {
         pstateT->goingToFloor[floor] = 0;
         stopsAtFloor[ielev][floor] = TRUE;
      }
      pelevT->fExpress = pelevT->fNeverExpress = fFalse;
      pelevT->fWantExpress = fTrue;
      
      pelevT->fExpectLoad = fFalse;
      pelevT->cuser = pelevT->cuserUnload
                       = pelevT->cuserLoaded = 0;
   }
      
   _ClearFloorStats(cfloor, dnfloor);
   dnfloor[0].celevUp = celev;

   for(;;)
   {
      CarAction   action;
      int         floorCallLow, floorCallHigh;
      int         cCallUp, cCallDown;
      ELEV *      pelev = NULL;
      CarState *  pstate = NULL;
      int         celevIdle = 0;
      
      // set fields to indicate what we are expecting to happen
         for each elevator
      // during the upcoming time slice
      for (ielev = 0; ielev < celev; ++ielev)
      {
         action = mp_ielev_action[ielev];
         pstate = &mp_ielev_state[ielev];
         pelev = &aelev[ielev];

         switch (pelev->actionPrev = action)
         {
         case kStoppedGoingUp:
            pelev->fExpectLoad = dnfloor[pstate->atFloor].fCallUp;
            goto LStop;
            
         case kStoppedGoingDown:
            pelev->fExpectLoad = dnfloor[pstate->atFloor].fCallDown;
            goto LStop;
            
         case kStoppedIdle:
LStop:
            Assert(stopsAtFloor[ielev][pstate->atFloor]);
            pelev->cuserUnload = pstate->goingToFloor
                                    [pstate->atFloor];
            break;
            
         default:
            pelev->fExpectLoad = fFalse;
            pelev->cuserUnload = 0;
            break;
         }
      }
      
      // if appropriate, set up express elevators
      _SetExpressElevators(celev, aelev, mp_ielev_state, 
                  cfloor, stopsAtFloor);
      
      // Advance Time
      if ((*pfnAdvanceTime)(mp_ielev_action, mp_ielev_state, 
                     stopsAtFloor, callGoingUp, callGoingDown))
      {
         break;
      }
      
      // update floor stats
      _ClearFloorStats(cfloor, dnfloor);
      floorCallLow = cfloor;
      floorCallHigh = -1;
      cCallUp = cCallDown = 0;
      for (floor = 0; floor < cfloor; ++floor)
      {
         EFLOOR *   pefloor = &dnfloor[floor];
         
         if (!callGoingUp[floor] && !callGoingDown[floor])
            continue;
         if (callGoingUp[floor])
         {
            ++cCallUp;
            pefloor->fCallUp = fTrue;
            if (floor < floorCallLow)
               floorCallLow = floor;
         }
         if (callGoingDown[floor])
         {
            ++cCallDown;
            pefloor->fCallDown = fTrue;
            if (floor > floorCallHigh)
               floorCallHigh = floor;
         }
      }

      // update elevator stats
      for (ielev = 0; ielev < celev; ++ielev)
      {
         int cuserRemain;
         
         action = mp_ielev_action[ielev];
         pstate = &mp_ielev_state[ielev];
         pelev = &aelev[ielev];
         
         cuserRemain = pelev->cuser - pelev->cuserUnload;

         _UpdateElev(ielev, aelev, mp_ielev_action[ielev], 
                  pstate, cfloor, dnfloor);
         pelev->cuserLoaded = pelev->cuser - cuserRemain;
         
         Assert(0 <= pelev->cuserLoaded && 
                     pelev->cuserLoaded <= kElevatorCapacity);

         if (pelev->cuserLoaded > 0)
         {
            Assert(action == kStoppedGoingUp || 
                           action == kStoppedGoingDown);
            if (action == kStoppedGoingUp)
               dnfloor[pstate->atFloor].cuserLoadUp += 
                        pelev->cuserLoaded;
            if (action == kStoppedGoingDown)
               dnfloor[pstate->atFloor].cuserLoadDown += 
                        pelev->cuserLoaded;
         }

         if (pelev->cuser == kElevatorCapacity)
         {
            if (action != kStoppedGoingDown)
               dnfloor[pstate->atFloor].fUpBusy = fTrue;
            if (action != kStoppedGoingUp)
               dnfloor[pstate->atFloor].fDownBusy = fTrue;
         }
      }
      
      // what's the traffic pattern?
      {
         int cuserUpper, cuserGround;
         
         cuserUpper = 0;
         for (floor = 3; floor < cfloor; ++floor)
            cuserUpper += dnfloor[floor].cuserDest;
         cuserGround = dnfloor[0].cuserDest + 
                        dnfloor[1].cuserDest + dnfloor[2].cuserDest;
         
         dir = dirMixed;
         if (cuserGround + cuserUpper > 0)
         {
            if (cuserUpper > cuserGround)
            {
               int cCallUpFromGround;
               
               cCallUpFromGround = 0;
               for (floor = 0; floor <= 2; ++floor)
                  if (callGoingUp[floor])
                     ++cCallUpFromGround;
               
               if (cCallUpFromGround >= 2)
                  dir = dirUpward;
            }
            
            if (dir == dirMixed)
            {
               cuserGround *= (cfloor - 3);
               cuserUpper *= 3;
               
               if (cuserGround > 2*cuserUpper)
                  dir = dirDownward;
               else if (cuserUpper > 2*cuserGround)
                  dir = dirUpward;
            }
         }
         else if (cCallUp + cCallDown > 0)
         {
            if (cCallUp > 3*cCallDown)
               dir = dirUpward;
            else if (cCallDown > 3*cCallUp)
               dir = dirDownward;
         }
      }

      // process the elevators
      Assert(celevIdle == 0);
      for (ielev = 0; ielev < celev; ++ielev)
      {            
         action = mp_ielev_action[ielev];
         pstate = &mp_ielev_state[ielev];
         pelev = &aelev[ielev];

         pelev->fWantExpress = fTrue;
         switch(action)
         {
         case kStoppedGoingUp:
            if (pelev->fExpectLoad && pelev->cuserUnload == 0 && 
                     pelev->cuserLoaded == 0 && 
                     dnfloor[pstate->atFloor].cuserLoadUp == 0 && 
                     callGoingUp[pstate->atFloor])
            {
         _ClearExpressElev(ielev, pelev, stopsAtFloor, cfloor);
               break;
            }
            // fall through
         case kGoingUp:
            if (pelev->floorNextStop == -1)
               goto LIdle;
               
            Assert(pelev->floorNextStop >= pstate->atFloor);
            action = kGoingUp;
            if (pelev->floorNextStop == pstate->atFloor)
            {
               action = kStoppedGoingUp;
            }
            else if (stopsAtFloor[ielev][pstate->atFloor]
               && callGoingUp[pstate->atFloor]
               && mp_ielev_action[ielev] == kGoingUp
               && pelev->cuser < kElevatorCapacity)
            {
               if (dnfloor[pstate->atFloor].celevUp == 0 || 
                        dnfloor[pstate->atFloor].fUpBusy)
               {
                  action = kStoppedGoingUp;
                  if (!pelev->fExpress)
                     ++dnfloor[pstate->atFloor].celevUp;
               }
            }
            else
            {
            }
            _SetElevAction(ielev, action, mp_ielev_action, 
                     mp_ielev_state, cfloor);
            break;

         case kGoingDown:
            if (pelev->fExpectLoad && pelev->cuserUnload == 0 && 
                     pelev->cuserLoaded == 0 && 
                     dnfloor[pstate->atFloor].cuserLoadDown == 0 && 
                     callGoingDown[pstate->atFloor])
            {
         _ClearExpressElev(ielev, pelev, stopsAtFloor, cfloor);
               break;
            }
            // fall through
         case kStoppedGoingDown:
            if (pelev->floorNextStop == -1)
               goto LIdle;
               
            Assert(pelev->floorNextStop <= pstate->atFloor);
            action = kGoingDown;
            if (pelev->floorNextStop == pstate->atFloor)
            {
               action = kStoppedGoingDown;
            }
            else if (stopsAtFloor[ielev][pstate->atFloor]
               && callGoingDown[pstate->atFloor]
               && mp_ielev_action[ielev] == kGoingDown
               && pelev->cuser < kElevatorCapacity)
            {
               if (dnfloor[pstate->atFloor].celevDown == 0 || 
                        dnfloor[pstate->atFloor].fDownBusy)
               {
                  action = kStoppedGoingDown;
                  if (!pelev->fExpress)
                     ++dnfloor[pstate->atFloor].celevDown;
               }
            }
            _SetElevAction(ielev, action, mp_ielev_action, 
                  mp_ielev_state, cfloor);
            
            break;

         case kStoppedIdle:
LIdle:
            {
               int cuserUp, cuserDown;
               
               cuserUp = cuserDown = 0;
               for (floor = 0; floor < pstate->atFloor; ++floor)
                  cuserDown += pstate->goingToFloor[floor];
         for (floor = pstate->atFloor; floor < cfloor; ++floor)
                  cuserUp += pstate->goingToFloor[floor];
               
               if (cuserUp + cuserDown > 0)
               {
                  _SetElevAction(ielev, 
                     cuserUp > cuserDown ? kGoingUp : kGoingDown, 
                        mp_ielev_action, mp_ielev_state, cfloor);
               }
               else
               {
                  // mark elevator as idle
                  mp_ielev_action[ielev] = kStoppedIdle;
                  ++celevIdle;
               }
            }
            break;
         
         default:
            AssertSz(fFalse, "illegal action value");
            break;
         }   // switch action
      }      // for ielev

      // if there are idle elevators, figure out which way to send them
      if (celevIdle > 0)
      {
         int cCallSkipPerElev, cElevPerCall;
         int cCalls;
         
         cCalls = cCallUp + cCallDown;
                           
         if (celevIdle > 0 && cCalls > 0)
         {
            int ielevDown;
            
            // try to send each idle express elevator to a call in its range
            for (ielevDown = 0; ielevDown < celev; ++ielevDown)
            {
            int      floorCur = mp_ielev_state[ielevDown].atFloor;

               if (mp_ielev_action[ielevDown] != kStoppedIdle)
                  continue;
               
               if (!aelev[ielevDown].fWantExpress || 
                           aelev[ielevDown].fNeverExpress)
                  continue;
               
               if (dir == dirUpward && floorCur > 2 && 
                  aelev[ielevDown].fExpress && floorCallLow <= 2)
               {
                  // let's stay the course and head for the ground floors...
                  if (callGoingDown[floorCur] && 
                           dnfloor[floorCur].celevDown == 0 && 
               aelev[ielevDown].actionPrev != kStoppedGoingDown)
                  {                     
         // as long as we are going anyway, try for some passengers on the way down
                  _ClearExpressElev(ielevDown, &aelev[ielevDown], 
                              stopsAtFloor, cfloor);
                     _SetElevAction(ielevDown, kStoppedGoingDown, 
                        mp_ielev_action, mp_ielev_state, cfloor);
                  }
                  else
                  {
                     // just send it
                     _SendElevToFloor(ielevDown, floorCallLow, 
               kStoppedGoingUp, mp_ielev_action, mp_ielev_state);
                  }
                  
                  -celevIdle;
                  continue;
               }
                  
               if (floorCur <= 2 && callGoingUp[floorCur] && 
                        dnfloor[floorCur].celevUp == 0 && 
                        aelev[ielevDown].actionPrev == kGoingUp)
               {                  
            // as long as we are going anyway, try for some passengers on the way up
                  _SetElevAction(ielevDown, kStoppedGoingUp, 
                        mp_ielev_action, mp_ielev_state, cfloor);
                  
                  -celevIdle;
                  continue;
               }
               
               for (floor = aelev[ielevDown].floorHigh; 
                                 -floor >= aelev[ielevDown].floorLow; )
               {
                  Assert(0 <= floor && floor < cfloor);
                  Assert(stopsAtFloor[ielevDown][floor]);
                  
                  if (callGoingDown[floor])
                  {
                     -celevIdle;
                     if (aelev[ielevDown].fExpress && 
                              stopsAtFloor[ielevDown][floorCur] && 
                              callGoingUp[floorCur] && 
                              dnfloor[floorCur].celevUp == 0 && 
                  aelev[ielevDown].actionPrev != kStoppedGoingUp)
                     {
            // as long as we are going anyway, try for some passengers on the way up
                        _SetElevAction(ielevDown, kStoppedGoingUp, 
                           mp_ielev_action, mp_ielev_state, cfloor);
                     }
                     else
                     {
                        // just send it
            _SendElevToFloor(ielevDown, floor, kStoppedGoingDown, 
                                 mp_ielev_action, mp_ielev_state);
                     }
                     // clear the call we're going to handle for 
                     ( ; floor >= aelev[ielevDown].floorLow; -floor)
                     {
                        Assert(0 <= floor && floor < cfloor);
                        if (callGoingDown[floor])
                        {
                           callGoingDown[floor] = fFalse;
                           -cCalls;
                           -cCallDown;
                           break;
                        }
                     }
                     break;
                  }
               }
               
               // if the elevator can't do anything in its express zone, un-express it
               if (mp_ielev_action[ielevDown] == kStoppedIdle && 
                                    dir == dirDownward)
               {
                  _ClearExpressElev(ielevDown, &aelev[ielevDown], 
                              stopsAtFloor, cfloor);
               }
            }
            
            // recalc highest floor with a down call
   while (floorCallHigh > 0 && !callGoingDown[floorCallHigh])
               -floorCallHigh;
         }
                  
         if (cCalls > 0)
         {

            cElevPerCall = 0;
            cCallSkipPerElev = cCalls/celevIdle;
            if (cCallSkipPerElev == 0)
               cElevPerCall = celevIdle/cCalls;
         }
         
         while (cCalls > 0 && celevIdle > 0)
         {
            int ielevNearest, cSkip;

            if (cCallUp > cCallDown)
            {
               // dispatch an up elevator
               
      for (cSkip = cElevPerCall; cSkip- >= 0 && celevIdle > 0; 
                                    -celevIdle)
               {
                  // find the nearest elevator
                  ielevNearest = _IelevFindNearest(floorCallLow, 
                        mp_ielev_action, mp_ielev_state, celev);
            Assert(0 <= ielevNearest && ielevNearest < cfloor);
            
                  // if we're sending an elevator out of its home range,
                  // don't make any more elevators into express elevators.
                  if (floorCallLow > 2 && 
                  (floorCallLow < aelev[ielevNearest].floorLow || 
                     aelev[ielevNearest].floorHigh < floorCallLow))
                  {
            _ClearExpressElev(ielevNearest, &aelev[ielevNearest], 
                           stopsAtFloor, cfloor);
                  }
                  
                  // send it
                  _SendElevToFloor(ielevNearest, floorCallLow,
                  kStoppedGoingUp, mp_ielev_action, mp_ielev_state);
               }
               
               // skip some up calls
         for (cSkip = cCallSkipPerElev, floor = floorCallLow; 
              cSkip > 0 && floor < cfloor; ++floor)
               {
                  if (callGoingUp[floor])
                  {
                     callGoingUp[floor] = fFalse;
                     -cCallUp;
                     -cSkip;
                  }
               }
               
               // find new low call floor
               while (floorCallLow < cfloor && 
                                 !callGoingUp[floorCallLow])
                  ++floorCallLow;
            }
            else
            {
               // dispatch a down elevator
               
      for (cSkip = cElevPerCall; cSkip- >= 0 && celevIdle > 0; 
                                                      -celevIdle)
               {
                  // find the nearest elevator
                  ielevNearest = _IelevFindNearest(floorCallHigh, 
                           mp_ielev_action, mp_ielev_state, celev);
            Assert(0 <= ielevNearest && ielevNearest < cfloor);
            
                  // if we're sending an elevator out of its home range,
                  // don't make any more elevators into express elevators.
                  if (floorCallHigh > 2 && 
                  (floorCallHigh < aelev[ielevNearest].floorLow || 
                  aelev[ielevNearest].floorHigh < floorCallHigh))
                  {
            _ClearExpressElev(ielevNearest, &aelev[ielevNearest], 
                           stopsAtFloor, cfloor);
                  }
                  
                  // send it
                  _SendElevToFloor(ielevNearest, floorCallHigh,
                  kStoppedGoingDown, mp_ielev_action, mp_ielev_state);
               }
               
               // skip some down calls
         for (cSkip = cCallSkipPerElev, floor = floorCallHigh; 
                        cSkip > 0 && floor > 0; -floor)
               {
                  if (callGoingDown[floor])
                  {
                     callGoingDown[floor] = fFalse;
                     -cCallDown;
                     -cSkip;
                  }
               }
               
               // find new low call floor
               while (floorCallHigh > 0 && 
                                       !callGoingDown[floorCallHigh])
                  -floorCallHigh;
               
            }
            
            cCalls = cCallUp + cCallDown;
         }
         
         if (celevIdle > 0)
         {
            int ielevSend, celevSent, floorWant;
            
            // send everything else to the ground floor
         for (ielevSend = celevSent = 0; celevSent < celevIdle; 
                           ++ielevSend)
            {
               Assert(0 <= ielevSend && ielevSend < celev);
               if (mp_ielev_action[ielevSend] != kStoppedIdle)
                  continue;

               floorWant = aelev[ielevSend].floorLow;
               
               ++celevSent;
               _SendElevToFloor(ielevSend, floorWant, 
                     floorWant < cfloor/2 ? kStoppedGoingUp : 
                                                         kStoppedGoingDown, 
                     mp_ielev_action, mp_ielev_state);
            }
         }   // celevIdle
      }      // if celevIdle > 0
   }         // while !AdvanceTime
   
   free(mp_ielev_action);
   free(mp_ielev_state);
   free(stopsAtFloor);
   free(callGoingUp);
   free(callGoingDown);
   free(dnfloor);
   free(aelev);
}

SetExpressElevators
// setup express elevators
static void _SetExpressElevators(int celev, ELEV aelev[], CarState
mp_ielev_state[], int cfloor, Boolean stopsAtFloor[kMaxElevators][kMaxFloors])
{
   int         ielev;
   int         celevExpress;

   // allocate 4/5th of the elevators as express elevators.
   // note that there will be no express elevators unless there
   // are at least 3 elevators total
   celevExpress = 4*celev/5;
   if (celevExpress < 2)
      celevExpress = 0;
   
   // setup the express elevators
   for (ielev = 0; ielev < celevExpress; ++ielev)
   {
      ELEV *      pelev = &aelev[ielev];
      CarState *   pstate = &mp_ielev_state[ielev];
      
      if (!pelev->fExpress && pelev->fWantExpress && 
            (pelev->cuser == 0 || 
      (pelev->cuser == pstate->goingToFloor[pstate->atFloor] && 
                     pstate->atFloor <= 2)))
      {
         pelev->fExpress = fTrue;
         
      _SetOneExpressElev(ielev, aelev, stopsAtFloor, cfloor, 3, 
                  cfloor, ielev, celevExpress);
      }
   }
   
   // setup the non-express elevators
   Assert(ielev == celevExpress);
   for ( ; ielev < celev; ++ielev)
   {
      ELEV *      pelev = &aelev[ielev];
      
      if (pelev->fExpress)
         _ClearExpressElev(ielev, pelev, stopsAtFloor, cfloor);
      pelev->fNeverExpress = fTrue;
      pelev->floorLow = 0;
      pelev->floorHigh = cfloor - 1;
   }
}

SetOneExpressElev
// set properties for a single express elevator.
// floors between 3 and cfloor-1 are divided evenly among "c" elevators,
// of which the specifiec elevator is number "i" in the sequence
static void _SetOneExpressElev(int ielev, ELEV aelev[], Boolean
stopsAtFloor[kMaxElevators][kMaxFloors], int cfloor, int floorMin, int floorMac, int i, int c)
{
   int floorT, floorLow, floorHigh;
   ELEV *pelev = &aelev[ielev];
   
   Assert(0 <= floorMin && floorMin
                                    < floorMac && floorMac <= cfloor);
   
   i = c - i - 1;
   floorLow =  ((c - i) * (floorMin) + (i) * (floorMac))/(c);
   ++i;
   floorHigh =  ((c - i) * (floorMin) + (i) * (floorMac))/(c);
   
   Assert(floorMin <= floorLow && floorLow
                              < floorHigh && floorHigh <= floorMac);
   
   pelev->floorLow = floorLow;
   pelev->floorHigh = floorHigh;
   for (floorT = 0; floorT < cfloor; ++floorT)
      stopsAtFloor[ielev][floorT] = floorT <= 2 ||
                        (floorLow <= floorT && floorT < floorHigh);
   
   pelev->fExpress = fTrue;
}

ClearExpressElev
// clear the express status from an elevator
static void _ClearExpressElev(int ielev, ELEV *pelev, 
Boolean stopsAtFloor[kMaxElevators][kMaxFloors], int cfloor)
{
   int floorT;
   
   if (pelev->fExpress)
   {
      for (floorT = 0; floorT < cfloor; ++floorT)
         stopsAtFloor[ielev][floorT] = fTrue;
      pelev->fExpress = fFalse;
   }
   pelev->fWantExpress = fFalse;
}

ClearFloorStats
// zero out the floor stats
static void _ClearFloorStats(int cfloor, EFLOOR dnfloor[])
{
   int floor;

   for (floor = 0; floor < cfloor; ++floor)
   {
      EFLOOR *pefloor = &dnfloor[floor];
      
      pefloor->celevUp = pefloor->celevDown = 0;
      pefloor->fCallUp = pefloor->fCallDown = fFalse;
      pefloor->cuserLoadUp = pefloor->cuserLoadDown = 
          pefloor->cuserDest = 0;
      pefloor->fUpBusy = pefloor->fDownBusy = fFalse;
   }
}

SendElevToFloor
// send the specified elevator to the specified floor
// if it's already there, set its action to actionDft.
static void _SendElevToFloor(int ielev, int floorWant,
CarAction actionDft, CarAction mp_ielev_action[], 
CarState mp_ielev_state[])
{
   CarAction   action;
   int         floorCur;
   
   floorCur = mp_ielev_state[ielev].atFloor;
   if (floorCur == floorWant)
   {
      action = actionDft;
   }
   else
   {
      action = floorWant > floorCur ? kGoingUp : kGoingDown;
   }
   
   _SetElevAction(ielev, action, mp_ielev_action,
              mp_ielev_state, cfloor);
}

UpdateElev
// update the stats for the specifed elevator
static void _UpdateElev(int ielev, ELEV aelev[], CarAction action, 
CarState *pstate, int cfloor, EFLOOR dnfloor[])
{
   int      cuser;
   int      floor, floorCur, floorHigh, floorLow;
   
   ELEV *   pelev = &aelev[ielev];
   
   floorHigh = -1;
   floorLow = cfloor;
   floorCur = pstate->atFloor;
   
   cuser = 0;
   for (floor = 0; floor < cfloor; ++floor)
   {
      int cuserFloor = pstate->goingToFloor[floor];
      if (cuserFloor == 0)
         continue;
      Assert(stopsAtFloor[ielev][floor]);
      cuser += cuserFloor;
      dnfloor[floor].cuserDest += cuserFloor;
      
      if (floor >= floorCur && floorHigh == -1)
         floorHigh = floor;
      if (floor <= floorCur)
         floorLow = floor;
   }
   
   pelev->cuser = cuser;
   pelev->floorNextStop = -1;
   
   switch (action)
   {
   case kStoppedGoingUp:
   case kGoingUp:
      if (floorHigh >= pstate->atFloor)
         pelev->floorNextStop = floorHigh;
      break;
   
   case kStoppedGoingDown:
   case kGoingDown:
      if (floorLow <= pstate->atFloor)
         pelev->floorNextStop = floorLow;
      break;
   
   case kStoppedIdle:
      break;
   }
}

IelevFindNearest
// return the index to the idle elevator nearest to floorWant
static int _IelevFindNearest(int floorWant, CarAction mp_ielev_action[],
CarState mp_ielev_state[], int celev)
{
   int      dfloorBest, dfloor;
   int      ielev, ielevBest;

   ielevBest = -1;
   dfloorBest = kMaxFloors;
   for (ielev = 0; ielev < celev; ++ielev)
   {
      if (mp_ielev_action[ielev] != kStoppedIdle)
         continue;
      
      dfloor = abs(mp_ielev_state[ielev].atFloor - floorWant);
      
      if (dfloor >= dfloorBest)
         continue;
      
      ielevBest = ielev;
      if ((dfloorBest = dfloor) == 0)
         break;
   }
   
   return ielevBest;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Adobe InCopy CC 2018 13.0.0.123 - Create...
InCopy CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous InCopy customer). Adobe InCopy CC 2018, ideal for large team projects... Read more
MacFamilyTree 8.2.5 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
Hopper Disassembler 4.3.2- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
MacFamilyTree 8.2.5 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
Hopper Disassembler 4.3.2- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
GraphicConverter 10.5.1 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Delicious Library 3.7 - Import, browse a...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Adobe Animate CC 2017 18.0.0.107 - Anima...
Animate CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2018 (was Flash CC) lets you... Read more
Adobe After Effects CC 2018 15.0 - Creat...
After Effects CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous After Effects customer). The new, more connected After Effects CC... Read more
Adobe Premiere Pro CC 2018 12.0.0 - Digi...
Premiere Pro CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Premiere Pro customer). Adobe Premiere Pro CC 2018 lets you edit... Read more

Darts of Fury guide - how to rise in the...
Darts of Fury is a new, immensely absorbing darts game from indie studio Yakuto. It's darts in its purest form, but collectible darts and other upgrades give this game an addictive edge that's hard to shake. As your progress out of the beginner... | Read more »
ICEY (Games)
ICEY 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ICEY is a 2D side-scrolling action game. As you follow the narrator's omnipresent voice, you will see through ICEY's eyes and learn the... | Read more »
The best new games we played this week -...
We've made it, folks. Another weekend is upon us. It's time to sit back and relax with the best new releases of the week. Puzzles, strategy RPGs, and arcade games abound this week. There's a lot of quality stuff to unpack this week, so let's hop... | Read more »
Wheels of Aurelia (Games)
Wheels of Aurelia 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: | Read more »
Halcyon 6: Starbase Commander guide - ti...
Halcyon 6 is a well-loved indie RPG with stellar tactical combat and some pretty good writing, too. It's now landed on the App Store, so mobile fans, if you're itching for a good intergalactic adventure, here's your game. Being a strategy RPG, the... | Read more »
Game of Thrones: Conquest guide - how to...
Fans of base building games might be excited to know that yet another entry in the genre has materialized - Game of Thrones: Conquest. Yes, you can now join the many kingdoms of the famed book series, or create your own, as you try to conquer... | Read more »
Halcyon 6: Starbase Commander (Games)
Halcyon 6: Starbase Commander 1.4.2.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.4.2.0 (iTunes) Description: An epic space strategy RPG with base building, deep tactical combat, crew management, alien diplomacy,... | Read more »
Legacy of Discord celebrates its 1 year...
It’s been a thrilling first year for fans of Legacy of Discord, the stunning PvP dungeon-crawling ARPG from YOOZOO Games, and now it’s time to celebrate the game’s first anniversary. The developers are amping up the festivities with some exciting... | Read more »
3 reasons to play Thunder Armada - the n...
The bygone days of the Battleship board game might have past, but naval combat simulators still find an audience on mobile. Thunder Armada is Chinese developer Chyogames latest entry into the genre, drawing inspiration from the explosive exchanges... | Read more »
Experience a full 3D fantasy MMORPG, as...
Those hoping to sink their teeth into a meaty hack and slash RPG that encourages you to fight with others might want to check out EZFun’s new Eternity Guardians. Available to download for iOS and Android, Eternity Guardians is an MMORPG that lets... | Read more »

Price Scanner via MacPrices.net

27″ 3.4GHz iMac on sale for $1699, save $100
Amazon has the 27″ 3.4GHz iMac (MNE92LL/A) on sale today for $1699 including free shipping. Their price is $100 off MSRP, and it’s the lowest price available for this model (except for Apple’s $1529... Read more
Clearance 2016 15″ MacBook Pros available for...
B&H Photo has leftover 2016 15″ MacBook Pros available for up to $700 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 15″ 2.7GHz Touch Bar MacBook Pro Space... Read more
Save $100 on 13″ MacBook Airs, prices start a...
Adorama has 2017 13″ MacBook Airs on sale today for $100 off MSRP including free shipping. Adorama charges NY & NJ sales tax only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $899, $100 off MSRP... Read more
1.4GHz Mac mini available for $399, $100 off...
TigerDirect has the 1.4GHz Mac mini on sale today for $399 including free shipping. Their price is $100 off MSRP, and it’s the lowest price available for this model. Although currently out of stock,... Read more
21″ 2.3GHz iMac on sale for $999, save $100
MacMall has the 21″ 2.3GHz iMac (MMQA2LL/A) on sale today for $999 including free shipping. Their price is $100 off MSRP, and it’s the lowest price available for this model. Read more
12″ iPad Pros on sale for $50 off MSRP, no ta...
Adorama has 12″ iPad Pros on sale today for $50 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: – 12″ 64GB iPad Pro: $749, save $50 – 12″ 256GB iPad Pro: $899, save $50... Read more
9″ iPads on sale for $30 off, starting at $29...
MacMall has 9″ iPads on sale for $30 off including free shipping: – 9″ 32GB iPad: $299 – 9″ 128GB iPad: $399 Read more
Apple restocks full line of refurbished 13″ M...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
13″ 3.1GHz/256GB MacBook Pro on sale for $167...
Amazon has the 2017 13″ 3.1GHz/256GB Space Gray MacBook Pro on sale today for $121 off MSRP including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1678 $121 off MSRP Keep an... Read more
13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more

Jobs Board

Project Engineer, *Apple* Education Profess...
Project Engineer, Apple Education Professional Services Job Number: 113143353New York City, New York, United StatesPosted: Oct. 17, 2017Weekly Hours: 40.00 Job Read more
Commerce Software Engineer, *Apple* Media P...
Commerce Software Engineer, Apple Media Products Job Number: 113092072New York City, New York, United StatesPosted: Oct. 19, 2017Weekly Hours: 40.00 Job Summary With Read more
Engineering Manager, *Apple* Retail Enginee...
# Engineering Manager, Apple Retail Engineering Job Number: 58139948 Santa Clara Valley, California, United States Posted: 20-Oct-2017 Weekly Hours: 40.00 **Job Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Commerce Engineer, *Apple* Media Products -...
Commerce Engineer, Apple Media Products (New York City) Job Number: 113028813New York City, New York, United StatesPosted: Sep. 20, 2017Weekly Hours: 40.00 Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.