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
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

VueScan 9.4.41 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - 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
SlingPlayer Plugin 3.3.20.505 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
LaunchBar 6.1 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Maya 2015 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
BBEdit 10.5.12 - Powerful text and HTML...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more

Latest Forum Discussions

See All

Rhonna Designs Magic (Photography)
Rhonna Designs Magic 1.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0 (iTunes) Description: Want to sprinkle *magic* on your photos? With RD Magic, you can add colors, filters, light leaks, bokeh, edges,... | Read more »
This Week at 148Apps: August 25-29, 2014
Shiny Happy App Reviews   | Read more »
Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

The Rise of Phablets
Carlisle & Gallagher Consulting Group, a businesses and technology consulting firm focused solely on the financial services industry, has released an infographic depicting the convergence of... Read more
Eddy – Cloud Music Player for iPhone/iPad Fre...
Ukraine based CapableBits announces the release of Eddy, its tiny, but smart and powerful cloud music player for iPhone and iPad that allows users to stream or download music directly from cloud... Read more
A&D Medical Launches Its WellnessConnecte...
For consumers and the healthcare providers and loved ones who care for them, A&D Medical, a leader in connected health and biometric measurement devices and services, has launched its... Read more
Anand Lal Shimpi Retires From AnandTech
Anand Lal Shimpi, whose AnandTech Website is famous for its meticulously detailed and thoroughgoing reviews and analysis, is packing it in. Lal Shimpi, who founded the tech site at age 14 in 1997,... Read more
2.5GHz Mac mini, Apple refurbished, in stock...
The Apple Store has Apple Certified Refurbished 2.5GHz Mac minis available for $509, $90 off MSRP. Apple’s one-year warranty is included, and shipping is free. Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Labor Day Weekend MacBook Pro sale; 15-inch m...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels Desktop... Read more
Labor Day Weekend iPad mini sale; $50 to $100...
Best Buy has the iPad mini with Retina Display (WiFi models) on sale for $50 off MSRP on their online store for Labor Day Weekend. Choose free shipping or free local store pick up. Price is for... Read more
13-inch 1.4GHz MacBook Air on sale for $899,...
Adorama has the new 2014 13″ 1.4GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY & NJ tax only. Their price is $100 off MSRP. Read more
It’s Official: Apple Issues Invitations To Se...
Apple has issued one of its characteristically cryptic press invitations for a special event to be held at the Flint Center for the Performing Arts in hometown Cupertino on Sept. 9, 2014 at 10:00 am... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.