TweetFollow Us on Twitter

Jun 98 Prog Challenge

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

June 1998 Programmers Challenge

by Bob Boonstra, Westford, MA

Blackjack

This month we welcome you to the Programmer's Challenge Casino, grease your palm with 1000 Programmer's Challenge Credits (not to be confused with Challenge points) furnished by the house, and invite you to spend a few milliseconds at our Challenge Blackjack table.

The prototype for the code you should write is:

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

#pragma enumsalwaysint on

typedef enum {kHiddenSuit=0,kClub,kDiamond,kHeart,kSpade} Suit;
typedef enum { kHiddenSpot=0,
 kAce,k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,kJack,kQueen,kKing
} Spot;

typedef struct Card {  /* suit and spots for a card */
 Suit suit;
 Spot spot;
} Card;

typedef enum {
 kStandPat=0,          /* no more cards for this hand */
 kClaimBlackjack,      /* if your initial cards are Ace and a face card */
    /* the following values request another card */
 kSplitAndHitMe,       /* only valid with initial pair showing */
 kHitMe,               /* request another card for this hand */
    /* the following values request one more card */
 kDoubleDownAndHitMe   /* only valid with initial two cards */
} Action;

typedef enum {         /* results of your request for a card */
    /* this result is possible anytime after a rule violation */
 kIllegalPlay=-1,      /* illegal play causes loss of your bet */
    /* these results are possible after you request another card */
 kNoResult=0,          /* play again if you like */
 kYouWin5CardCharlie,  /* you have five cards and do not bust, you win */
 kYouBust,             /* your card puts you over 21, you lose */
    /* this result is only possible after you kClaimBlackjack in the initial callback */
 kYouWinBlackjack,     /* you have Blackjack and dealer does not, you win */
    /* this result is only possible after initial callback for a game */
  kDealerWinsBlackjack,
    /* dealer has Blackjack, you do not, no card dealt, you lose */
    /* these results are possible after you kStandPat or kClaimBlackjack */
 kPush,                /* dealer has same score, no win or loss */
    /* these results are possible after you kStandPat */
 kDealerBusts,         /* dealer went over 21, you win */
 kDealerWinsHiTotal,   /* dealer has lower total, you lose */
 kYouWinHiTotal        /* you have lower total, you win */
} Result;

typedef void BetProc(     /* place a bet for this */
 unsigned int betAmount, 
    /* amount you bet, must be >= minBet and <= maxBet */
 Card yourHand[2],      /* your initial hand */ 
 Card dealerHand[2]    /* dealers initial hand, first card is hidden */
);

typedef Result HitProc(  /* returns result for this hand */
 Action yourAction,      /* hit me or not, split or not after initial pair, */
    /* double down or not after initial two cards */
 Boolean insurance,      /* TRUE requests insurance when eligible */
    /* these items are always returned */
 Card yourCards[],       /* all of your cards, including a new hit */
 int *numYourCards,      /* number of cards in yourCards */
    /* these items are returned when result is not kNoResult */
 Card dealerCards[],     /* dealers hand, with hidden card revealed */
    /* (helps with card counting) */ 
 int *numDealerCards,    /* number of cards in dealers hand */
 int *yourWinnings       /* winnings are positive, loss is negative */
);

void InitBlackjack(
 int numDecks,          /* number of decks used by the dealer, 2..10*/
 int yourBankroll,      /* number of credits you have to start */
 int minBet,            /* minimum bet for each hand */
 int maxBet,            /* maximum bet for each hand */
 BetProc makeABet,      /* callback to place a wager */
 HitProc hitMe          /* callback to get a card */
);

Boolean Blackjack(      /* return true to keep playing, false to cash in */
  Boolean newDeck       /* true when dealer starts with fresh numDecks decks of cards */
);

#if defined (__cplusplus)
}
#endif

Play at the Challenge Casino begins with a call to InitBlackjack, where you are told how many decks the house uses (numDecks), how many Credits you have to work with (yourBankroll) courtesy of the house, the minimum (minBet) / maximum (maxBet) bet per hand at the Casino, how to place a bet (the makeABet callback) and how ask for another card (the hitMe callback). Business is slow at the Casino, and you are the only player at the table.

After the call to InitBlackjack, your Blackjack routine will be called repeatedly until you run out of Credits (in which case we show you the door) or until you decide to cash in. The house is certain that you are not a card counter, so they make it very obvious when they are starting with a fresh set of numDecks decks of cards by setting the newDeck parameter.

The first thing your Blackjack routine should do is call the makeABet callback to make a wager and obtain your first cards. The dealer also receives two cards, one of which you can see and one of which is face down (kHiddenSuit and kHiddenSpot). The dealer's hidden card will be revealed to you only at the end of the hand. After you get your cards, you can repeatedly request an additional card by calling hitMe with yourAction set to kHitMe until you believe you will win the hand or you bust. Another card will be added to yourCards and *numYourCards will be incremented. You win at Blackjack by obtaining a hand total that is less than or equal to 21 and at the same time is higher than the total in the dealer's hand. Cards are counted at their face value (i.e., (int)theCard.spot), except for aces and picture cards (Jacks, Queens, Kings). Picture cards are counted with a value of 10. Aces can be counted as either 1 or 11, at the option of the player. (In our game, the hitMe routine will score Aces to your best advantage, giving you the highest possible hand total without exceeding 21.)

As long as your card total does not exceed 21, hitMe will return kNoResult and you may keep playing. If your total exceeds 21, hitMe will return kYouBust, in which case you lose regardless of what the dealer holds. If you draw a fifth card without going bust, you have a Five Card Charlie, hitMe returns kYouWin5CardCharlie, and you win.

When you are finished requesting additional cards, you should call hitMe with yourAction set to kStandPat. The dealer will then draw cards until s/he has a total of 17 or more, and hitMe will return kDealerBusts if the dealer's total exceeds 21, kDealerWinsHiTotal if the dealer's total is greater than yours, kYouWinHiTotal if your total is greater than the dealer's, or kPush if your total and the dealer's are the same. In addition, *yourWinnings is set to the net change in yourBankroll. In the case of a tie, or 'push', *yourWinnings is set to zero. In all cases, the dealer's full hand is provided in dealerHand once the result of the hand is determined, and *numDealerCards is set to the number of entries in dealerHand.

If your first two cards are an ace and a 10-valued card (a ten or a face card), you should call hitMe with yourAction set to kClaimBlackjack and hitMe will return with kYouWinBlackjack (unless the dealer also has a blackjack). If the dealer's first two cards are an ace and a 10-valued card, the dealer has a blackjack and hitMe will return kDealerWinsBlackjack, unless both you and the dealer have a blackjack, in which case the result is kPush. No additional cards are dealt when either player has blackjack.

You have the option of 'doubling down' after looking at your first two cards by calling hitMe with yourAction set to kDoubleDownAndHitMe. The hitMe routine will double your bet, give you one more card, play the dealer's hand, and return the result.

If your first two cards are identical in value, you may 'split' the hand and play each card separately. You do this by calling hitMe with yourAction set to kSplitAndHitMe. Play the first hand as usual, but instead of returning when the hand is finished, call hitMe with yourAction set to kSplitAndHitMe again to play the second hand. You may only split on the initial two cards, not on any subsequent pairs. You cannot double down on a split hand.

When the dealer's exposed card is an ace, you are allowed to request insurance of one half of your original bet. If the dealer has a blackjack, insurance protects you from losing your initial bet (i.e., your net winnings are zero). If the dealer does not have blackjack, you lose the insurance amount and win or lose the initial bet based on how the hand plays out.

Oh, and for those of you that think gambling doesn't pay, we must insist that you actually wager those Challenge Credits initially provided by the house. Your point total will be reduced by a 'freeloader penalty', the number of your initial yourBankroll of Credits that you fail to wager. Once you have wagered yourBankroll credits, you are free to continue playing or retire with your remaining funds without penalty.

The Challenge winner will be the player that accumulates the most points, where:

Points = Credits at game end ñ milliseconds played ñ freeloader penalty

This will be a native PowerPC Challenge, using the CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Three Months Ago Winner

The March Challenge was to efficiently identify a sequence of airline flights that would take one from an origin to a destination in the minimum elapsed time, coping with the uncertainties of airline travel. Congratulations to Willeke Rieken (the Netherlands) taking first place in the Help Peter Get Home Challenge. Willeke won based on having fewer violations of the minimum connection time constraint specified in the problem statement, which resulted in less penalty time being added to his solution.

The winning solution is a little tough to read because Willeke apparently likes to be frugal with commentary. He begins by building what he calls a 'forest' of Departure records that associate each airline flight with the departure and arrival airport records. The work is then done by the FlyHome method of the Airp class instance associated with the departure airport. FlyHome then calls CalcExpectedTime for prospective intermediate stops, which in turn calls CalcExpectedTime for subsequent intermediate stops, eliminating dead ends and flights that result in loops. When the presumed fastest route is found, the JumpOnAPlane method is called to actually commit to taking the first flight segment, after which FlyHome is called for the intermediate airport to repeat the process with the intermediate airport as the departure point.

I used 12 random test cases to evaluate the solutions. The test cases resulted in between 1 and 5 flight segments per case, for a total of ~40 flight segments. I had hoped to use a digital version of the international airline guide to evaluate the solutions, but I was unable to obtain the guide until the last minute, and unable to reverse engineer the data structures in the time remaining. I was able to reverse engineer the flight schedule used on the Air Canada web site, containing the Air Canada flight database and a significant number of connecting flights from other airlines. I supplemented this with selected flights entered manually from a hardcopy of the international OAG, along with some arbitrary manual data. Note to self: sleep is a valuable thing ñ think more carefully about how you are going to test these Challenges in the future.

The table below shows the total flight time in hours for the 12 test, followed by the execution time in milliseconds, and the number of 24-hour penalties imposed for violating the connection time restriction imposed by the problem statement. The execution time, weighted so that one second of run time equates to one hour of simulated flight time, is added to the flight and penalty times to obtain the final score, with a lower score being better. Finally, the table lists the code size, data size, and programming language used for each of the solutions. The number in parentheses after a contestant's name is the total number of Challenge points earned in all Challenges to date prior to this one.

Name, Flight Time Execution (hours) Penalties (msecs) Score (24 hours) Code Data Lang
Willeke Rieken (27) 358.4 1159 1 383.6 3424 132 C++
Ernst Munter (352) 356.5 354 2 404.9 4164 1096 C++
Alan Hart (14) 414.8 995 2 463.8 5308 168 C++

Top 20 Contestants

Here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated more than 10 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 228
  2. Boring, Randy 73
  3. Cooper, Greg 61
  4. Mallett, Jeff 50
  5. Rieken, Willeke 47
  6. Nicolle, Ludovic 34
  7. Lewis, Peter 31
  8. Antoniewicz, Andy 24
  9. Gregg, Xan 24
  10. Murphy, ACC 24
  11. Hart, Alan 21
  12. Day, Mark 20
  13. Higgins, Charles 20
  14. Hostetter, Mat 20
  15. Studer, Thomas 20
  16. O'Connor, Turlough 14

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 Willeke's winning solution to the Help Peter Get Home Challenge.

HelpPeter.Cp
Copyright 1998, Willeke Rieken

// FindQuickestRoute

#include "helppeter.h"

#include <stdlib.h>
#include <string.h>

#define kMinInADay 1440

class Airp;

class Departure
class Departure  // flights
{
  public:
    Airp  *fDestination;
    Departure  *fNextDep;
    long  fScheduledDepartureTime;  // minutes after midnight
    long  fExpectedFlightDuration;
    long  fTimeOffset;
    long  fFirstArrival;
    FlightNum  fFlightNumber;
    DayOfWeek  fFirstStartDay;
    Boolean  fOperatingDays[7];
    static  GetFlightTime fGetFlightTime;
    Departure(Flight *theFligth, long theTimeOffset,
              Airp *theArrAirp);
  void SetFirstArrival(DayOfWeek theStartDay, long theStartTime,
                          long theCumTime);
  long CalcExpectedTime(Airp *theEndAirp, long theFastestTime);
  long JumpOnAPlane(DayOfWeek theStartDay, long theStartTime,
                        Airp *theEndAirp);
};

class Airp
class Airp
{
  public:
    static Airp  **fAllAirports;
    static long  fNumAirports;
    Departure  *fFirstDep;
    long  fTimeOffset;
    long  fMinConnectTime;
    long  fFirstArrival;
    long  fPrevArrival;
    long  fPrevTime;
    short  fBeenHere;
    DayOfWeek  fPrevDay;
    Airp(Airport *theAirport);
    ~Airp();
    void AddFlight(Departure *theDep);
    void ResetFirstArrivals();
    long CalcExpectedTime(DayOfWeek theStartDay, 
                          long theStartTime,
                          Airp *theEndAirp, long theCumTime,
                          long theFastestTime);
    long FlyHome(DayOfWeek theStartDay, long theStartTime,
                  Airp *theEndAirp);
};

GetFlightTime Departure::fGetFlightTime = 0;

Departure::Departure
Departure::Departure(Flight *theFlight, long theTimeOffset, 
            Airp *theArrAirp)
{
  fDestination = theArrAirp;
  fNextDep = 0;
  strcpy(fFlightNumber, theFlight->flightNumber);
  fScheduledDepartureTime = 
      theFlight->scheduledDepartureTime.hour * 60 +
                    theFlight->scheduledDepartureTime.min;
  fExpectedFlightDuration = 
      theFlight->nominalFlightDuration.hour * 60 +
                    theFlight->nominalFlightDuration.min +
                    ((1 / theFlight->lambdaDeparture) +
                    (1 / theFlight->lambdaDuration) + 0.5);
  memcpy(fOperatingDays, theFlight->operatingDays, 7);
  fTimeOffset = theTimeOffset;
  fFirstArrival = 0x7fffffff;
}

Departure::SetFirstArrival
void Departure::SetFirstArrival(DayOfWeek theStartDay, 
        long theStartTime,  long theCumTime)
{
  long  aTime = theCumTime;
  
  // calculate time spent at the airport so Peter can eliminate
  // slower flights to the same airport
  if (fScheduledDepartureTime < theStartTime)
  {
    aTime = aTime + kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  aTime = aTime + (fScheduledDepartureTime - theStartTime);
  while (!fOperatingDays[theStartDay])
  {
    aTime = aTime + kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  aTime = aTime + fExpectedFlightDuration;
  fFirstArrival = aTime;
  fFirstStartDay = theStartDay;
  // store earliest arrival with the airport
  // Peter can eliminate slower flights from other airports
  if (aTime < fDestination->fFirstArrival)
    fDestination->fFirstArrival = aTime;
}

Departure::CalcExpectedTime
long Departure::CalcExpectedTime(Airp *theEndAirp, 
        long theFastestTime)
// theStartTime is local
{
  // the time is calculated in SetFirstArrival
  if (fDestination == theEndAirp)
  {
    return fFirstArrival;
  }
  else
  {
    if (fFirstArrival < theFastestTime)
    {
      // keep track of the day of the week
      DayOfWeek  aStartDay = fFirstStartDay;
      long  aStartTime = fScheduledDepartureTime + 
          fExpectedFlightDuration - fTimeOffset;

      if (aStartTime > kMinInADay)
      {
        aStartTime = aStartTime - kMinInADay;
        if (aStartDay == Saturday)
          aStartDay = Sunday;
        else
          aStartDay = (DayOfWeek)(aStartDay + 1);
      }
      else
        if (aStartTime < 0)
        {
          aStartTime = aStartTime + kMinInADay;
          if (aStartDay == Sunday)
            aStartDay = Saturday;
          else
            aStartDay = (DayOfWeek)(aStartDay - 1);
        }
      // calculate expected time to get home from the next airport
      long anExpectedTime = 
        fDestination->CalcExpectedTime(aStartDay, aStartTime, 
                theEndAirp, fFirstArrival, theFastestTime);
      if (anExpectedTime > 0)
        return fFirstArrival + anExpectedTime;
      else
        return anExpectedTime;  // slower or didn't arrive home
    }
    else
      return -1;  // slower
  }
}

Departure::JumpOnAPlane
long Departure::JumpOnAPlane(DayOfWeek theStartDay, long theStartTime, Airp *theEndAirp)
// theStartTime is local
{
  long  aTime = 0;
  long  aFlyingTime;
  
  // calculate time until the plane will depart
  if (fScheduledDepartureTime < theStartTime)
  {
    // tomorrow
    aTime = aTime + kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  aTime = aTime + (fScheduledDepartureTime - theStartTime);
  while (!fOperatingDays[theStartDay])
  {
    aTime = aTime + kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  // calculate delays and flying time
  aFlyingTime = (*fGetFlightTime)(fFlightNumber);
  aTime += aFlyingTime;
  if (fDestination == theEndAirp)
  {
    // Peter is home and won't take another plane
    return aTime;
  }
  else
  {
    // keep track of the day of the week
    theStartTime += aTime - fTimeOffset;
    if (theStartTime > kMinInADay)
    {
      theStartTime = theStartTime - kMinInADay;
      if (theStartDay == Saturday)
        theStartDay = Sunday;
      else
        theStartDay = (DayOfWeek)(theStartDay + 1);
    }
    else
      if (theStartTime < 0)
      {
        theStartTime = theStartTime + kMinInADay;
        if (theStartDay == Sunday)
          theStartDay = Saturday;
        else
          theStartDay = (DayOfWeek)(theStartDay - 1);
      }
    // fly home from the next airport
    return aTime + 
        fDestination->FlyHome(theStartDay, 
            theStartTime, theEndAirp);
  }
}

Airp **Airp::fAllAirports = 0;

long Airp::fNumAirports = 0;

Airp::Airp
Airp::Airp(Airport *theAirport)
{
  fFirstDep = 0;
  fTimeOffset = theAirport->timeOffset.hour * 60 +
          theAirport->timeOffset.min;
  fMinConnectTime = theAirport->minConnectTime.hour * 60 +
          theAirport->minConnectTime.min;
  fBeenHere = 0;
  fFirstArrival = 0x7fffffff;
  fPrevTime = 0;
}

Airp::~Airp
Airp::~Airp()
{
  Departure  *aDep;
  while (fFirstDep)
  {
    aDep = fFirstDep->fNextDep;
    delete fFirstDep;
    fFirstDep = aDep;
  }
}

Airp::AddFlight
void Airp::AddFlight(Departure *theDep)
{
  theDep->fNextDep = fFirstDep;
  fFirstDep = theDep;
}

Airp::ResetFirstArrivals
void Airp::ResetFirstArrivals()
{
  for (long aCount = 0; aCount < fNumAirports; aCount++)
  {
    fAllAirports[aCount]->fFirstArrival = 0x7fffffff;
    fAllAirports[aCount]->fPrevTime = 0;
  }
}

Airp::CalcExpectedTime
long Airp::CalcExpectedTime(DayOfWeek theStartDay,
  long theStartTime,
                        Airp *theEndAirp, long theCumTime,
                        long theFastestTime)
// theStartTime is GMT
{
  // calculate the expected time to get home from this airport
  Departure  *aFastestDep = 0;
  Departure  *aDep = fFirstDep;
  Departure  *aPrevDep = 0;
  long  aFastestTime = 0x7fffffff;
  long  aTime;
  
  if (fBeenHere) return -1;    // flying in circles
  if (theCumTime > fFirstArrival)  // there is a faster way to get here
    return -1;
  if (fPrevTime && (fPrevArrival == theStartTime) &&
    (fPrevDay == theStartDay))  // arrived here at the same time at another try
    return fPrevTime;  // the time to get home will be the same
  fPrevArrival = theStartTime;
  fPrevDay = theStartDay;
  fPrevTime = 0;
  // calculate time spent at this airport
  theStartTime = theStartTime + fMinConnectTime + fTimeOffset;
  if (theStartTime > kMinInADay)
  {
    theStartTime = theStartTime - kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  else
    if (theStartTime < 0)
    {
      theStartTime = theStartTime + kMinInADay;
      if (theStartDay == Sunday)
        theStartDay = Saturday;
      else
        theStartDay = (DayOfWeek)(theStartDay - 1);
    }
  if (theCumTime + fMinConnectTime < theFastestTime)
  {
    fBeenHere = 1;
    // set the earliest arrival for every other airport
    // Peter can fly to from this airport
    while (aDep)
    {
      if (!aDep->fDestination->fBeenHere)
        aDep->SetFirstArrival(theStartDay, 
            theStartTime, theCumTime);
      aDep = aDep->fNextDep;
    }
    // try which flight might be the quickest way home
    aDep = fFirstDep;
    while (aDep)
    {
      if (!aDep->fDestination->fBeenHere)
      {
    aTime = aDep->CalcExpectedTime(theEndAirp, theFastestTime);
        if (aTime > 0)
        {
          if (aTime < aFastestTime)
          {
            aFastestTime = aTime;
            aFastestDep = aDep
          }
          aPrevDep = aDep;
          aDep = aDep->fNextDep;
        }
        else
          if (!aTime)  // didn't arrive home
          {
            // remove flight, it will never work
            if (aPrevDep)
            {
              aPrevDep->fNextDep = aDep->fNextDep;
              delete aDep;
              aDep = aPrevDep->fNextDep;
            }
            else
            {
              fFirstDep = aDep->fNextDep;
              delete aDep;
              aDep = fFirstDep;
            }
          }
          else
          {
            // too slow or going the wrong way
            aPrevDep = aDep;
            aDep = aDep->fNextDep;
          }
      }
      else
        aDep = aDep->fNextDep;
    }
    fBeenHere = 0;
    if (fFirstDep)
    {
      if (aFastestDep)
      {
        if (theCumTime + fMinConnectTime + aFastestTime < 
                                    theFastestTime)
        {
          fPrevTime = fMinConnectTime + aFastestTime;
          return fMinConnectTime + aFastestTime;
        }
        else
          return -1;  // slower
      }
      else
        return -1;  // didn't find a way home
    }
    else
      return 0;  // no fligths from here to theEndAirp
  }
  else
    return -1;  // slower
}

Airp::FlyHome
long Airp::FlyHome(DayOfWeek theStartDay, long theStartTime,
                    Airp *theEndAirp)
// theStartTime is GMT
{
  Departure  *aFastestDep = 0;
  Departure  *aDep = fFirstDep;
  Departure  *aPrevDep = 0;
  long  aFastestTime = 0x7fffffff;
  long  aTime;
  
  if (fBeenHere) return -1;  // flying in circles
  fBeenHere = 1;
  ResetFirstArrivals();  // delays may change earliest arrivals
  
  // calculate the time spent at this airport
  theStartTime += fMinConnectTime + fTimeOffset;
  if (theStartTime > kMinInADay)
  {
    theStartTime = theStartTime - kMinInADay;
    if (theStartDay == Saturday)
      theStartDay = Sunday;
    else
      theStartDay = (DayOfWeek)(theStartDay + 1);
  }
  else
    if (theStartTime < 0)
    {
      theStartTime = theStartTime + kMinInADay;
      if (theStartDay == Sunday)
        theStartDay = Saturday;
      else
        theStartDay = (DayOfWeek)(theStartDay - 1);
    }
  // set the earliest arrival for every other airport
  // Peter can fly to from this airport
  while (aDep)
  {
    if (!aDep->fDestination->fBeenHere)
      aDep->SetFirstArrival(theStartDay, theStartTime, 0);
    aDep = aDep->fNextDep;
  }
  // try which flight might be the quickest way home
  aDep = fFirstDep;
  while (aDep)
  {
    if (!aDep->fDestination->fBeenHere)  // don't fly in circles
    {
      aTime = aDep->CalcExpectedTime(theEndAirp, aFastestTime);
      if (aTime > 0)  // found a way home
      {
        if (aTime < aFastestTime)
        {
          // the fastest until now
          aFastestTime = aTime;
          aFastestDep = aDep;
        }
        aPrevDep = aDep;
        aDep = aDep->fNextDep;
      }
      else
        if (!aTime)  // didn't arrive home
        {
          if (aPrevDep)
          {
            aPrevDep->fNextDep = aDep->fNextDep;
            delete aDep;
            aDep = aPrevDep->fNextDep;
          }
          else
          {
            fFirstDep = aDep->fNextDep;
            delete aDep;
            aDep = fFirstDep;
          }
        }
        else
        {
          // too slow or going the wrong way
          aPrevDep = aDep;
          aDep = aDep->fNextDep;
        }
    }
    else
      aDep = aDep->fNextDep;
  }
  if (aFastestDep)
  return fMinConnectTime + aFastestDep->JumpOnAPlane(theStartDay,
                                theStartTime, theEndAirp);
  else
    return 0;
}

FindQuickestRoute
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 */
)
{
  Airp  **anAirPorts = new Airp*[numAirports];
  Airp  *aStartAirp = 0;  // where Peter starts
  Airp  *anEndAirp = 0;    // Peter's home
  Airp  *aDepAirp, *anArrAirp;
  Departure  *aDep;
  long  aAirpCount, aFlightCount, aTime;
  
  // make a forest of the airports and flights
  // each airport has a list of flights from that airport
  // each flight points to the next airport
  for (aAirpCount = 0; aAirpCount < numAirports; aAirpCount++)
  {
    anAirPorts[aAirpCount] = new Airp(&airports[aAirpCount]);
    if (!strcmp(airports[aAirpCount].name, departureAirport))
      aStartAirp = anAirPorts[aAirpCount];
    if (!strcmp(airports[aAirpCount].name, arrivalAirport))
      anEndAirp = anAirPorts[aAirpCount];
  }
  for (aFlightCount = 0; aFlightCount < 
              numFlights; aFlightCount++)
  {
    aDepAirp = 0;
    anArrAirp = 0;
    for (aAirpCount = 0; aAirpCount < numAirports; aAirpCount++)
    {
      if (!strcmp(airports[aAirpCount].name,
                airlineSchedule[aFlightCount].fromAirport))
      {
        aDepAirp = anAirPorts[aAirpCount];
        if (anArrAirp) break;
      }
      if (!strcmp(airports[aAirpCount].name,
                  airlineSchedule[aFlightCount].toAirport))
      {
        anArrAirp = anAirPorts[aAirpCount];
        if (aDepAirp) break;
      }
    }
    if (aDepAirp && anArrAirp && (aDepAirp != anArrAirp))
    {
      aDep = new Departure(&airlineSchedule[aFlightCount],
                        aDepAirp->fTimeOffset, anArrAirp);
      aDepAirp->AddFlight(aDep);
    }
  }
  Airp::fAllAirports = anAirPorts;
  Airp::fNumAirports = numAirports;
  Departure::fGetFlightTime = myGetFlightTime;
  aTime = aStartAirp->FlyHome(startDay,
      startTime.hour * 60 + startTime.min ñ 
            aStartAirp->fTimeOffset, anEndAirp);
  for (aAirpCount = 0; aAirpCount < numAirports; aAirpCount++)
    delete anAirPorts[aAirpCount];
  delete[] anAirPorts;
  return aTime * 60;
}
 
AAPL
$98.15
Apple Inc.
-0.23
MSFT
$43.58
Microsoft Corpora
-0.31
GOOG
$587.42
Google Inc.
+1.81

MacTech Search:
Community Search:

Software Updates via MacUpdate

Mellel 3.3.6 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
LibreOffice 4.3.0.4 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Freeway Pro 7.0 - Drag-and-drop Web desi...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With it's user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Drive Genius 3.2.4 - Powerful system uti...
Drive Genius is an OS X utility designed to provide unsurpassed storage management. Featuring an easy-to-use interface, Drive Genius is packed with powerful tools such as a drive optimizer, a... Read more
Vitamin-R 2.15 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Toast Titanium 12.0 - The ultimate media...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more

Latest Forum Discussions

See All

Star Admiral Review
Star Admiral Review By Rob Thomas on July 30th, 2014 Our Rating: :: ADMIRABLE ADMIRALSUniversal App - Designed for iPhone and iPad While this new digital CCG may feel a bit familiar, Star Admiral offers a sci-fi twist and galaxy’s... | Read more »
Zap! Pow! Become a Badass Wizard in Phan...
Zap! Pow! | Read more »
Urban Trial Freestyle Review
Urban Trial Freestyle Review By Blake Grundman on July 30th, 2014 Our Rating: :: RIDIN' DIRTYUniversal App - Designed for iPhone and iPad A rough ride that has trouble keeping its wheels on the track.   | Read more »
Take Note! Noteshelf Has Recieved a Big...
Take Note! Noteshelf Has Recieved a Big Update. Posted by Jessica Fisher on July 30th, 2014 [ permalink ] iPad Only App - Designed for the iPad | Read more »
Cubama Review
Cubama Review By Nadia Oxford on July 30th, 2014 Our Rating: :: TETRIIIIIS IIIIIN SPAAAAACE!Universal App - Designed for iPhone and iPad With its addictive challenge and interesting premise, Cubama is frantic screen-tapping fun.   | Read more »
Become a Guardians of Galactic Peace Wit...
Become a Guardians of Galactic Peace With the New Spacefaring Sim, Kairobotica. Posted by Jessica Fisher on July 30th, 2014 [ permalink ] | Read more »
Soul Guardians: Age of Midgard Review
Soul Guardians: Age of Midgard Review By George Fagundes on July 30th, 2014 Our Rating: :: SO MUCH GRIND IT CRUNCHESUniversal App - Designed for iPhone and iPad Swords and trading cards are fun, right? So is Soul Guardians: Age of... | Read more »
NFL Fantasy Football App Redesigned Ahea...
NFL Fantasy Football App Redesigned Ahead of Upcoming 2014 Season Posted by Ellis Spice on July 30th, 2014 [ permalink ] | Read more »
Matter Review
Matter Review By Jennifer Allen on July 30th, 2014 Our Rating: :: ORIGINAL PHOTO MANIPULATIONUniversal App - Designed for iPhone and iPad Matter lets you add geometric 3d shapes to your images and manipulate things so each image... | Read more »
Note Review
Note Review By Jennifer Allen on July 29th, 2014 Our Rating: :: TOO SIMPLEiPhone App - Designed for the iPhone, compatible with the iPad Note is a note taking app that’s a little too short on features to be worth its asking price... | Read more »

Price Scanner via MacPrices.net

More iPad Upgrade Musings – The ‘Book Mystiqu...
Much discussed recently, what with Apple reporting iPad sales shrinkage over two consecutive quarters, is that it had apparently been widely assumed that tablet users would follow a two-year hardware... Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $999.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Save up to $300 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
WaterField Unveils 15″ Outback Solo & 13″...
Hard on the heels of Apple’s refreshed MacBook Pro Retina laptops announcement, WaterField Designs has unveiled a 15-inch version of the waxed-canvas and leather Outback Solo and a 13-inch version of... Read more
New Roxio Toast 12 Delivers Digital Media Pow...
Roxio Toast 12 is a hub for sharing digital media to virtually any platform or device. has introduced two new additions to its Roxio Toast product family – Roxio Toast 12 Titanium and Roxio Toast 12... Read more
The lowest prices on leftover Retina MacBook...
Best Buy has dropped prices on leftover 13″ and 15″ Retina MacBook Pros by up to $300 off original MSRP on their online store for a limited time. Choose free local store pickup (if available) or free... Read more
Apple Updates MacBook Pro with Retina Display...
Apple today updated its MacBook Pro with Retina display with faster processors and double the amount of memory in both entry-level configurations. MacBook Pro with Retina display features a Retina... Read more
Up to $250 price drop on leftover 15-inch Mac...
B&H Photo has dropped prices on 2013 15″ Retina MacBook Pros by as much as $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2349... Read more
Updated MacBook Pro Price Trackers
We’ve updated our MacBook Pro Price Trackers with the latest information on prices, bundles, and availability on the new 2014 models from Apple’s authorized internet/catalog resellers as well as... Read more
Apple updates MacBook Pros with slightly fast...
Apple updated 13″ and 15″ Retina MacBook Pros today with slightly faster Haswell processors. 13″ models now ship with 8GB of RAM standard, while 15″ MacBook Pros ship with 16GB across the board. Most... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.