TweetFollow Us on Twitter

Nov 00 Challenge

Volume Number: 16 (2000)
Issue Number: 11
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra, Westford, MA

FreeCell

Those of you who spend time on the Dark Side might have encountered a solitaire game called FreeCell packaged with a prominent operating system by Mr. Bill. Your Challenge this month is to produce a FreeCell player.

The prototype for the code you should write is:

typedef enum {
   kNoSuit=0, kSpade, kHeart, kDiamond, kClub
} Suit;

typedef enum {
   kNoSpot=0, 
   kAce, k2, k3, k4, k5, k6, k7, k8, k9, k10,
   kJack, kQueen, kKing
} Spot;

typedef struct Card {
   Suit   suit;   /* the suit of the card, kSpade .. kClub */
   Spot   spot;   /* the spot of the card, kAce .. kKing */
} Card;

typedef enum {   /* places to move cards from */
   sFreeCellA=2,sFreeCellB,sFreeCellC,sFreeCellD,
   sTableau0=6,sTableau1,sTableau2,sTableau3,sTableau4,sTableau5,sTableau6,sTableau7
} Source;

typedef enum {   /* places to move cards to */
   dHome=1,
   dFreeCellA=2,dFreeCellB,dFreeCellC,dFreeCellD,
   dTableau0=6,dTableau1,dTableau2,dTableau3,
   dTableau4,dTableau5,dTableau6,dTableau7
} Destination;

typedef struct Move {   /* move a card from theSource to theDestination */
   Source theSource;
   Destination theDestination;
} Move;

typedef struct Tableau {   /* each Tableau can contain 0..13 cards */
   Card theCard[13];
} Tableau;

long /* numMoves */ FreeCell(
   const Tableau   theTableau[8],   /* the cards as initially dealt */
   Move theMoves[],      /* return your moves in order here */
   long   maxMoves          /* storage is preallocated for maxMoves
   theMoves */
);

The FreeCell game is different from many solitaire games in a couple of respects. First, all of the cards are visible, so winning the game is more a matter of strategy than of luck. Second, while there are FreeCell deals that cannot be solved, nearly every game can be won, as contrasted with less than half of other popular solitaire games.

FreeCell starts with the playing Cards dealt face up into 8 piles called Tableaus. All 52 Cards are used, which means that the first four Tableaus receive seven Cards, and the remaining four Tableaus receive six Cards. The object of the game is to move all of the Cards onto four "Home" piles, one for each Suit, played in order from Ace up to King. You also have available four temporary locations, or "Free Cells", each of which can hold one Card. A Move consists of one of the following:

  • moving an Ace from a Free Cell or from the top of a Tableau to an empty Home pile
  • moving the next higher Card of a Suit from a Free Cell or from the top of a Tableau to the Home pile for that Suit
  • moving a Card from the top of a Tableau to an empty Free Cell
  • moving a Card from the top of a Tableau or a Free Cell to an empty Tableau
  • moving a Card from the top of a Tableau or from a Free Cell to the top of a Tableau, where the Suit of the Card on top of the destination Tableau has the opposite color of the Card being moved, and where the Spot of the Card on top of the destination Tableau is one higher than the Spot of the Card being moved.

Cards can be moved to or from a Free Cell, but each Free Cell can hold only one Card. Cards can be moved to the Home piles, never back from the Home piles. Cards can be moved to or from the top of a Tableau, but they can only be moved to a Tableau if the Suit colors alternate and if the Card value (Spot) decreases by one. Any Card from a Free Cell or the top of another Tableau may be placed on an empty Tableau.

Your FreeCell routine will be called with the Cards dealt into the 8 Tableaus. Your task is to generate a sequence of Moves that solve the puzzle, returning them in theMoves. Each Move consists of a Source and a Destination. It is not necessary to specify the Card being moved, because the Source uniquely identifies the Card at any given point in the game. FreeCell should return the number of Moves generated, or zero if you are unable to solve the puzzle.

Your solution will be awarded 10,000 points for each puzzle it solves correctly, and penalized 1 point for each millisecond of processor time required to solve the puzzle.

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

This Challenge was suggested by Peter Lewis, who wins 2 Challenge points for the suggestion. More information on the game FreeCell can be found at http://www.freecell.org.

Three Months Ago Winner

Congratulations once again to Ernst Munter (Kanata, Ontario) for submitting the winning entry to the August Longest Word Sort Challenge. Ernst's entry was the fastest of the seven entries submitted, and was just under 40% faster than the second-place entry by Jonny Taylor.

The Longest Word Sort Challenge required contestants to sort a sequence of lines of text based on the length of words in each line. The line with the longest word was to be considered greater than any other line. Among lines with longest words of the same length, the comparison was to be based on the next longest word, etc. Among lines with words of exactly the same length, the order was to be based on an alphanumeric comparison of words, in order of length, and then in order of occurrence.

The key to Ernst's solution is the LineDescriptor that he uses to profile each line of text. The LineDescriptor contains a packed description of the number of words of each length contained in the line. This allows Ernst to compare lines by comparing the numeric line profile values, using a single subtraction in the LineDescriptor::IsLessThan routine to compare the number of words of several lengths. In the event the LineDescriptors match exactly, the CompText routine compares the words of each line as text, in order of word length. This Challenge allowed the use of assembly language, and Ernst used one line of it in the BitsNeeded routine, which is used by Text::ComputeFieldSizes to calculate the width of the packed field needed to hold the number of words of a particular length.

Jonny Taylor's second-place solution uses a combination of sorting techniques, starting with a radix sort to partially sort the list based on the lengths of the 16 longest words in each line, and then using a quicksort algorithm to sort groups of lines with identical word lengths. Jan Schotsman's third place solution uses a merge sort to compare groups of up to 32 lines, starting with a comparison of the lengths of the 16 longest words in each line, and resorting to a more careful comparison when necessary. This Challenge certainly produces an interesting variety of approaches to an unusual sorting problem. The table below lists, for each of the solutions submitted, the cumulative execution time in milliseconds. It also provides the code size, data size, and programming language used for each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

NameTime (msecs)Code SizeData SizeLang
Ernst Munter (631)1683384330C++
Jonny Taylor (26)2721406844C
Jan E. Schotsman337725656C
Rob Shearer (47)41742616965C++
Darrell Walisser6304124128C
Ladislav Hala (7)63831282429C
Ron Nepsund (47)9726492501C

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more 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.

Rank Name Points
1. Munter, Ernst 243
2. Saxton, Tom 106
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Shearer, Rob 51
6. Boring, Randy 50
7. Taylor, Jonathan 36
8. Brown, Pat 20

... and the Top Contestants Awaiting Their First Win

Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

9. Downs, Andrew 12
10. Jones, Dennis 12
12. Duga, Brady 10
13. Fazekas, Miklos 10
15. Selengut, Jared 10
16. Strout, Joe 10
17. Wihlborg, Claes 9
18. Hala, Ladislav 7
20. Schotsman, Jan 7
21. Widyyatama, Yudhi 7
22. Heithcock, JG 6

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 Ernst's winning Longest Word Sort solution:

LongestWordSort.cp
Copyright © 2000
Ernst Munter, Kanata, ON, Canada

/*

The Problem
—————-
Text is to be sorted by lines, with the lengths of words as well as the
text itself determining the order of lines.

Solution
————
The text is analyzed, and a line descriptor derived for each line. The
line descriptor contains a profile which lists the frequency of words by
length for the referenced line.  This profile is the primary key for the
sort.  Text comparisons only come into play when the profiles are
identical.

To reduce the main sort effort, lines are pre-sorted into groups which
share the same longest word length.

Each group is then sorted with heap sort, where the first phase (of
inserting the line into a heap) is combined with making a copy of the
line of text into a temporary pre-sorted text, i.e. by line group.  The
second phase of the heap sort is then combined with copying the result
back to the external text array, in the final order.
 
Optimizations
——————-
Memory accesses are minimized by copying the text just once to temporary
storage and back, as part of the sorting opration. 

The sorting itself is conducted with short line descriptors, based on
bit-packed profiles.  In most cases, a line descriptor will be 16 or 20
bytes long.

The number of comparisons is reduced (further economizing on memory
access) by using a combination of distribution sort (by line group) and
heap sort within each line group segment.  Null and null-word lines
remain in the original order and are already sorted by the distribution
sort.

Most functions are written as inlined, but the compiler will not
necessarily inline them, using its own "smart"ness.  This is not
necessarily optimal. I have forced it not to inline Pop() and
CompText().  This allows the compiler then to inline other function,
reducing the number of function calls overall.
 
Assumptions
—————-
TextToSort should end with a Mac newline character (0x0d); Any text
beyond the last newline character will not be sorted.

No assumptions are made for limits except that the longest word must be
less than 128 characters long.  Lines may be of any length and contain
any number of words.
*/

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "LongestWordSort.h"

#define MAXLENGTH    127   // no word longer than MAXLENGTH chars is expected

typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned long ulong;

enum {
   kMaxLength=MAXLENGTH,
   kArraySize=1+MAXLENGTH,
   kEOL=0x0d,
   kAlnumType=0,
   kWhiteType=1,
   kEOLtype=2,
   kCaseSensitive=0xFF,
   kNoCase=0xDF,
   kSignBit=0x80000000
};

static uchar kCaseMask[2] = {kNoCase,kCaseSensitive};
static ulong gCaseMask;
static ulong gDescending;

inline long Max(long a,long b)
// Algebraic method of selecting greater of two longs, avoids branch stalls
{
   long D = (a-b) >> 31;
   long notD = ~D;
   return (b & D) | (a & notD);
}

BitsNeeded
inline long BitsNeeded(ulong x)
// Returns number of bits needed to encode range 0 to x
{
   // this simple intrinsic is just what the job needs
   return 32 - __cntlzw(x);
/*
   // platform independent method:
   int n=0;
   while(x) { x >>= 1; n++;}
   return n;
*/
}

// Private version of the table from ctype, to include a code for EndOfLine (kEOL)
static struct CharType {
   uchar T[256];
   CharType()
   {
      for (long c=0;c<256;c++)
         T[c]=(isalnum(c))?kAlnumType:kWhiteType;
      T[kEOL]=kEOLtype;
   }
} gCharType;

struct LineDescriptor
//    A LineDescriptor characterises one line of text, 
//   containing all information needed for efficient sorting 
struct LineDescriptor;
typedef LineDescriptor* LineDescriptorPtr;
struct LineDescriptor {
   uchar*   textRef;         // pointer to start of line in copy of text
   ulong   lineLength;         // number of chars of this line
   ushort   longestWordLength;   // length of the longest word in this line
   ushort   profileLength;      // number of longs in profile
   long   profile[1];         // packed, number of words per length
   
   ulong LineLength() const {return lineLength;}
   
   long Init(uchar* lineStart,ulong lineLen,ulong longest,
      ulong lengthDist[],uchar fieldWidth[])
// Initializes the fields for one line.
// Returns the length of the struct, which includes the variable-size profile
   {
      textRef=lineStart;
      lineLength=lineLen;
      longestWordLength=longest;
// Builds the line profile by packing the number of words, by length, 
// into a string of 31-bit values for efficient comparison later.
      long* prof=profile;
      ulong acc=0;
      ulong fill=0;
      for (long len=longest;len>0;—len)
      {
         long numBits=fieldWidth[len];            
         long value=lengthDist[len];   
         fill+=numBits;
         if (fill > 31)
         {
            fill=numBits;
            *prof++=acc;
            acc=value;
         } else 
         {
            acc = value | (acc << numBits);
         }
         lengthDist[len]=0;
      }
      *prof++=acc;
      profileLength=prof-profile;
      return (sizeof(LineDescriptor) - sizeof(ulong)) +
         sizeof(ulong) * profileLength;
   }
   
LineDescriptor::IsLessThan
   ulong IsLessThan(const LineDescriptor& other) const
// Returns true if this line should be "before" the other line (ascending)
   {   
// Compare line profiles first:
      const long* A=profile;                           
      const long* B=other.profile;
      long pLength=profileLength;
      
      // there is always at least one profile word to compare
      long delta = (*A - *B);
      if (delta)                                 
         return delta & kSignBit;                     
                                                
      while (—pLength) {
         delta = *++A - *++B;                        
         if (delta)
            return delta & kSignBit;
      } 
                                 
// Both profiles are equal: must compare on the basis of text:
      delta=CompText(other);                           
      if (delta)
         return  delta & kSignBit;
                                                
//  The text is exactly the same: 
//    Compare on the basis of the original line order
//    But reverse if descending to compensate for reverse CopyBack
      return gDescending ^ ((textRef - other.textRef) & kSignBit);
   }
   
   static long CompWords(const uchar* w1,
      const uchar* w2,long len,long caseMask)
// Simple string comparison, character by character, case sensitive as required
   {
      for (long i=0;i<len;i++) 
      {
         long c1=*w1++ & caseMask;
         long c2=*w2++ & caseMask;
         long delta=c1-c2;
         if (delta) return delta;
      } 
      return 0;
   }
   
   LineDescriptor::LocateNext
static const uchar* LocateNext(const uchar* start,long length) 
// Returns the next word of the specified length 
   {
      ulong c=*start,len=0;
      const uchar* word=start;
      for (;;)
      {
         long charType=gCharType.T[c];
         c=*++start;
         if (charType==kAlnumType)    // is alnum
         {
            if (len==0) word=start-1;
            len++;   
         } else 
         {
            if (len==length)      // lengths match: found it
                  break;
            
            if (charType==kEOLtype)   // reached end of the line
               return 0;
            len=0;
         }
      }
      return word;
   }
   
   void Write(uchar* outText) const
   {
// Note: memcpy is faster than strncpy or character by character copy.
      memcpy(outText,textRef,lineLength);
   }
   
   long CompText(const LineDescriptor& other) const;
};

LineDescriptor::CompText
long LineDescriptor::CompText(const LineDescriptor& other) const
// Returns result of comparing the line as text, longest words first
{   
   for (long len=longestWordLength;len>0;len—)
   {
      const uchar* w1=textRef;
      const uchar* w2=other.textRef;
      for (;;)
      {
         if (0==(w1=LocateNext(w1,len))) 
            break; // no word of this length found
            
         w2=other.LocateNext(w2,len);         
         // if w1 exists, w2 must exist 
          long d=CompWords(w1,w2,len,gCaseMask);            
         if (d)
            return (d);
         w1 = w1+len;
         w2 = w2+len;
      }
   }                                             
   return 0;
}

struct Segment   
// The priority queue (Heap) structure is used for sorting the line descriptors.
// Sorting occurs in two phases: Insert() and Pop()
// We build a separate heap for each lineGroup segment (which shares a common 
// longest word length).  This reduces the size of the individual heaps, resulting in 
// fewer comparisons overall.  
struct Segment {
   LineDescriptorPtr*    heapBase;
   ulong   heapSize;
   ulong   maxHeapSize;
   uchar*   nextLineDesc;
   ulong   lineDescSize;

// Just keep track of the line count, to prepare correct heap size                  
   void AddLine(){maxHeapSize++;}
   
   ulong MemRequired(ulong profileLongs,ulong profileBits)
   {
// Returns the amount of memory required for lineDescs and their index (=heap)
      if (maxHeapSize==0) return 0;
      ulong profileSizeInLongs=profileLongs+(31+profileBits)/32;
      ulong profileBytes=4*profileSizeInLongs;
      
      lineDescSize=
         profileBytes + (sizeof(LineDescriptor) - sizeof(ulong));
      return
         lineDescSize * maxHeapSize +             // for linedescs
         sizeof(LineDescriptorPtr*) * (1+maxHeapSize);// for heap index
   }
   
   uchar* Init(uchar* memPool)
   {
// Grabs memory from the pool for lineDescs and the heap; returns updated pool
      if (maxHeapSize>0)
      {
         nextLineDesc=memPool;
         memPool += maxHeapSize * lineDescSize;
      
         heapBase=(LineDescriptorPtr*) memPool;
         memPool += sizeof(LineDescriptorPtr*) * (1+maxHeapSize);
      }
      return memPool;
   }      
   
   LineDescriptorPtr GetLineDesc() 
// Walks the index memory to assign consecutive lineDesc indices
   {
      LineDescriptorPtr next=LineDescriptorPtr(nextLineDesc);
      nextLineDesc += lineDescSize;
      return next;
   }
   
   void Insert(LineDescriptorPtr k) 
// Inserts one line, while maintaining the heap property
   {
       long i=++heapSize;
       long j=i>>1;
       LineDescriptorPtr z;
       while (j && (k->IsLessThan(*(z=heapBase[j])))) 
       {   
            heapBase[i]=z;     
             i=j;
            j=i>>1;
       }
       heapBase[i]=k;    
     }
     
   uchar* CopyBack(uchar* textToSort)
// Pops one line off the heap, and copies the referenced line to the output.
// When descending, lines are copied starting at the end of the output.
// Returns the updated output text pointer, in preparation for the next copy.
   {
      if (0==heapSize)
         return textToSort;
         
      if (gDescending)
      {
         uchar* endText=textToSort;
         do {
            LineDescriptorPtr textLine=Pop();
            uchar* outText=endText - textLine->LineLength();
            textLine->Write(outText);
            endText=outText;
         } while(heapSize);
         return endText;
      } else
      {
         uchar* outText=textToSort;
         do {
            LineDescriptorPtr textLine=Pop();
            textLine->Write(outText);
            outText+=textLine->LineLength();
         } while(heapSize);
         return outText;
      }
   }
   
   LineDescriptorPtr Pop();
};

Segment::Pop
LineDescriptorPtr Segment::Pop() 
//   The node at heapBase[1] has the lowest weight.
//   It is popped from the heap and returned.  
//  The heap is adjusted to maintain the heap property.
{
    LineDescriptorPtr rc=heapBase[1];
      LineDescriptorPtr k=heapBase[heapSize—];
    if (heapSize<=1) {
         heapBase[1]=k;            
         return rc;
      }
      long i=1,j=2;
      while (j<=heapSize) 
      {
         if ((j<heapSize)
       && (heapBase[j+1]->IsLessThan(*heapBase[j])))
            j++;
         if (k->IsLessThan(*heapBase[j]))
            break;
         heapBase[i]=heapBase[j];  
         i=j;j+=j;
      }
      heapBase[i]=k;        
      return rc;
}
   
struct Text
struct Text {
   uchar*    theText;
   ulong   textSize;
   uchar*   copyText;
   ulong   gNumLines;
   ulong   gLongest;
   
   uchar*   lineDescMemory;
      
// highest number of words of length x in a line:
   ulong   lengthDist[kArraySize];
   ulong   tempLengthDist[kArraySize];
   
// one segment of lineDescriptors for each possible lineGroup
   Segment   segment[kArraySize];
   
// size (=numChars) of each text segment by longestWord line group:
   ulong   segmentSize[kArraySize];
   
// start of each text segment by longestWord line group
   uchar*   segmentStart[kArraySize];
   
// width of profile fields in bits for each possible word length
   uchar   fieldWidth[kArraySize];

   Text(char *textToSort,long numChars) :
         theText((uchar*)textToSort),
         textSize(numChars),
         copyText(new uchar[numChars])
   {
// Constructor analyzes text and computes text profile, prior to sorting.
// Determines the division of the text into line groups.
      memset(lengthDist,0,sizeof(lengthDist) 
         + sizeof(tempLengthDist) 
         + sizeof(segment) 
         + sizeof(segmentSize));
      Analyze();
      ComputeFieldSizes();
      lineDescMemory=GetLineDescMemory();   
   }
   ~Text()
   {
      delete [] lineDescMemory;
      delete [] copyText;
   }
   
   void Sort()
// Does the actual sorting of the segments:
   {
// Scans the text a second time while inserting lines in segments heaps.
// This constitutes the first phase of sorting.
      Presort();
      
// Zero-word lines will be in the original order in line group 0,
// They can just be copied en bloc, to the front or back end of the output.
      uchar* dest=theText;
      if (gDescending)
      {
         dest += textSize-segmentSize[0];
         memcpy(dest,copyText,segmentSize[0]);
      } else 
      {
         memcpy(dest,copyText,segmentSize[0]);
         dest += segmentSize[0];
      }
   
// The remaining lines are popped from each segment heap,  
// starting with the linegroup with the shortest longest words.
// This completes the second phase of sorting. 
      for (long len=1;len<=gLongest;len++)
      {
         dest=segment[len].CopyBack(dest);
      }
   }
   void Analyze();
   void ComputeFieldSizes();
   uchar* GetLineDescMemory();
   void Presort();
};

Text::Analyze
void Text::Analyze()
// Scans the original text and collects statistics such as 
//      - the number of lines
//      - the number of words by length
//      - the size of each line group (lines with the same max-length)
//      - the longest word in the whole text
// The loop in this routine relies on finding a 0x0d character at text end. 
{
   ulong   len=0,longest=0,numLines=0;
   ulong   globalLongest=0;
   uchar*   text=theText;
   ulong   c=*text;
   uchar*   lineStart=text;
   ulong   numChars=textSize;
   for (;;)
   {
      long charType=gCharType.T[c];
      c=*++text;
      if (charType==kAlnumType) len++;   // part of a word
      else 
      {
         if (len)                  // register the word
         {
            tempLengthDist[len]++; 
            longest=Max(longest,len);
            len=0;
         }
      
         if (charType==kEOLtype)         // register the line
         {
            for (long l=0;l<=longest;l++)
            {
               if (lengthDist[l] < tempLengthDist[l])
                  lengthDist[l] = tempLengthDist[l];      
               tempLengthDist[l]=0;
            }
            segment[longest].AddLine();
            globalLongest=Max(globalLongest,longest);
            ulong lineLength=text-lineStart;
            segmentSize[longest]+=lineLength;
            numChars -= lineLength;
            numLines++;
            
            if (numChars <= 0)
               break;
            longest=0;   
            lineStart=text;
         }
      } 
   }
   gNumLines = numLines;
   gLongest  = globalLongest;
}

Text::ComputeFieldSizes
void Text::ComputeFieldSizes()
// Computes the minimum field widths for profiles, for each word length
// also devides the text copy into segments, one per line group
{
   uchar* start=copyText;
   for (long len=0;len<=gLongest;len++)
   {
      fieldWidth[len] = BitsNeeded(lengthDist[len]);
      segmentStart[len]=start;
      start+=segmentSize[len];
   }
}

Text::GetLineDescMemory
uchar* Text::GetLineDescMemory()
// Allocates the memory required for the variable size line descriptors 
// and sets up the lineGroup segments.
// Note: In the interest of not fragmenting the memory heap unnecesssarily,
//       this memory is allocated as a single chunk, and then divided
//       out among the segments for line descriptors and index arrays.
{   
   ulong memRequired=0;
   
   ulong profileBits=0,profileLongs=0;
   for (long len=1;len<=gLongest;len++)
   {
      long fWidth=fieldWidth[len];
      if (fWidth)
      {
         // accumulate total bits to cover fields up to length len
         profileBits += fWidth;
         if (profileBits > 31)
         {
            profileLongs++;
            profileBits=fWidth;
         }
         
         // if segment[len] is not empty, reserve memory for it 
         memRequired += 
               segment[len].MemRequired(profileLongs,profileBits);
      } 
   }

// Allocate all required memory ..
   uchar* allocated=new uchar[memRequired];
   memset(allocated,0,memRequired);
   
// .. and divide it among active segments
   uchar* memPool=allocated;
   for (long len=1;len<=gLongest;len++)
      memPool=segment[len].Init(memPool);
   
   return allocated;
}

Text::Presort
void Text::Presort()
// Second scan of the text:
//      assigns and initializes a line descriptor for each line, 
//      and inserts it in the selected segment 
{
   uchar* text=theText;
   ulong len=0,longest=0;
   memset(tempLengthDist+1,0,gLongest*sizeof(ulong));
   uchar* lineStart=text;
   ulong c=*text;
   long numLines=gNumLines;
   for (;;)
   {
      long charType=gCharType.T[c];
      c=*++text;
      if (charType==kAlnumType) len++;
      else 
      {
         if (len)            // register the word
         {
            tempLengthDist[len]++;
            longest=Max(longest,len);
            len=0;
         }
      
         if (charType==kEOLtype)      // register the line
         {
            —numLines;
            ulong lineLength=text-lineStart;
                  
            uchar* copyDest=segmentStart[longest];
            memcpy(copyDest,lineStart,lineLength);
            segmentStart[longest] = copyDest+lineLength;
            lineStart=text;
            
            if (longest)         // make a new line descriptor
            {
               LineDescriptorPtr lineDesc =
                  segment[longest].GetLineDesc();
            
               // note side effect: Init clears tempLengthDist
               lineDesc->Init(copyDest,lineLength,longest,
                  tempLengthDist,fieldWidth);
                  
               segment[longest].Insert(lineDesc);
               
               longest=0;
            } // else, no need to do anything (no words in line) 
            if (numLines<=0)
               break;
         }
      } 
   }
}

LongestWordSort
void LongestWordSort(
   char *textToSort,      /* the text to be sorted */
   long numChars,         /* the length of the text in bytes */
   Boolean descending,    /* sort in descending order if true */
   Boolean caseSensitive  /* sort is case sensitive if true */
) {
// Just to be sure, let's ignore all text beyond the last CR
   while (numChars && (kEOL != textToSort[numChars-1]))
      numChars—;

   if (numChars==0) return; // quit if there is no text to sort
   
// Make sort parameters global
   gDescending=(descending)?kSignBit:0;
      gCaseMask=kCaseMask[caseSensitive];
      
// Initialize ..
   Text* T=new Text(textToSort,numChars);
// and sort: 
   T->Sort();
   delete T;   
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

HandBrake 1.0.2 - Versatile video encode...
HandBrake is a tool for converting video from nearly any format to a selection of modern, widely supported codecs. Features Supported Sources VIDEO_TS folder, DVD image or real DVD (unencrypted... Read more
PhotoDesk 4.1.5 - Instagram client for p...
PhotoDesk lets you view, like, comment, and download Instagram pictures/videos. (NO Uploads! / Image Posting! Instagram forbids that! AND you need an existing Instagram account). But you can do so... Read more
Sound Studio 4.8.6 - 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
Capo 3.5.1 - Slow down and learn to play...
Capo lets you slow down your favorite songs so you can hear the notes and learn how they are played. With Capo, you can quickly tab out your songs atop a highly-detailed OpenCL-powered spectrogram... Read more
Google Earth 7.1.8.3036 - View and contr...
Google Earth gives you a wealth of imagery and geographic information. Explore destinations like Maui and Paris, or browse content from Wikipedia, National Geographic, and more. Google Earth combines... Read more
QuickBooks 16.1.11.1556 R12 - Financial...
QuickBooks helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save. Built for... Read more
Google Earth 7.1.8.3036 - View and contr...
Google Earth gives you a wealth of imagery and geographic information. Explore destinations like Maui and Paris, or browse content from Wikipedia, National Geographic, and more. Google Earth combines... Read more
QuickBooks 16.1.11.1556 R12 - Financial...
QuickBooks helps you manage your business easily and efficiently. Organize your finances all in one place, track money going in and out of your business, and spot areas where you can save. Built for... Read more
FileZilla 3.24.0 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.24.0: New The context menu for remote file search... Read more
Bookends 12.7.8 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Bookends uses the cloud to sync reference libraries on all the Macs you use.... Read more

Super Mario Run dashes onto Android in M...
Super Mario Run was one of the biggest mobile launches in 2016 before it was met with a lukewarm response by many. While the game itself plays a treat, it's pretty hard to swallow the steep price for the full game. With that said, Android users... | Read more »
WarFriends Beginner's Guide: How to...
Chillingo's new game, WarFriends, is finally available world wide, and so far it's a refreshing change from common mobile game trends. The game's a mix of tower defense, third person shooter, and collectible card game. There's a lot to unpack here... | Read more »
Super Gridland (Entertainment)
Super Gridland 1.0 Device: iOS Universal Category: Entertainment Price: $1.99, Version: 1.0 (iTunes) Description: Match. Build. Survive. "exquisitely tuned" - Rock Paper Shotgun No in-app purches, and no ads! | Read more »
Red's Kingdom (Games)
Red's Kingdom 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Mad King Mac has kidnapped your father and stolen your golden nut! Solve puzzles and battle goons as you explore and battle your... | Read more »
Turbo League Guide: How to tame the cont...
| Read more »
Fire Emblem: Heroes coming to Google Pla...
Nintendo gave us our first look at Fire Emblem: Heroes, the upcoming mobile Fire Emblem game the company hinted at last year. Revealed at the Fire Emblem Direct event held today, the game will condense the series' tactical RPG combat into bite-... | Read more »
ReSlice (Music)
ReSlice 1.0 Device: iOS Universal Category: Music Price: $9.99, Version: 1.0 (iTunes) Description: Audio Slice Machine Slice your audio samples with ReSlice and create flexible musical atoms which can be triggered by MIDI notes or... | Read more »
Stickman Surfer rides in with the tide t...
Stickson is back and this time he's taken up yet another extreme sport - surfing. Stickman Surfer is out this Thursday on both iOS and Android, so if you've been following the other Stickman adventures, you might be interested in picking this one... | Read more »
Z-Exemplar (Games)
Z-Exemplar 1.4 Device: iOS Universal Category: Games Price: $3.99, Version: 1.4 (iTunes) Description: | Read more »
5 dastardly difficult roguelikes like th...
Edmund McMillen's popular roguelike creation The Binding of Isaac: Rebirth has finally crawled onto mobile devices. It's a grotesque dual-stick shooter that tosses you into an endless, procedurally generated basement as you, the pitiable Isaac,... | Read more »

Price Scanner via MacPrices.net

12-inch 1.2GHz Space Gray Retina MacBook on s...
Amazon has the 2016 12″ 1.2GHz/512GB Space Gray Retina MacBook (Apple model #MLH82LL/A) on sale for $1299.99 including free shipping. Their price is $300 off MSRP. Read more
Twelve South Releases RelaxedLeather Cases fo...
Inspired by the laid-back luxury of burnished leather boots and crafted in rich tones of taupe, herb and marsala, RelaxedLeather cases deliver smart, easy protection for the iPhone 7. Each genuine... Read more
Week’s Best Deal: New 2016 13-inch 2.0GHz Mac...
Amazon has the new 2016 13″ 2.0GHz non-Touch Bar MacBook Pros on sale for a limited time for $225 off MSRP including free shipping: - 13″ 2.0GHz MacBook Pro, Space Gray (MLL42LL/A): $1274.99 $225 off... Read more
Back in stock: Apple refurbished Mac minis fr...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off MSRP - 2.6GHz Mac... Read more
Apple Ranked ‘Most Intimate Brand’
The top ranked ‘”intimate” brands continued to outperform the S&P and Fortune 500 indices in revenue and profit over the past 10 years, according to MBLM’s Brand Intimacy 2017 Report, the largest... Read more
B-Eng introduces SSD Health Check for Mac OS
Fehraltorf, Switzerland based independant Swiss company- B-Eng has announced the release and immediate availability of SSD Health Check 1.0, the company’s new hard drive utility for Mac OS X. As the... Read more
Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: -... Read more
4-core 3.7GHz Mac Pro on sale for $2290, save...
Guitar Center has the 3.7GHz 4-core Mac Pro (MD253LL/A) on sale for $2289.97 including free shipping or free local store pickup (if available). Their price is a $710 savings over standard MSRP for... Read more
128GB Apple iPad Air 2, refurbished, availabl...
Apple has Certified Refurbished 128GB iPad Air 2s WiFis available for $419 including free shipping. That’s an $80 savings over standard MSRP for this model. A standard Apple one-year warranty is... Read more
13-inch 2.7GHz Retina MacBook Pro on sale for...
B&H Photo has the 2015 13″ 2.7GHz/128GB Retina Apple MacBook Pro on sale for $100 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro (MF839LL/A): $... Read more

Jobs Board

*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing Read more
*Apple* Retail - Multiple Positions- Deer Pa...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Technician - nfrastructure (United S...
Let’s Work Together Apple Technician This position is based in Portland, ME Life at nfrastructure At nfrastructure, we understand that our success results from our Read more
*Apple* Mobile Master - Best Buy (United Sta...
**467692BR** **Job Title:** Apple Mobile Master **Location Number:** 000602-Columbia MO-Store **Job Description:** **What does a Best Buy Apple Mobile Master Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.