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

Latest Forum Discussions

See All

Combo Quest (Games)
Combo Quest 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Combo Quest is an epic, time tap role-playing adventure. In this unique masterpiece, you are a knight on a heroic quest to retrieve... | Read more »
Hero Emblems (Games)
Hero Emblems 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ** 25% OFF for a limited time to celebrate the release ** ** Note for iPhone 6 user: If it doesn't run fullscreen on your device... | Read more »
Puzzle Blitz (Games)
Puzzle Blitz 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Puzzle Blitz is a frantic puzzle solving race against the clock! Solve as many puzzles as you can, before time runs out! You have... | Read more »
Sky Patrol (Games)
Sky Patrol 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: 'Strategic Twist On The Classic Shooter Genre' - Indie Game Mag... | Read more »
The Princess Bride - The Official Game...
The Princess Bride - The Official Game 1.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.1 (iTunes) Description: An epic game based on the beloved classic movie? Inconceivable! Play the world of The Princess Bride... | Read more »
Frozen Synapse (Games)
Frozen Synapse 1.0 Device: iOS iPhone Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Frozen Synapse is a multi-award-winning tactical game. (Full cross-play with desktop and tablet versions) 9/10 Edge 9/10 Eurogamer... | Read more »
Space Marshals (Games)
Space Marshals 1.0.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: ### IMPORTANT ### Please note that iPhone 4 is not supported. Space Marshals is a Sci-fi Wild West adventure taking place... | Read more »
Battle Slimes (Games)
Battle Slimes 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: BATTLE SLIMES is a fun local multiplayer game. Control speedy & bouncy slime blobs as you compete with friends and family.... | Read more »
Spectrum - 3D Avenue (Games)
Spectrum - 3D Avenue 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: "Spectrum is a pretty cool take on twitchy/reaction-based gameplay with enough complexity and style to stand out from the... | Read more »
Drop Wizard (Games)
Drop Wizard 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Bring back the joy of arcade games! Drop Wizard is an action arcade game where you play as Teo, a wizard on a quest to save his... | Read more »

Price Scanner via MacPrices.net

14-inch M4 Pro/M4 Max MacBook Pros on sale th...
Don’t pay full price! Get a new 14″ MacBook Pro with an M4 Pro or M4 Max CPU for up to $320 off Apple’s MSRP this weekend at these retailers…they are the lowest prices available for these MacBook... Read more
Get a 15-inch M4 MacBook Air for $150 off App...
A couple of Apple retailers are offering $150 discounts on new 15″ M4 MacBook Airs this weekend. Prices at these retailers start at $1049: (1): Amazon has new 15″ M4 MacBook Airs on sale for $150 off... Read more
Unreal Mobile is offering a $100 discount on...
Unreal Mobile, an MVNO using AT&T and T-Mobile’s networks, is offering a $100 discount on any new iPhone with service. This includes new iPhone 16 models as well as iPhone 15, 13, and SE phones... Read more
16-inch M4 Pro MacBook Pros on sale for $250-...
Don’t pay full price! Amazon has 16-inch M4 Pro MacBook Pros (Silver or Black colors) on sale right now for up to $300 off Apple’s MSRP. Shipping is free. These are the lowest prices currently... Read more
Get a 14-inch M4 MacBook Pro for up to $240 o...
Amazon is offering a $150-$250 discount on Apple’s 14-inch M4 MacBook Pros right now. Shipping is free. Be sure to select Amazon as the seller, rather than a third-party seller: – 14″ M4 MacBook Pro... Read more
Clearance 14-inch M3 Pro MacBook Pros availab...
B&H Photo has clearance 14″ M3 Pro MacBook Pros (in Black or Silver) on sale for $500 off original MSRP, only $1499. B&H offers free 1-2 day delivery to most US addresses: – 14″ 11-Core M3... Read more
Sams Club is offering a $50 discount on Titan...
Sams Club has Titanium Apple Watch Series 10 models on sale for $50 off Apple’s MSRP. Sams Club Membership required. Note that sale prices are for online orders only, in-store prices may vary. Choose... Read more
Sunday Sale: Apple’s latest 13-inch M4 MacBoo...
Amazon has new 13″ M4 MacBook Airs on sale for $150 off MSRP right now, starting at $849. Sale prices apply to most colors and configurations. Be sure to select Amazon as the seller, rather than a... Read more
Apple’s M4 Mac minis on sale for record-low p...
B&H Photo has M4 and M4 Pro Mac minis in stock and on sale right now for up to $150 off Apple’s MSRP, each including free 1-2 day shipping to most US addresses. Prices start at only $469: – M4... Read more
Week’s Best Deals: 14-inch M4 MacBook Pros fo...
Don’t pay full price! These retailers are offering $200-$250 discounts on new 14-inch M4 MacBook Pros this week…they are the lowest sale prices available for new MacBook Pros: (1): Amazon is offering... Read more

Jobs Board

All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.