Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

Poker Hand Evaluator

This month’s challenge was suggested by Chris Derossi (Mountain View, CA). The goal is to compare two poker hands and determine which is higher. Your routine will be given two hands of 7 cards each. It will have to make the best 5 card hand it can from each and return the two 5-card hands as well as which is higher.

Here is how poker hands rank (from lowest to highest, with an example of each in parentheses):

one pair (5, 5, *, *, *)

two pair (5, 5, 8, 8, *)

three of a kind (5, 5, 5, *, *)

straight (5, 6, 7, 8, 9)

flush (club, club, club, club, club)

full house (5, 5, 5, 8, 8)

four of a kind (5, 5, 5, 5, *)

straight flush (5, 6, 7, 8, 9; all clubs)

five of a kind (5, 5, 5, 5, wildCard)

The prototype of the function you write is:

typedef unsigned char Card;

typedef SevenCardHand {
 Card cards[7];
} SevenCardHand;

typedef FiveCardHand {
 Card cards[5];
} FiveCardHand;

short
ComparePokerHands(hand1Ptr, hand2Ptr,
 best1Ptr, best2Ptr, 
 wildCardAllowed, wildCard, 
 straightsAndFlushesValid,
 privateDataPtr)
SevenCardHand  *hand1Ptr;
SevenCardHand  *hand2Ptr;
FiveCardHand*best1Ptr;
FiveCardHand*best2Ptr;
Boolean  wildCardAllowed;
Card     wildCard;
Boolean  straightsAndFlushesValid;
void    *privateDataPtr;

A Card is a byte value (unsigned char) from 0 to 51 where 0 represents the 2 of clubs, 9 is the jack of clubs, 12 is the ace of clubs, 13 is the 2 of diamonds, 26 is the 2 of hearts, 39 is the 2 of spades and 51 is the ace of spades.

The inputs are two SevenCardHands (from the same deck; you won’t get duplicate Cards). Your routine should make the highest hand possible with 5 of the 7 cards and store the resulting hand in the two FiveCardHands. It should then return one of the following values: -1 if hand 1 is higher than hand 2, 0 if the hands are tied and 1 if hand 2 is higher than hand 1. Hands can be tied because suit counts for nothing when ranking hands. Aces can be high or low (whichever makes the resulting hand better).

WildCardAllowed is true if wild cards are allowed and false if not. If they are allowed then wildCard will be the card that is wild, from 0 to 12. All suits of that care are wild. For example, if wildCard is 4 then all 6’s are wild (Card values 4, 17, 30 and 43).

StraightsAndFlushesValid is true if straights and flushes are to be counted in the ranking. If it is false then straights and flushes do not count for anything (they are low hands).

PrivateDataPtr is the value returned by your Init routine, which is not timed, whose prototype is:

void *
ComparePokerHandsInit(wildCardAllowed, wildCard,
     straightsAndFlushesValid)
Boolean wildCardAllowed;
Card    wildCard;
Boolean straightsAndFlushesValid;

You can allocate up to 1MB of memory in your Init routine (in case you want to generate some lookup tables). The pointer you return will be passed to your ComparePokerHands routine.

E-mail me if you have any questions. Have fun.

Two Months Ago Winner

I had to disqualify two of the eight entries I received for the Huffman Decoding challenge because of incorrect results. Congratulations to Challenge Champion Bob Boonstra (Westford, MA) for earning his fifth win. The top four entrants each optimized their solutions for those cases where there was extra memory available. Greg McKaskle (Austin, TX) had a very strong showing for the extra memory case but his very-little-extra-memory case code came in 3rd place, preventing him from winning overall.

Here are the times and code sizes for each entry. Numbers in parens after a person’s name indicate how many times that person has finished in the top 5 places of all previous Programmer Challenges, not including this one:

Name 256K time8K time  code
Bob Boonstra (12)12422308
Greg McKaskle    11113    2012
John Schlack (1) 28551470
Wolfgang Thaller (age 13) 40929    1090
Allen Stenger (7)103 103  440
Peter Hance 1211 1211188

From reading the winning code you may notice that even a master such as Bob has picked up at least one trick from studying previous Challenge winners. He chose to borrow the ‘switch-do-while’ idea from Bill Karsh’s SwapBytes entry (a neat trick, indeed). Glad to see it. After all, this column is meant to be educational (by teaching tricks by example) as much as it is a contest.

I’ve been getting more requests than usual to have access to the current Challenge before the magazine hits the streets (especially from people outside the US). Well, this being the 90’s and all, the latest Challenge is available on-line the day the magazines go out in the mail. Check out p. 2 for where to look on each of the online services.

Hope that helps. Here is Bob’s winning solution:

HuffmanDecode

Copyright (c) 1994  J Robert Boonstra

Problem Statement

Given a symbol table, decompress the Huffman encoded input stream and return the number of decompressed bytes.

Solution Strategy

Use the untimed initialization routine to create a tree structure corresponding to the sym values in the symbol table. In the timed decode routine, traverse the tree. When a leaf node is encountered, output the corresponding value, and begin traversing the tree again from the root.

We determine whether there is enough storage for the tree structure by trying to construct it. If there is not enough storage, set up a simple table of pointers into the symbol table based on symbol length. This is not especially efficient, but it produce correct results.

 
#pragma options(honor_register,!assign_registers)

TYPEDEFS and DEFINES
#define ulong  unsigned long
#define ushort unsigned short
#define uchar  unsigned char

/*
 * SymElem is the data structure provided in the problem
 * definition.  Symbols are sorted by symLength and within
 * length by sym.
 */
typedef struct SymElem {
  unsigned short symLength;
  unsigned short sym;
  unsigned short value;
} SymElem, *SymElemPtr;

/*
 * DecodeNode is a node in the tree used to decode the 
 * input stream.  The zeroP and oneP values are offsets
 * into the tree corresponding to reading a 0 or a 1 given
 * the prior input.  Note that the zeroP field is used at a
 * leaf node (identified by a zero in the oneP field) to 
 * represent the SymElem value.  The offsets are stored
 * relative to the current tree position for efficiency
 * in calculating the address.  Note also that 16 bits are 
 * enough to access the max available 256K (64K nodes of 
 * 4 bytes each).  In cases where only 64K storage is used,
 * the offsets are premultiplied by sizeof(DecodeNode) to
 * squeeze out a little additional efficiency at some small
 * expense in code size.
 */
typedef struct DecodeNode {   
    ushort zeroP;   /* index of right tree node, or value */ 
    ushort oneP;    /* index of left tree node            */ 
} DecodeNode; 

typedef struct SymDecode {
        SymElemPtr symP;
        ushort numEntries;
        ushort align;
} SymDecode;

PROTOTYPES

void *HuffmanDecodeInit(SymElemPtr theSymTable,
  unsigned short numSymElems,
  unsigned long maxMemoryUsage);

unsigned long HuffmanDecode(SymElemPtr theSymTable,
  unsigned short numSymElems, char *bitsPtr,
  unsigned long numBits, unsigned short *outputPtr,
  void * privateHuffDataPtr);
 
#define kUnused (ushort)0xFFFF
#define kTerminalNode 0
#define InitializeNewNode()                                \
{                                                          \
    if ((void *)pFree > (void *)pMax)                      \
      goto notEnoughStorage;                               \
    pFree->oneP = kUnused;                                 \
    pFree->zeroP = kUnused;                                \
}

#define kGMode 0
#define kSEP 4
#define kGlobalStorageSize (kSEP+16*sizeof(SymDecode))

#define gMode *(short *)((char *)privateHuffDataPtr+kGMode)

HuffmanDecodeInit

void *HuffmanDecodeInit(SymElemPtr theSymTable,
  unsigned short numSymElems,
  unsigned long maxMemoryUsage)
{
register DecodeNode *p;
register DecodeNode *pOrig;
register DecodeNode *pFree;
register ulong pMax;
register ushort i;
register ulong nodeNum=1;
SymDecode *theSymElemPtr;
SymElemPtr sP;
void *privateHuffDataPtr;
ulong count;
ushort sym,maxLng,maxDiff=0;

/*
 * Allocate entire memory allocation, return if allocation
 * fails.
 */
  if (0 == (p=privateHuffDataPtr = NewPtr(maxMemoryUsage)))
     return 0;
  gMode = 0;

/* 
 * Initialize SymElem pointers
 */
  theSymElemPtr = (SymDecode *)((char *)privateHuffDataPtr +
                                                      kSEP);
  sP = theSymTable;
  count = 0;
  sym = theSymTable->sym;
  for (i=1; i<=16; ++i) {
    ushort oldCount;
    oldCount = count;
    theSymElemPtr->symP = sP;
    while ((sP->symLength==i) && (count<numSymElems))
      { ++count;  ++sP; }
    theSymElemPtr++->numEntries = count-oldCount;
  }

/*
 * Initialize tree pointers.
 */
  p = (DecodeNode *)(kGlobalStorageSize + 
                                (char *)privateHuffDataPtr);
  pOrig = pFree = p;
  pMax = (ulong)((char *)p + maxMemoryUsage -
                (kGlobalStorageSize + sizeof(DecodeNode)) );

/*
 * Initialize root of tree.
 */
  InitializeNewNode();
  ++pFree;

/*
 * Loop over symbol table elements.
 * Insert each symbol into the tree.
 * Tree is traversed by following the zeroP/oneP indices 
 * corresponding to the bits of the sym field in the symbol
 * table, from most significant to least significant bit.
 * Leaves of the tree are indicated by oneP==kTerminalNode.
 * The zeroP field of leaf nodes contains the decompressed 
 * output for the bit sequence that led to the leaf when 
 * the oneP field is kTerminalNode.
 */
  for (i=0; i<numSymElems; ++i) {
    SymElemPtr sP;
    register short sym;
    ushort value;
    register ushort symLength;
    sP = theSymTable+i;
    sym = sP->sym;
    value = sP->value;
    symLength = sP->symLength;
    p = pOrig;

/*
 * Loop over bits in the sym field.
 */
    sym <<= (16-symLength);
    do {
      if (0 > sym ) {
/*
 * Process a 1, allocate a new node if one is needed.
 */
        if (kUnused == p->oneP) { 
          InitializeNewNode();
          p->oneP = (pFree-p);
          if (p->oneP > maxDiff) maxDiff = p->oneP;
          p = pFree++;
        } else {
          p += p->oneP;
        }
      } else {
/*
 * Process a 0, allocate a new node if one is needed.
 * Note that since we reuse the zeroP field later to contain
 * the value to be output, this code depends on having a
 * correct (i.e. deterministic) Huffman encoding in
 * theSymTable, and will crash spectacularly otherwise.
 */
        if (kUnused == p->zeroP) {
          InitializeNewNode();
          p->zeroP = (pFree-p);
          if (p->zeroP > maxDiff) maxDiff = p->zeroP;
          p = pFree++;
        } else {
          p += p->zeroP;
        }
      }
      sym <<= 1;
    } while (--symLength);

/*
 * Insert value into leaf node.
 */
    p->zeroP = value;
    p->oneP = kTerminalNode;
    maxLng = sP->symLength;
  }

/* 
 * Premultiply offsets by node size for "fast" mode.
 */
  if ( (1<<14)-1 > maxDiff  ) {
    gMode = 1;
    p = pFree;
    do {
      --p;
      if (p->oneP != kTerminalNode) {
        if (p->zeroP != kUnused)
          p->zeroP *= sizeof(DecodeNode);
        if (p->oneP != kUnused)
          p->oneP *= sizeof(DecodeNode);
      }
    } while (p>pOrig);
  }
  goto done;


notEnoughStorage: 
/*
 * If we do not have enough storage for the tree, fall back
 * on a slower technique requiring less storage.
 */
  gMode = 2;
done:
  return privateHuffDataPtr;
}

macro ProcessBit

#define ProcessBit(mask,bitNum)                            \
{ register ulong temp;                                     \
  if (!(theChar & mask)) temp = tP->zeroP;                 \
  else                   temp = oneP;                      \
  temp *= sizeof(DecodeNode);                              \
  t += temp;                                               \
  if (kTerminalNode == (oneP = tP->oneP))  {               \
    *outP++ =  tP->zeroP;                                  \
    t = (char *)decode_tree;                               \
    oneP = tP->oneP;                                       \
  }                                                        \
}

macro ProcessBitFast

#define ProcessBitFast(mask,bitNum)                        \
{ register ulong temp;                                     \
  if (!(theChar & mask)) temp = tP->zeroP;                 \
  else                   temp = oneP;                      \
  t += temp;                                               \
  if (kTerminalNode == (oneP = tP->oneP))  {               \
    *outP++ =  tP->zeroP;                                  \
    t = (char *)decode_tree;                               \
    oneP = tP->oneP;                                       \
  }                                                        \
}

macro ProcessBitSlow

#define ProcessBitSlow(mask,bitNum,keepMask,next)          \
{ register ushort temp;                                    \
  if (!(theChar & mask)) temp = tP->zeroP;                 \
  else                   temp = oneP;                      \
  if (temp != kUnused) {                                   \
    temp *= sizeof(DecodeNode);                            \
    t += temp;                                             \
    if (kTerminalNode == (oneP = tP->oneP))  {             \
      *outP++ =  tP->zeroP;                                \
      t = (char *)decode_tree;                             \
      oneP = tP->oneP;                                     \
      theSym=0;  theSymLng=0;                              \
      theChar &= keepMask;                                 \
      bitStart = bitNum-1;                                 \
      next;                                                \
    }                                                      \
  } else {                                                 \
    theBitNum = bitNum;                                    \
    goto overflow;                                         \
  }                                                        \
}

HuffmanDecode

unsigned long HuffmanDecode(SymElemPtr theSymTable,
  unsigned short numSymElems, char *bitsPtr,
  unsigned long numBits, unsigned short *outputPtr,
  void * privateHuffDataPtr)
{
register char *bitsP = bitsPtr;
register ushort *outP = outputPtr;
register char *t = (char *)privateHuffDataPtr + 
                                         kGlobalStorageSize;
#define tP ((DecodeNode *)t)

register uchar theChar; 
register ushort oneP;
register ulong count; 
ushort state;
 
  oneP = ((DecodeNode *)t)[0].oneP;
  state = 0;
/*
 * Set up loop count to loop over complete input bytes, and
 * jump past the switch statement into the loop.
 * The billKarsh-inspired switch--do subterfuge allows us  
 * to optimize the main loop and still reuse code for the 
 * leftover bits at the end.
 */
  count = numBits>>3;
/*
 * Select case.
 */
  {
    register ushort mode;
    if (0 == (mode = *(ushort *)(t - kGlobalStorageSize)) )
      goto start;
    if (1 == mode) goto startFast;
    goto slowest;
  }


/*
 * CASE 0
 *
 * This section processes the case where the decode tree
 * fit into available memory, but the offsets are in units
 * of sizeof(long).
 * We jump to doLeftOverBits at the end to pick up the last byte.
 */
doLeftOverBits:
  state = 1;
  count = 1;                  /* Only one byte to process */
  theChar =  *bitsP;          /* Fetch last byte */
  theChar>>=(8-numBits);      /* Shift bits into position */
  switch (numBits) {
    register ulong decode_tree;
start:
    decode_tree = (ulong)t;
    do { 
bit0:
/*
 * Loop over the bytes in the input stream, decoding as
 * we go.  Rather than loop over the bits in each byte,
 * the bit loop is unrolled for efficiency.
 */
        theChar =  *bitsP++;  /* get input byte */ 
case 0: ProcessBit(0x80,8);     /* process 0th bit */
case 7: ProcessBit(0x40,7);     /* process 1st bit */ 
case 6: ProcessBit(0x20,6);     /* process 2nd bit */ 
case 5: ProcessBit(0x10,5);     /* process 3rd bit */ 
case 4: ProcessBit(0x08,4);     /* process 4th bit */ 
case 3: ProcessBit(0x04,3);     /* process 5th bit */ 
case 2: ProcessBit(0x02,2);     /* process 6th bit */ 
case 1: ProcessBit(0x01,1);     /* process 7th bit */ 
    } while (--count);
  }
/*
 * Make another pass to process the bits in the last byte.
 */
  if (state==0) {
    if (numBits &= 7) goto doLeftOverBits;
  }
  goto done;


/*
 * CASE 1
 *
 * This section processes the case where the decode tree
 * fit into available memory, but the offsets are in units
 * of bytes.
 * We jump to doLeftOverBitsFast at the end to pick up the 
 * last byte.
 */
doLeftOverBitsFast:
  state = 1;
  count = 1;                  /* Only one byte to process */
  theChar =  *bitsP;          /* Fetch last byte */
  theChar>>=(8-numBits);      /* Shift bits into position */
  switch (numBits) {
    register ulong decode_tree;
startFast:
    decode_tree = (ulong)t;
    do { 
bit0Fast:
/*
 * Loop over the bytes in the input stream, decoding as
 * we go.  Rather than loop over the bits in each byte,
 * the bit loop is unrolled for efficiency.
 */
        theChar =  *bitsP++;  /* get input byte */ 
case 0: ProcessBitFast(0x80,8); /* process 0th bit */
case 7: ProcessBitFast(0x40,7); /* process 1st bit */ 
case 6: ProcessBitFast(0x20,6); /* process 2nd bit */ 
case 5: ProcessBitFast(0x10,5); /* process 3rd bit */ 
case 4: ProcessBitFast(0x08,4); /* process 4th bit */ 
case 3: ProcessBitFast(0x04,3); /* process 5th bit */ 
case 2: ProcessBitFast(0x02,2); /* process 6th bit */ 
case 1: ProcessBitFast(0x01,1); /* process 7th bit */ 
    } while (--count);
  }
/*
 * Make another pass to process the bits in the last byte.
 */
  if (state==0) {
    if (numBits &= 7) goto doLeftOverBitsFast;
  }
  goto done;

/* 
 * CASE 2
 *   This code handles the case where the entire decode
 *   tree did not fit into the private storage.  In this
 *   case we use the portion of the tree that did fit, but
 *   we may have to linearly search the SymTable for the
 *   longer symbols.
 */
slowest:
{
  SymDecode *theSymElemPtr;
  SymElemPtr sP;
  short bitStart,theSymLng,theMask,theBitNum,saveCount,x;
  register ushort theSym;
  theSymLng = 0;
  theSym = 0;
  goto startSlow;
doLeftOverBitsSlow:
  state = 1;
  count = 1;                /* Only one byte to process */
  theChar =  *bitsP;        /* Fetch last byte */
  theChar>>=(8-numBits);    /* Shift bits into position */
  switch (numBits) {
    ulong decode_tree;
startSlow:
    decode_tree = (ulong)t;
    do { 
      theChar =  *bitsP++;  /* get input byte */ 
      bitStart = 8;
slow0:                                /* process 0th bit */
case 0: ProcessBitSlow(0x80,8,0x7F,);
slow7:                                /* process 1st bit */
case 7: ProcessBitSlow(0x40,7,0x3F,);
slow6:                                /* process 2nd bit */
case 6: ProcessBitSlow(0x20,6,0x1F,);
slow5:                                /* process 3rd bit */
case 5: ProcessBitSlow(0x10,5,0x0F,); 
slow4:                                /* process 4th bit */
case 4: ProcessBitSlow(0x08,4,0x07,);
slow3:                                /* process 5th bit */
case 3: ProcessBitSlow(0x04,3,0x03,);
slow2:                                /* process 6th bit */
case 2: ProcessBitSlow(0x02,2,0x01,); 
slow1:                                /* process 7th bit */
case 1: ProcessBitSlow(0x01,1,0x00,continue);  

      theSym <<= bitStart;
      theSym |= theChar;
      theSymLng += bitStart;
      
      continue; /* continue with next char */
overflow:
      theSym <<= bitStart-theBitNum;
      theSym |= (theChar>>theBitNum);
      theSymLng += bitStart-theBitNum;                               
     
      theMask = 1<<(theBitNum-1);
      theChar &= (1<<theBitNum)-1;
      bitStart = theBitNum;

      /* search SymTab for theSym */
      saveCount = count;
      theSymElemPtr = (SymDecode *)
                        ((char *)privateHuffDataPtr + kSEP);
      theSymElemPtr += theSymLng-1;
search:
      sP = theSymElemPtr->symP;
      count = theSymElemPtr->numEntries;
      if (count) do {
        if (sP->sym < theSym) goto nextSP;
        if (sP->sym > theSym) goto noSym;
        *outP++ = sP->value;
        if (state != 0) goto done;
        theSymLng = 0;
        theSym = 0;
        theChar &= ((1<<theBitNum)-1);
        bitStart = theBitNum;
        count = saveCount;
        t = (char *)decode_tree;
        oneP = tP->oneP;
next:   switch (theBitNum) {
        case 8:
        case 0:  count = saveCount;
                 goto nextChar0;
        case 1:  goto slow1;
        case 2:  goto slow2;
        case 3:  goto slow3;
        case 4:  goto slow4;
        case 5:  goto slow5;
        case 6:  goto slow6;
        case 7:  goto slow7;
nextSP: ++sP;
        } /* end switch */
      } while (--count);
noSym:if (0 == theBitNum) {
        if (0==--saveCount) {
lastChar:
          if (state!=0) goto done;
          state=1;
          theChar = *bitsP;
          count = 1;
          theBitNum = 8;  theMask = 0x80;
        } else {
          theChar =  *bitsP++;  /* get input byte */ 
          theBitNum = 8;  theMask = 0x80;
        }
      }
      theSym<<=1;
      if (theChar&theMask) theSym|=1;
      --theBitNum;
      theMask>>=1;
      ++theSymElemPtr;
      goto search;
nextChar: 
      theSym <<= 8;
      theSym |= theChar;
      theSymLng += 8;
nextChar0: ;
    } while (--count);
    if ((state==0) && (numBits &= 7)) 
      goto doLeftOverBitsSlow;
  }
}
done: 
    return (char *)outP-(char *)outputPtr;  
}