Nov 92 Challenge
Volume Number: 8
Issue Number: 7
Column Tag: Programmers' Challenge
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)
Ptr baseAddress;
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.