Programmer’s Challenge

By Bob Boonstra

Connect IV

This month, your Challenge is to write code for a well-known game that will compete against other Challenge entries, as well as against the clock. The game board consists of an NxM array into which two players alternate inserting pieces. Pieces are inserted into the top of a column in the vertically oriented board, so that they drop into the lowest unoccupied cell of that column. The objective is to be the first player to arrange 4 or more pieces into a vertical, horizontal, or diagonal line.

The winner of this Challenge will be determined by a round-robin tournament in which each entry competes against each other entry an even number of times, half of the time playing with the first move, and half playing with the second move. (If the number of entries makes a full round-robin tournament impractical, I’ll use another fair tournament scheme.) Each tournament victory will earn two points for the winning entry, and each tie earns one point. The entry with the greatest number of tournament points wins the Challenge. Ties will be broken by execution time, code size, etc.

The prototype for the code you should write is:

long /*yourMove*/ ConnectMove (
 long numCols,   /* number of columns in the game board */
 long numRows,   /* number of rows in the game board */
 void *privStorage,/* preallocated storage for your use */
 long prevMove,  /* column where opponent last moved, 0 ..  numCols-1 */
 Boolean newGame,/* TRUE if this is your first move in a new game */
 Boolean *victory/* set to TRUE if you claim victory */
    /*   this move, otherwise set to FALSE */
);

For your first move in a new game, your ConnectMove code will be called with newGame set to TRUE. If your opponent made the first move in this game, prevMove will be set to the (origin zero) column that the opponent selected as the first move. If you are to make the first move, prevMove will be set to -1. In the call for the first move of a new game, you will also be provided with a pointer privStorage to 1MB of memory, already initialized to zero, for your use during that game. Finally, the initial call will provide the number of columns (numCols) and rows (numRows) in the board for that game. The number of rows and columns will each be larger than 6 and less than 64.

Alternating calls will be made to your ConnectMove routine and the opposing ConnectMove routine. For the second and subsequent moves in each game, newGame will be set to FALSE, and the values of numCols, numRows, and privStorage will be the same as in the initial call. Each time ConnectMove is called, you should evaluate the move made by your opponent (provided in prevMove) and return the column into which you make your move as the function result. If you believe you have won the game, you should set *victory to TRUE; otherwise you should set *victory to FALSE. Falsely claiming victory or making an illegal move, such as trying to insert a game piece into a column that is already filled, will result in forfeiting that game.

For this Challenge, you may dynamically allocate additional storage beyond that provided by privStorage, provided you deallocate it before returning after each move. You may not use any static storage beyond that provided by privStorage.

To conduct the tournament, the code for multiple entries will be compiled into a single application. In case you are wondering, I will append a unique integer to the name of each routine before compiling so that each ConnectMove routine will be named uniquely.

This will be a native PowerPC Challenge, scored using the Symantec environment. Solutions may be coded in C or C++.

Two Months Ago Winner

Perhaps the earlier Challenge deadline caught people a little off guard this month. Whatever the reason, only three people chose to enter the Edge Detector Challenge this month. Congratulations to Ernst Munter (Kanata, ON, Canada) for submitting the fastest entry to the Edge Detector Challenge. This is Ernst’s third win in the last four contests, and it brings him within 2 points of the lead in our Top Contestants point total.

Contestants were required to process PixMap images in 8-bit, 16-bit, or 32-bit color and identify pixels where the color difference with adjacent pixels exceeded a specified threshold in the specified color component (or combination of components). The second place solution by Miguel Cruz Picao was actually faster than the winning solution in two of the three color depth cases, but was slower in the third case and slower overall. Miguel elected to implement entirely separate code for each of the three color depth cases, while Ernst sacrificed some processing time for smaller code size by testing for color depth while processing each line of the image, using common code for the rest of the three cases. On the other hand, Ernst used the EdgeType provided as a parameter to select, outside of any loops, the edge detection routine to use for the entire image, while Miguel’s code tested the EdgeType for each pixel. Ernst elected to make four passes through each pair of adjacent image lines, comparing pixels that were adjacent horizontally, diagonally in each direction, and vertically, allowing compact and efficient comparison loops. The overall result was that the winning solution was some 25% faster than the second-place solution in the 32-bit case, which was enough to make it about 5% faster overall.

Table 1 summarizes the results for each entry, including code size, data size, execution time for each of the three color depth cases, and the overall score based on total execution time. Numbers in parentheses after a person’s name indicate that person’s cumulative point total for all previous Challenges, not including this one.

Name Code Data Time Time Time Score

Ernst Munter (154) 1492 116 833 912 723 2467

Miguel Cruz Picao (11) 3420 20 1120 899 582 2600

Greg Cooper 1872 28 1830 1902 1802 5534

Table 1. Results for each entry

1. [Name deleted] 176 11. Mallett, Jeff 44

2. Munter, Ernst 174 12. Kasparian, Raffi 42

3. Gregg, Xan 92 13. Vineyard, Jeremy 42

4. Karsh, Bill 90 14. Lengyel, Eric 40

5. Larsson, Gustav 87 15. Darrah, Dave 31

6. Stenger, Allen 65 16. Brown, Jorg 30

7. Cutts, Kevin 57 17. Lewis, Peter 30

8. Riha, Stepan 51 18. Landry, Larry 29

9. Goebel, James 49 19. Beith, Gary 24

10. Nepsund, Ronald 47 20. Elwertowski, Tom 24

Table 2. Top 20 contestants

Top 20 Contestants of All Time

Table 2 shows the Top 20 Contestants for the Programmer’s Challenges to date The numbers below include points awarded for this month’s entrants.

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 5th place 2 points

2nd place 10 points finding bug 2 points

3rd place 7 points suggesting Challenge 2 points

4th place 4 points

Here is Ernst’s winning solution:

EdgeDetector.c

Copyright 1996, Ernst Munter

/*
Problem Statement
---------
Given a Pixmap image, create a Bitmap which shows the edges in the image.

Pixmaps may have 8, 16, or 32 bit colors. Parameters control which colors should contribute to the edge 
detection, and a threshold for the color space difference (an RMS value) to be considered an edge.

All 16 bits of the individual color values must be considered, which can result in 32-bit overflow when squares 
are added.

Solution
----
The general idea is to process 2-row strips of the image through an intermediate ColorSpec stage in which 
the “value” fields are used to mark edge pixels. 

Step1:

We allocate a small amount of memory, sufficient to hold two rows of pixels in ColorSpec format (8 bytes 
per pixel). Pixels from each row in the Pixmap are converted to ColorSpec format (RGB + “value”).

Step2:

The two lines are scanned with 4 different patterns to determine edges:  given 2 rows with pixels as shown

 A B C D E F G H ...
 a b c d e f g h ...

We compare pixel pairs in four separate runs of EdgePairs():
 a-b, b-c, c-d, d-e ...  (WEST - EAST)
 A-b, B-c, C-d, D-e ...  (NORTH-WEST - SOUTH-EAST)
 B-a, C-b, D-c, E-d ...  (NORTH-EAST - SOUTH-WEST)
 A-a, B-b, C-c, D-d ...  (NORTH - SOUTH)

This procedure is repeated for rows 0 and 1, then 1 and 2, 2 and 3, and so on.  (Plus an West-East run for 
row 0).

During each run, the “value” field of every pair of pixels found to be part of an edge is set to -1 (0xFFFF). 
All other values remain at 0.

Step 3:

Before shifting down to the next row, the ColorSpecs of the upper row are scanned to construct a row of 
the Bitmap.

Optimizations
-------
The combinations of pixel size and edge types are dealt with as follows:

All pixel types are normalized to a single ColorSpec format by the GetLine procedure.

Different edge types call for different series of tests.  Specifically, 1, 2, or 3 colors can be optimized separately. 
On of a set of 7 separate short functions is selected at runtime.  This requires the edge type to be evaluated 
only once, to select the EdgeXXX procedure that will be used many times as the image is scanned from top 
to bottom.

Comparing an RMS (root of sum of squares) value with a threshold is equivalent to comparing the sum of 
squares with the square of the threshold value.  This avoids the need to compute square roots.

In the case of a single color edge type, the square of the difference would not need to be formed.  A simple 
comparison of the threshold with the absolute difference would suffice.  However, the runtime difference 
between a multiply and computing the absolute value would depend on CPU type etc, and would tend to be 
small.  I opted for uniformity, and square all differences.

The dynamically allocated storage should typically fit inside the CPU cache, and not slow things down as 
it is read and written continuously.

Assumptions
------
Bitmap is large enough to hold the result.  eType is within the range of redOnly to redGreenAndBlue, otherwise 
the call will certainly crash.

Amount of static memory = 8 pointers (32 bytes)
Amount of dynamic memory required is for 2 rows of
ColorSpec records (a 1024 pix wide image -> 16K of storage).

*/

#include <QDOffscreen.h>
// Contains PixMap, BitMap and EdgeType defs

#include <stdlib.h>

Definitions
typedef enum
{
 redOnly = 1,
 greenOnly,
 redAndGreen,
 blueOnly,
 redAndBlue,
 greenAndBlue,
 redGreenAndBlue
} EdgeType;

typedef void EdgeProc(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

Function Prototypes
void EdgeDetect(
 PixMapHandle    pMapH,
 BitMap *bMap,
 unsigned short  threshold,
 EdgeType eType);

void Get1Line(
 ColorSpec* line,
 void*  pix,
 int    size,
 ColorSpec* CT,
 int    pixelSize);

void EdgeRed(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void EdgeGreen(
 ColorSpec* P,
 ColorSpec*    Q,
 int    size,
 unsigned long   TH);

void EdgeRedGreen(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void EdgeBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void EdgeRedBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void EdgeGreenBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void EdgeRedGreenBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH);

void Copy2Bitmap(
 ColorSpec* P,
 unsigned char*  bits,
 int    size);

Static Allocations
static EdgeProc* EdgeProcedure[8] = {
 0,
 EdgeRed,
 EdgeGreen,
 EdgeRedGreen,
 EdgeBlue,
 EdgeRedBlue,
 EdgeGreenBlue,
 EdgeRedGreenBlue};

EdgeDetect
void EdgeDetect(
 PixMapHandle    pMapH,
 BitMap *bMap,
 unsigned short  threshold,
 EdgeType eType) {
PixMap* pm=*pMapH;

unsigned char*   pix=(unsigned char*)GetPixBaseAddr(pMapH);
unsigned char*   bits=(unsigned char*)bMap->baseAddr;
unsigned long  TH=(unsigned long)threshold*threshold;
int     y;
int     pixelSize=pm->pixelSize;
int     pixRowBytes=pm->rowBytes & 0x3FFF;
int     pixInRow=pm->bounds.right-pm->bounds.left;
int     bitRowBytes=bMap->rowBytes;

ColorSpec*  allocated;
ColorSpec*  line0;
ColorSpec*  line1;
ColorSpec*  CTable=(*(pm->pmTable))->ctTable;
EdgeProc* EP;

// Get memory for a 2-row strip of pixels:
  if (0==(allocated=(ColorSpec*)malloc(
 2*sizeof(ColorSpec)*pixInRow))) return;
  line0=allocated-1;  //(we always use pre-increment later)
  line1=line0+pixInRow;

// Determine EdgeProc to use:
  EP=EdgeProcedure[eType];

// Prepare first row:
  Get1Line(line0,pix,pixInRow,CTable,pixelSize);
  (*EP)(line0,line0+1,pixInRow-1,TH);    //W-E

// Process remaining rows:
  for (y=pm->bounds.top+1;y<pm->bounds.bottom;y++) {
    pix+=pixRowBytes;
    Get1Line(line1,pix,pixInRow,CTable,pixelSize);
                                                             
    (*EP)(line1,  line1+1,pixInRow-1,TH);  //W-E
    (*EP)(line0,  line1+1,pixInRow-1,TH);  //NW-SE
    (*EP)(line0+1,line1,  pixInRow-1,TH);  //NE-SW
    (*EP)(line0,  line1,  pixInRow,TH);    //N-S

// Convert ColorSpec.values to Bitmap.bits:
    Copy2Bitmap(line0,bits,bitRowBytes);

// Swap line0 with line1:
    {ColorSpec* temp=line0;line0=line1;line1=temp;}
    bits+=bitRowBytes;
  }

// Convert the last row;
  Copy2Bitmap(line0,bits,bitRowBytes);

// Release dynamic memory:
  free(allocated);
}

Get1Line
/***************** Local Functions ************************/
void Get1Line(
 ColorSpec* line,
 void*  pix,
 int    size,
 ColorSpec* CT,
 int    pixelSize){
inti,r,g,b;
unsigned long  x;
  if (pixelSize==8) {
    unsigned char*   PIX =((unsigned char*)pix);
    for (i=0;i<size;i++) {
      x=*PIX++;
      line++;
      *((double*)(line))=*((double*)(CT+x));
      line->value=0;
    }
  } else if (pixelSize==16) {
    unsigned short*  PIX =((unsigned short*)pix);
    for (i=0;i<size;i++) {
      x=*PIX++;
      line++;
      r=((x & 0x7C00) << 1)  | ((x & 0x7C00) >> 4) |
 ((x & 0x7C00) >> 9)  | ((x & 0x7C00) >> 14);
      g=((x & 0x03E0) << 6)  | ((x & 0x03E0) << 1) |
 ((x & 0x03E0) >> 4)  | ((x & 0x03E0) >> 9);
      b=((x & 0x001F) << 11) | ((x & 0x001F) << 6) |
 ((x & 0x001F) << 1)  | ((x & 0x001F) >> 4);
      line->value=0;
      line->rgb.red=  (unsigned short)r;
      line->rgb.green=(unsigned short)g;
      line->rgb.blue= (unsigned short)b;
    }
  } else { //pixelSize not 8 or 16, so it must be 32
    unsigned long* PIX =((unsigned long*)pix);
    for (i=0;i<size;i++) {
      x=*PIX++;
      line++;
      r=((x & 0xFF0000) >> 8) | ((x & 0xFF0000) >> 16);
      g= (x & 0x00FF00)       | ((x & 0x00FF00) >> 8);
      b= (x & 0x0000FF)       | ((x & 0x0000FF) << 8);
      line->value=0;
      line->rgb.red=  (unsigned short)r;
      line->rgb.green=(unsigned short)g;
      line->rgb.blue= (unsigned short)b;
    }
  }
}

Copy2Bitmap
void Copy2Bitmap(
 ColorSpec* P,
 unsigned char*  bits,
 int    size) {
int     i;
  P++;
  for (i=0;i<size;i++) {
    *bits = (unsigned char) (
     (P[0].value & 0x80) |
     (P[1].value & 0x40) |
     (P[2].value & 0x20) |
     (P[3].value & 0x10) |
     (P[4].value & 0x08) |
     (P[5].value & 0x04) |
     (P[6].value & 0x02) |
     (P[7].value & 0x01) );
    P+=8;
    bits++;
  }
}

EdgeRedGreenBlue
void EdgeRedGreenBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  delta,acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.red-Q->rgb.red;
    acc*=acc;
    delta=(unsigned long)P->rgb.green-Q->rgb.green;
    delta*=delta;
    acc+=delta;
    if (acc<delta) {P->value=Q->value=-1;continue;}
    delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
    delta*=delta;
    acc+=delta;
    if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  }
}

EdgeGreenBlue
void EdgeGreenBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  delta,acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.green-Q->rgb.green;
    acc*=acc;
    delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
    delta*=delta;
    acc+=delta;
    if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  }
}


EdgeRedBlue
void EdgeRedBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  delta,acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.red-Q->rgb.red;
    acc*=acc;
    delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
    delta*=delta;
    acc+=delta;                                    
    if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  }
}

EdgeRedGreen
void EdgeRedGreen(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  delta,acc;
   for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.red-Q->rgb.red;
    acc*=acc;
    delta=(unsigned long)P->rgb.green-Q->rgb.green;
    delta*=delta;
    acc+=delta;
    if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  }
}

EdgeBlue
void EdgeBlue(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.blue-Q->rgb.blue;
    acc*=acc;
    if (acc>=TH) P->value=Q->value=-1;
  }
}

EdgeGreen
void EdgeGreen(
 ColorSpec* P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.green-Q->rgb.green;
    acc*=acc;
    if (acc>=TH) P->value=Q->value=-1;;
  }
}

EdgeRed
void EdgeRed(
 ColorSpec*    P,
 ColorSpec* Q,
 int    size,
 unsigned long   TH) {
int     i;
unsigned long  acc;
  for (i=0;i<size;i++) {
    P++;Q++;
    acc=(unsigned long)P->rgb.red-Q->rgb.red;
    acc*=acc;
    if (acc>=TH) P->value=Q->value=-1;
  }
}