Programmers' Challenge

By Mike Scanlin, MacTutor Regular Contributing Author

November 92 Programming Challenge of the Month

Millions of Colors?

Ever wonder how many of the 16,777,216 possible colors are really used in a typical 24-bit color image? Do you really need to run in 24-bit mode to appreciate certain images? Could some images be accurately represented as indexed color images instead, without any loss of color? Hmmm... The first thing you’d need to know is how many unique RGB values there are in the image, which would tell you how big your color lookup table would need to be. Let’s try it.

This month’s challenge is to quickly determine how many unique RGB values there are in a given 24-bit color image. The input to your function will be the dimensions and base address of an interleaved ARGB image:

unsigned long UniqueRGBValues(baseAddress, numRows, numCols)
PtrbaseAddress;
short   numRows, numCols;

The byte pointed to by baseAddress is the alpha byte of the upper left pixel. Following that are bytes for red, green and blue, which are then followed by the next set of ARGB values. You can ignore the alpha bytes completely when calculating unique RGB values. If you feel the need to allocate an array of 16,777,216 bits then, yes, you can assume your routine will have at least 2.5MBs free memory when called to do so (but remember that the time to initialize such an array is non-zero; there may be faster methods...).

Let’s say the maximum value for numCols is 640 and for numRows it’s 480. Your routine should be very fast for the average case but also be able to deal with the worst case where you have 640x480 unique RGB values.

We goofed

No two ways about it. In our rush to get the October issue out the door we were a little too hasty in determining the winner of the August MacTutor Challenge. Not more than 48 hours after the issue had gone to press (but before the stated challenge deadline had passed) we received a solution that was better than the one declared to be the winner. Our apologies to Greg Landweber (Princeton, NJ) who was the actual winner (and will also be receiving the prize). In order to prevent this from happening again in the future, we have moved the deadline up (see below).

The “deadline has now passed” winner of the “How many ways can you spell ‘CAT’” challenge is Will Galway (Salt Lake City, UT) whose entry was the only non-recursive one received. Take note recursion fanatics: Although recursion is a Good Thing conceptually (and in many cases practically), these monthly challenges are primarily about speed. We don’t need to contribute to the large body of existing slow code; we need faster code. Take a couple of No-Doze and study Will’s non-recursive alternative.

Thanks to Bob Barnhart (San Diego, CA) for his entertaining animated solution. Too bad it wasn’t as fast as it was fun to watch. Bob’s entry brings up another point as well: Please use a column width of 79 characters or less in your code. AppleLink (or the internet-AppleLink gateway, I’m not sure which) breaks lines longer than 80 characters and it’s a pain to manually fix them up when I get them. Thanks.

Here are Greg’s winning solution to the August Challenge (the real winner) and Will’s winning solution to the September Challenge (some comments have been removed for space reasons. The complete sources are on the source code disk):

Banded Pegs

/* Solution to the August 1992 MacTutor
 * Programmers' Challenge
 *
 * by Greg Landweber
 */

/* The number of holes in a row or column. */
#define max 13

void BandedPegs (numPegs, pegsPtr, numEdgePegsPtr,
 edgePegsPtr, areaPtr)
short numPegs;
Point *pegsPtr;
short *numEdgePegsPtr;
Point *edgePegsPtr;
Fixed *areaPtr;
{
 /* leftmost and rightmost peg in each row */
    short   xLeft[max],xRight[max];
 /* top and bottom rows containing pegs */
    short   top,bottom;
 /* horizontal and vertical coords. of peg */
    short   x,y;
 /* used to compute twice the enclosed area */
    short   area;
 /* number of pegs on left and right side */
    short   numLeft,numRight;
 /* array of pegs on left and right */
    Point   leftPegs[max],rightPegs[max];
 /* general use array index */
    short   index;
 /* for stepping through arrays of Points */
    Point   *pegPtr1,*pegPtr2;
 
/* Fill xLeft[v] and xRight[v] with the h-coords
 * of the leftmost and rightmost pegs in row v.
 * If there are no pegs in row v, then set
 *  xLeft[v]  = max, and
 *      xRight[v] = -1.
 * Note that any pegs inbetween the leftmost and
 * rightmost pegs in a row will automatically be
 * in the interior of the rubber band polygon.
 * This reduces the maximum number of pegs to 26.
 */
 
    for ( index = 0; index < max; index++ ) {
        xLeft [index] = max;
        xRight[index] = -1;
    }
 
    pegPtr1 = pegsPtr;
    for ( index = numPegs; index > 0; index-- ) {
        y = pegPtr1->v;
        x = pegPtr1->h;
        if ( x < xLeft [y] )
            xLeft [y] = x;
        if ( x > xRight[y] )
            xRight[y] = x;
        pegPtr1++;
    }
 
/* Find the bottom (lowest v) and top
 * (highest v) rows containing pegs. */

    bottom = -1;
    while ( xLeft [++bottom] == max );
 
    top = max;
    while ( xLeft [--top] == max );
 
/* Fill leftPegs[] with a list of all the pegs
 * on the left side of the convex polygon from
 * the top (hi v) to the bottom (lo v), and put
 * the number of those pegs - 1 in numLeft. */

 /* leftPegs[0] is the topmost (highest v) */
    leftPegs[0].h = xLeft[top];
 /* point on the left side of the polygon. */
    leftPegs[0].v = top;
 /* Index of the last peg in leftPegs[]. */
    numLeft = 0;
 
 /* Add pegs from the top to the bottom. */
    for (y = top - 1; y >= bottom; y--)
    /* Check if there is a peg in row y. */
        if ( (x = xLeft[y]) != max ) {
        /* Note thatpegPtr2 is the current
        * peg in the list and pegPtr1 is the
        * next. */ 
            pegPtr1 = leftPegs;
            pegPtr2 = pegPtr1++;
            for ( index = 0; index < numLeft; index++ )
            /* Is the peg at {x,y} to the left of
             * the line from *pegPtr1 to *pegPtr2? */
                if ( ( (x - pegPtr1->h) 
                    (pegPtr2->v - pegPtr1->v) ) <
                    ( (pegPtr2->h - pegPtr1->h) *
                    (y  - pegPtr1->v) ) )
                /* If so, all the pegs from pegPtr1 on
                 * will be to the right of the line
                 * from {x,y} to *pegPtr2, and so we
                 * remove them from the left peg list. */
                    numLeft = index;
                else
                /* If not, we go on to the next peg. */
                    pegPtr2 = pegPtr1++;
            /* Tack {x,y} onto the end of the list. */
            numLeft++;
            pegPtr1->v = y;
            pegPtr1->h = x;
        }

/* Fill rightPegs[] with a list of all the pegs
 * on the right side of the convex polygon from
 * the top (hi v) to the bottom (lo v), and put
 * the number of those pegs - 1 in numRight.
 */
 
 /* rightPegs[0] is the topmost (highest v)
  * point on the right side of the polygon. */
    rightPegs[0].h = xRight[top];
    rightPegs[0].v = top;

 /* Index of the last peg in rightPegs[]. */
    numRight = 0;

 /* Add pegs from the top to the bottom. */
    for (y = top - 1; y >= bottom; y--)
    /* Check if there is a peg in row y. */
        if ( (x = xRight[y]) != max ) { 
        /* Note that pegPtr2is the current peg */
        /* in the list and pegPtr1 is the next. */
            pegPtr1 = rightPegs;        
            pegPtr2 = pegPtr1++;        
            for ( index = 0; index < numRight; index++ )
            /* Is the peg at {x,y} to the right of
             * the line from *pegPtr1 to *pegPtr2?*/
                if ( ( (x - pegPtr1->h) *
                    (pegPtr2->v - pegPtr1->v) ) >
                    ( (pegPtr2->h - pegPtr1->h) *
                    (y - pegPtr1->v) ) )
               /* If so, all the pegs from pegPtr1 on
                * will be to the left of the line
                * from {x,y} to *pegPtr2, and so we
                * remove them from the right peg list. */
                    numRight = index;   
                else
                /* If not, we go on to the next peg.*/
                    pegPtr2 = pegPtr1++;
            numRight++;                 
            /* Tack {x,y} onto the end of the list. */
            pegPtr1->v = y;
            pegPtr1->h = x;
        }
 
/* Copy the contents of numLeft[] and
 * numRight[] into edgePegsPtr. */
    pegPtr2 = edgePegsPtr;

    pegPtr1 = leftPegs + 1;
    for ( index = numLeft - 1; index > 0; index-- )
        *(pegPtr2++) = *(pegPtr1++);

/* Do the pegs all lie on the same line?
 * If so, the left and right are the same.  */
    if ( *( (long *)leftPegs + 1 ) !=
        *( (long *)rightPegs + 1 ) ) {
        pegPtr1 = rightPegs + 1;
        for ( index = numRight - 1; index > 0; index-- )
            *(pegPtr2++) = *(pegPtr1++);
    }
 
/* Put all the pegs in the top and bottom
 * rows into edgePegsPtr. */
    pegPtr1 = pegsPtr;
    for ( index = numPegs; index > 0; index-- ) {
        if ( (pegPtr1->v == top) || (pegPtr1->v == bottom) )
            *(pegPtr2++) = *pegPtr1;
        pegPtr1++;
    }
 
/* Figure out how many pegs there are touching
 * the edge of the polygon. */
    *numEdgePegsPtr = pegPtr2 - edgePegsPtr;
 
/* Compute twice the area to the left of the
 * right side of the polygon. */
    area = 0;
 
/* The area of a trapezoid with height h and\
 * parallel sides of length a and b is h*(a+b)/2.
 * Here we have h = pegPtr2->v - pegPtr1->v,
 * a = pegPtr2->h, and  b = pegPtr1->h. */
    pegPtr1 = rightPegs;

/* Loop through all of the line segments on
 * the right side of the convex polygon. */        
    for ( index = numRight; index > 0; index-- ) {
        pegPtr2 = pegPtr1++;        
        area += (pegPtr2->v - pegPtr1->v) *
            (pegPtr2->h + pegPtr1->h);
    }
 
/* Subtract twice the area to the left of the
 * left side of the polygon. */
    pegPtr1 = leftPegs;             

/* Loop through all of the line segments on
 * the left side of the convex polygon. */
    for ( index = numLeft; index > 0; index-- ) {
        pegPtr2 = pegPtr1++;        
        area -= (pegPtr2->v - pegPtr1->v) *
            (pegPtr2->h + pegPtr1->h);
    }
 
/* Finally, divide by two and convert the
 * result to type Fixed. */
    *areaPtr = FixRatio( area, 2 );
}

How Many ways can you spell ’CAT‘

/* count-paths.h:  Declarations for count-paths.c
 *
 * Copyright (C) 1992,  William F. Galway
 *
 * Anyone can do what they like with this code,
 * as long as they acknowledge its author,
 * and include this message in their code.
 */
 
typedef int BOOL;
 
#define TRUE 1
#define FALSE 0
 
/* Possible target systems/compilers...  */
#define ThinkC 0
#define GnUnix 1
 
#if !defined(TARGET)
#define TARGET ThinkC
#endif
 
#if !defined(DEBUG)
#define DEBUG FALSE
#endif
 
#if !defined(VERBOSE)
#define VERBOSE FALSE
#endif
 
/* Maximum dimensions of the "matrix". */
#define MAXORDER 10
 
#if (TARGET==GnUnix)
/* This is the "Mac" StringPtr type.  The first
 * byte gives the length, the rest of the bytes
 * make up the string. */
typedef unsigned char Str255[256], *StringPtr;
 
/* Native is the type most naturally addressed,
 * roughly speaking...  */
typedef void Native;
#endif

#if (TARGET==ThinkC)
/* Native is the type most naturally addressed,
 * roughly speaking...  */
typedef char Native;
#endif
 
typedef struct locnode {
  /* Next node in list for a given character. */
    struct locnode *next;
} LocNode;
 
typedef struct {
    /* Number of entries per row...  */
    long dy;

    /* Vector of LocNodes indexed by
     * character code, giving first location
     * of character. */
    LocNode char_index[256];

    /* "Matrix" of LocNodes giving further
     * locations of each character. */
    LocNode index_matrix[(2+MAXORDER)*(2+MAXORDER)];
} Index;
 
/* BuildIndex builds up index for matrix of
 * given order. */
void BuildIndex(long order, const char *matrix,
 Index *index);
 
/* count_paths counts paths using previously
 * built index. */
long count_paths(const Index *index,
 const StringPtr word);
 
/* CountPaths is the "top level" path counting
 * routine. */
long CountPaths(short order, char *matrix,
 const StringPtr inputWordPtr);
 
/*-----------------------------------------*/
 
/* count-paths.c
 *
 * Copyright (C) 1992,  William F. Galway
 *
 * Anyone can do what they like with this code,
 * as long as they acknowledge its author,
 * and include this message in their code.
 */
 
/* The algorithm used by this implementation
 * avoids "combinatorial blowup" by working
 * backwards through the input word, keeping a
 * "count table" showing the number of paths for
 * the substring at each node.  For example, for
 * the string "CAR" we would get the following
 * counts (count tables) at each stage:
 *  -for "r":
 *     0  0  0
 *     0  1  0
 *     0  0  0
 *  -for "ar":
 *     0  0  0
 *     1  0  1
 *     0  1  0
 *  -for "car":
 *     1  0  1
 *     0  0  0
 *     0  0  2
 * giving a total of 4 solutions found at the
 * final stage. (This non-recursive approach is
 * reminiscent of the iterative versus the
 * recursive method of computing Fibonacci
 * numbers.)
 *
 * We actually keep two count tables around, one
 * giving counts for the "previous stage" (the
 * "previous table"), and one being built up for
 * the "current stage" (the "current table"). We
 * build the current table by locating occurrences
 * of the leading character of the substring, and
 * then summing the counts from the four
 * neighboring locations in the previous table. 
 * To ease the problem of dealing with the edges
 * of the tables, we allocate "dummy" rows and
 * columns at the edges of our count tables. The
 * counts at the edges always remain zero, while
 * the interesting stuff goes on in the interior
 * of the tables.
 *
 * To simplify (and speed up) the task of locating
 * occurrences of characters in the matrix, we
 * first build an "index" for the matrix which is
 * basically a linked list of pointers and then
 * index into the index (!) by the character that
 * we need the location(s) of. The index needs
 * building only once for a given matrix, after
 * which the count_paths routine may be called
 * (see how CountPaths invokes count_paths below).
 *
 * Other points to note:
 *
 *  -- Use of "Native" pointers for less "pointer
 *     arithmetic".
 *  -- The result returned by CountPaths is more
 *     properly interpreted as an unsigned long
 *     rather than as a signed long.
 *  -- These routines are not robust when called
 *     with matrices of order outside the range
 *     1..MAXORDER.
 */
 
#include "count-paths.h"
#include <stdio.h>
 
/* Build up index for matrix of given order.  */
void BuildIndex(long order, const char *matrix,
 Index *index)
{
    register unsigned char *chrp;
    register LocNode *spot, *spot2;
    long i,j;
 
    /* Zero out the char_index (256 entries).  */
    spot = index->char_index;
    spot2 = spot+256;
    do {
        (spot++)->next = NULL;
    } while (spot < spot2);
 
    /* Build up the index... The c'th entry in
     * char_index points to a chain of pointers
     * residing in index_matrix...  Note that
     * "edge" rows and columns are allowed to
     * contain nonsense. */

    spot = index->index_matrix+order+3;
    chrp = (unsigned char *)matrix;
    i = order;
    do {
        j = order;
        do {
            /* char_index[char] points to head of
             * chain for char. Set spot pointed at
             * to point to "next" spot with ch in
             * it (as previously stored in
             * char_index). */
            spot2 = &index->char_index[*chrp++];
            spot->next = spot2->next;
            spot2->next = spot++;
        } while (--j);

        /* Skip last & first columns of row. */
        spot += 2;
    } while (--i);
  
    index->dy = order+2;
 
    return;
}
 
/* Count paths using previously built index. */
long count_paths(const Index *index, const StringPtr word)
{
    register unsigned char *chrp;
    register long dyoffset;

    /* tbl_offset gives offset from "current
     * counts" table to "previous counts" table. 
     * i.e., previous_counts =
     * current_counts+tbl_offset. */
    long tbl_offset;

    /* current_offset, previous_offset give
     * offset from index->index_matrix to
     * current/previous count tables. */
    register long current_offset;
    register long previous_offset;
    LocNode *spot;
    long *countp;
    register long total;
    long count_tables[2*(2+MAXORDER)*(2+MAXORDER)];
 
    /* Point chrp to last char of word. */
    chrp = word + *word;
 
    /* Initialize misc offsets, pointers. */
    dyoffset = index->dy*sizeof(long);

    /* (short) avoids subroutine call for
     * multiply for some systems. */
    tbl_offset = (short)(index->dy)*(short)dyoffset;
    current_offset = (Native *)count_tables-
        (Native *)(index->index_matrix);
    previous_offset = tbl_offset+current_offset;
 
    /* Zero out the count tables. */
    countp=count_tables;
    do {
        *countp++ = 0;
    } while (countp < (long *)((Native *)
        count_tables+2*tbl_offset));
  
    total = 0;
 
    /* Initialize counts for "previous table".
     * (It will soon be previous!) */
    for (spot=(index->char_index)[*chrp].next;
        spot!=NULL; spot=spot->next) {
        *(long *)((Native *)spot+previous_offset) = 1;
        total++;
    }
 
    if (total==0 || --chrp<=word)
        return total;
 
    while (TRUE) {
        total = 0;
        for (spot=(index->char_index)[*chrp].next;
            spot!=NULL; spot=spot->next) {
            countp = (long *)((Native *)spot +
                previous_offset);

            /* Hairy expression avoids variable,
             * may free up register... */
            total += *(long *)((Native *)spot +
                current_offset) = *(countp-1) +
                *(countp+1) + *(long *)((Native *)
                countp-dyoffset) + *(long *)
                ((Native*)countp+dyoffset);
        }

        if (total==0 || --chrp<=word)
            return total;
 
      /* Swap "current" and "previous" count
       * tables. */
        current_offset += tbl_offset;
        previous_offset -= tbl_offset;
        tbl_offset = - tbl_offset;
         /* Zero out current counts, only need
         * touch non-zero entries. */
        for (spot=(index->char_index)[*(chrp+2)].next;
            spot!=NULL; spot=spot->next) {
            *(long *)((Native *)spot + current_offset) = 0;
        }
    }
}


long CountPaths(short order, char *matrix,
 const StringPtr inputWordPtr)
{
    long ord=order;
    Index index;
 
    /* Problem statement restricts word length to
     * be >0, but be paranoid since
     * count_paths(...) is not robust for 0 length
     * words. Return 0 if empty (zero length)
     * word. */
    if (*inputWordPtr == 0) {
        return 0;
    } else if (*inputWordPtr == 1) {
        /* Avoid work of building index, etc. for
         * length one words. */
        register char ch=(char)inputWordPtr[1];
        char *chrp = matrix;
        long total=0;
 
        do {
            if (ch == *chrp++) {
                total++;
            }
        } while (chrp < matrix+order*order);
        return total;
    } else {
        /* Invoke count_paths after building the
         * index... */
        BuildIndex(ord, matrix, &index);
        return count_paths(&index, inputWordPtr);
    }
}