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

June 1998 Programmers Challenge

by Bob Boonstra, Westford, MA

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.

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.

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