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;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

xScope 4.1.2 - Onscreen graphic measurem...
xScope is powerful set of tools that are ideal for measuring, inspecting, and testing on-screen graphics and layouts. Its tools float above your desktop windows and can be accessed via a toolbar,... Read more
MacFamilyTree 7.3.3 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
Skype 7.5.0.738 - Voice-over-internet ph...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
PushPal 3.0 - Mirror Android notificatio...
PushPal is a client for Pushbullet, which automatically shows you all of your phone's notifications right on your computer. This means you can see who's calling or read text messages even if your... Read more
Logic Pro X 10.1.1 - Music creation and...
Apple Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get... Read more
VLC Media Player 2.2.0 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Sound Studio 4.7.8 - Robust audio record...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
LibreOffice 4.4.1.2 - Free, open-source...
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
VueScan 9.5.03 - 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
Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more

This Week at 148Apps: February 23-27, 20...
Final February Fun at 148Apps   How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you’re looking for. The ones we love become Editor’s Choice, standing out... | Read more »
GDC 2015 – Does Not Commute is Definitel...
GDC 2015 – Does Not Commute is Definitely a Game You Should Keep an Eye on Posted by Rob Rich on March 2nd, 2015 [ permalink ] We were teased about Mediocre Games’ (Smash Hit, | Read more »
F84 Games & POW! Announce Stan Lee V...
F84 Games has announced that it is working with legendary comic creator Stan Lee and POW! Entertainment to produce Stan Lee’s Hero Command. The game will be a action adventure of heroic proportions. | Read more »
Setlyst Keeps Your Set Straight So You C...
Setlyst Keeps Your Set Straight So You Can Focus On Rocking Out. Posted by Jessica Fisher on March 2nd, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Space is Vast, So Space Agency Has a Vas...
Space is Vast, So Space Agency Has a Vast New Update! Posted by Jessica Fisher on March 2nd, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Size DOES Matter Review
Size DOES Matter Review By Campbell Bird on March 2nd, 2015 Our Rating: :: HARD TO BEATUniversal App - Designed for iPhone and iPad This rhythm game has a unique control scheme and performance system that make it feel like a true... | Read more »
The first ever action 3D card battler Al...
On the other hand, you probably haven’t played an action 3D card battler – until now. Step forward, All Star Legion. All Star Legion is a 3D QTE-based action RPG card battler, but fear not – the game itself isn’t as convoluted as its description.... | Read more »
Travel Back to the 1980s With the Making...
Headup Games has released a hilarious making of video for its upcoming title, Pixel Heroes: Byte & Magic. The game is a RPG/Roguelike where you control three heroes set to save the township of Pixton from an evil cult called The Sons of Dawn.... | Read more »
Heavenstrike Rivals Review
Heavenstrike Rivals Review By Campbell Bird on March 2nd, 2015 Our Rating: :: HEAVENLY STRATEGICUniversal App - Designed for iPhone and iPad Despite a few flaws, this free-to-play strategy game is a fun mix of new and old strategy... | Read more »
Get The Whole Story – Lone Wolf Complete...
Get The Whole Story – Lone Wolf Complete is Now Available and On Sale Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

Sale! 15-inch 2.2GHz Retina MacBook Pro for $...
 Best Buy has the 15″ 2.2GHz Retina MacBook Pro on sale for $1774.99 $1799.99, or $225 off MSRP. Choose free home shipping or free local store pickup (if available). Price valid for online orders... Read more
27-inch 3.5GHz 5K iMac in stock today and on...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more
Apple Launches Free Web-Based Pages and Other...
Apple’s new Web-only access to iWork productivity apps is a free level of iCloud service available to anyone, including people who don’t own or use Apple devices. The service includes access to Apple... Read more
Survey Reveals Solid State Disk (SSD) Technol...
In a recent SSD technology use survey, Kroll Ontrack, a firm specializing in data recovery, found that while nearly 90 percent of respondents leverage the performance and reliability benefits of SSD... Read more
Save up to $600 with Apple refurbished Mac Pr...
The Apple Store is offering Apple Certified Refurbished Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... Read more
Apple CEO Tim Cook to Deliver 2015 George Was...
Apple CEO Tim Cook will deliver the George Washington University’s Commencement address to GWU grads on May 17, at which time he will also be awarded an honorary doctorate of public service from the... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
Save up to $50 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549 $50 off - 128GB iPad Air 2... Read more
16GB iPad Air 2 on sale for $447, save $52
Walmart has the 16GB iPad Air 2 WiFi on sale for $446.99 on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale price for online orders only,... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Pay Automation Engineer - iOS System...
**Job Summary** At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring passion and dedication to your job Read more
Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
*Apple* Pay - Site Reliability Engineer - 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.