TweetFollow Us on Twitter

Oct 01 Challenge

Volume Number: 17 (2001)
Issue Number: 10
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Programmer's Assistant

How often has this happened to you? You're working on a piece of code, perhaps even a piece of Challenge code, you add a couple of lines, you compile, and you get some bizarre error. Something nothing near where you were editing. Perhaps an "Illegal function definition ..." in a routine you weren't even working on. And then you realize, eventually if you are slow, or immediately if you are less slow, that you added an "if (condition) {" statement and omitted the closing brace. Or some other simple syntax error.

Well, I happen to think that computers ought to be able to help us with this. My editor ought to do more to help me avoid mistakes. Yes, I know that some editors will balance parentheses for you, assuming you remembered to type the closing paren. But I want more. And this month's Challenge asks you to write such an editor for C/C++.

The first required feature is auto-completion of key words and user-defined names. For example, if I have defined variables "loop_index" and "loop_counter", then, after I type enough characters to uniquely identify a variable name (e.g., "loop_i"), my programmer's assistant should supply the remaining letters "ndex". The automatically supplied characters should be selected so that they are replaced in the event I continue typing. As a highly desirable optional feature, the assistant should offer me an auto-completion key (e.g., the option key, or a menu item with a keyboard equivalent), which, when pressed, offers me a popup menu of possible completions for the word currently being typed, even when the completion is not uniquely identified.

The second required feature is auto-completion of syntactic elements. If I start a conditional by typing "if", my programmer's assistant should, when prompted by an auto-completion key, complete the conditional by inserting parentheses, braces, and an "else" clause, leaving something like this:

if () {
} else {
}

In this example, the cursor ought to be left between the parentheses, so that I can insert the conditional. You ought to provide some convenient way for me to move the cursor from the conditional (between the parentheses) to the TRUE branch (between the first pair of braces) to the FALSE branch (between the second pair of braces).

You would provide similar auto-completion for while loops, do loops, for loops:

while () {
}

for ( ; ; ) {
}

do {
} while ();

Other required auto-completions include case statements, struct declarations, enum declarations, and function declarations. Additional auto-completion features may be incorporated at your option. Other options (e.g., indentation styles) will also earn extra feature points.

A significant amount of extra consideration will be given to any solution that allow support for other languages, through use of a configuration file, provided such a configuration file is provided for C/C++ and at least one other language.

This will be a native PowerPC Challenge, using any of the following environments: CodeWarrior, REALbasic (version 3.2.1 or earlier), MetaCard (version 2.3.2 or earlier), Revolution (version 1.0), or Project Builder. You may use another development environment if I can arrange to obtain a copy - email progchallenge@mactech.com to check before you use something else. You can develop for Mac OS 9 or Mac OS X. This will be another Challenge based on a subjective evaluation of which entry best satisfies the required features, provides the most attractive set of optional features, and provides the best general usability and look-and-feel. Your solution should be a complete Macintosh application, so there is no prototype and no test code for this Challenge. Your submission should provide everything needed to build your application, as well as documentation of the features you have implemented, to ensure that I don't overlook anything.

Three Months Ago Winner

Only two people chose to enter the July DownNOut Challenge, and many-time champion Ernst Munter is once again our winner. The object of this Challenge was score as many points as possible while removing colored cells from a rectangular board. Cells are removed when they match the color of a selected cell and are connected to that cell via cells of the same color that are adjacent horizontally or vertically. The number of points earned for each move is the square of the number of cells removed, so there is an incentive to remove cells in the largest blocks possible. Solutions were required to display and update the game state after each move.

Ernst observes in his commentary that the time penalty discourages spending a lot of time searching alternative moves, so his solution relies on heuristics. His first step for each move is to identify all contiguous areas of cells (CreateAreas) and calculate their size. Next, he picks a target color for the move, with the objective of removing a large number of cells for that color in a later move. Ernst selects the color which has the smallest score based on the initial position of contiguous areas of cells, on the theory that removing the colors with larger initial contiguous areas will both score points and allow the smaller areas to coalesce. Once the target color is selected, Ernst tries to remove the smallest area of another color (GetSmallestArea1) that is nearest the top of the game board, and which has cells of the same color below it (a "shadow"). Failing that, he removes the smallest area of the target color. If no such areas are available, he chooses another target color and begins again.

I used a total of six test cases to evaluate the solutions, ranging in size from 8x25 to 20x40 cells, with 3, 4, or 5 cell colors. The table below lists, for each of the solutions submitted, the total number of points earned by removing cells over all test cases, the execution time in milliseconds, and the score. The score subtracts from the points earned a penalty of 1% for each millisecond of execution time, calculated individually for each test case. The table also lists 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.

Name Points Time Score
(msec)
Ernst Munter (758) 91632 236 25337
J. T. 52666 4536 -561692
Name Code Data Lang
Ernst Munter 10028 458 C++
J. T. 7192 340 C

Top Contestants ...

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 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
(24 mo)
1. Munter, Ernst 271
2. Rieken, Willeke 73
3. Saxton, Tom 71
4. Taylor, Jonathan 56
5. Wihlborg, Claes 49
6. Shearer, Rob 48
7. Maurer, Sebastian 38
10. Mallett, Jeff 20
11. Truskier, Peter 20
Name Wins Total Points
(24 mo)
Munter, Ernst 10 778
Rieken, Willeke 3 134
Saxton, Tom 2 189
Taylor, Jonathan 2 56
Wihlborg, Claes 2 49
Shearer, Rob 1 62
Maurer, Sebastian 1 108
Mallett, Jeff 1 114
Truskier, Peter 1 20

...and the Top Contestants Looking for a Recent Win

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

Rank Name Points Total
(24 mo) Points
8. Boring, Randy 32 144
9. Sadetsky, Gregory 22 24
12. Schotsman, Jan 14 14
13. Nepsund, Ronald 10 57
14. Day, Mark 10 30
15. Downs, Andrew 10 12
16. Desch, Noah 10 10
17. Duga, Brady 10 10
18. Fazekas, Miklos 10 10
19. Flowers, Sue 10 10
20. Strout, Joe 10 10
21. Nicolle, Ludovic 7 55
22. Hala, Ladislav 7 7
23. Leshner, Will 7 7
24. Miller, Mike 7 7

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 DownNOut solution:

DownNOut.cpp
Copyright © 2001
Ernst Munter

/*
Copyright © 2001, Ernst Munter, Kanata, ON, Canada.
 
      "Down-N-Out"
      
A solitaire game where colored stones are placed in a vertical grid of rows and
columns. Adjacent stones of the same color form groups which can be removed as
long as a group contains at least two stones. After each move, consisting of the 
removal of a group of stones from one or more columns, remaining stones slide down 
in each column. Empty columns are filled by shifting ajacent columns towards the 
center. The score is the sum of the squares of the number of stones in each move. 

The standard game will have three colors with 100 stones each, on a board of 10 rows 
and 30 columns.

Strategy
————
I select a target color and aim to make all the stones of of this color into a 
single contiguous group, by removing all groups of the other colors first.

As stones are removed, and others slide down, some groups may be separated and 
others newly formed. Hence, by careful play, and with some luck in picking the
right candidate, one can almost always assemble most of the stones of one color 
into one large group - when playing manually.

The time penalty in this challenge is 1% per millisecond of time. Hence, there is
not a lot of time for searches or backtracking. I have chosen to go with a few
heuristics which captures most of the stones in a single big move at the end (yielding 
a score of near 10,000), in about half of the games played. Just as often, however, 
it fails to provide a bridge, and the final pay-off is considerably less:

   ideally, 100 * 100 = 10,000, for a single move of all 100 stones of a color
   but 50 * 50 + 50 * 50 = 5,000 if two moves of 50 stones each are needed.
   
Display and Timing
—————————
The display of the board uses ColorQuickDraw PaintRect(), directly to the window.
A number of experiments with off-screen GWorlds did not result in any improvements.
The time to compute all the moves of a typical game is on the order of 2.5 msec, 
for a 2.5% penalty (display disabled); with the display on, the time increases
to 12.5msec overall. 
*/
#define NDEBUG
#include <assert.h>
#include <stdlib.h>
#include "DownNout.h"

#define SHOWCELLS 1   // May be set to 0 for timing without the display

enum {
   kMaxNumColors   = 18,   // 16 cell colors + white + black
   kMaxCellSize   = 8,   // dont draw them larger than this
   kMinCellSize   = 2      //           or smaller than this
};

const RGBColor myColors[kMaxNumColors]={
   {0xFF00,0xFF00,0xFF00},   //white
   {0xFFFF,0x0000,0x0000},   //red
   {0x0000,0xFFFF,0x0000},   //green
   {0x0000,0x0000,0xFFFF},   //blue
   
   {0xFFFF,0xFFFF,0x0000},   //yellow
   {0xFFFF,0x0000,0xFFFF},   //pink
   {0x0000,0xFFFF,0xFFFF},   //light blue-1
   
   {0xFFFF,0x9999,0x3333},   //brown-1
   {0xFFFF,0x3333,0x9999},   //light purple
   {0x9999,0xFFFF,0x3333},   //light green
   {0x9999,0x3333,0xFFFF},   //violet
   {0x3333,0xFFFF,0x9999},   //emerald
   {0x3333,0x9999,0xFFFF},   //light blue-2
   
   {0xCCCC,0x9999,0x6666},   //brown-2
   {0x6666,0xCCCC,0xCCCC},   //blue-3
   {0xCCCC,0x6666,0xCCCC},   //purple
   {0x5F00,0x5F00,0x5F00},   //gray
   {0x0000,0x0000,0x0000}   //black
};

static long gCellSize;   // final size of squares for drawing
static WindowPtr win;   // the window provided by caller during InitDownNOut()

typedef long MyCellColor;   // faster than CellColor=char

/*******************************************************************
/
/                     Class MyCell
/
/*******************************************************************/

class ColorSquare
// Defines the screen location and color of each cell, and draws it.
{
   Rect      rect;
   MyCellColor   color;
public:
   void Init(const Point& spt,const MyCellColor cc,long cellSize)

   {
      rect.top=spt.v+1;      // leave a 1-pixel white margin
      rect.left=spt.h+1;
      rect.bottom=spt.v+cellSize;
      rect.right=spt.h+cellSize;
      color=cc;
   }
   MyCellColor Color() const {return color;}
   
   void CopyColor(const MyCellColor xcolor) {color=xcolor;}
   
   void ClearColor() {color=0;}
   
   void Show()
   {
      RGBForeColor(myColors+color);
      PaintRect(&rect);
   }
};

/*******************************************************************
/
/                     Class MyCell
/
/*******************************************************************/

class MyCell:public ColorSquare
// Defines the logical position on the board, and a few flags 
{

private:
   long      tag;   // unique tag for each area
   short      row;   
   short      col;
   bool      seen;   // semaphore for recursive search
   bool      touch;   // indicates need to redraw this square
public:

   void Init(const Point& spot,const MyCellColor cc,
          long rrow,long ccol,long cellSize)
   {
      ColorSquare::Init(spot,cc,cellSize);
      row=rrow;
      col=ccol;
      tag=0;
      seen=false;
      touch=true;
   }

   long    Row() const {return row;}
   long    Col() const {return col;}
   
   void Tag(long t) {tag=t;}
   bool IsTagged(const long t) const {return (tag==t);}
   
   void See() {seen=true;}
   bool IsSeen() const {return seen;}
   void UnSee() {seen=false;}
   
   void Touch() {touch=true;}
   
   bool IsBlank() const {return (Color()==0);}
   
   void CopyBack(CellColor* b) {*b=Color();}
   
   void CopyColor(const MyCell* x) 
   { 
      if (Color() != x->Color())
      {
         touch=true;   
         ColorSquare::CopyColor(x->Color());
      } // else no change in color, no need to reassign or redraw
   }
   
   void ClearColor() {
      if (Color() != 0)
      {
         touch=true;
         ColorSquare::ClearColor();
      } // else no change in color, no need to reassign or redraw
   }
   
   int CompPosition(MyCell* x)
// Comparison member function for qsort
   {
      int dCol=col - x->col;// sort left to right
      if (dCol==0)
         return x->row - row;// and top to bottom
      return dCol;
   }
   
   void   Show()
// Draws the cell if it has changed
   {
      if (touch)
      {
         ColorSquare::Show();
         touch=false;

      }

   }

};

typedef MyCell* MyCellPtr;

static int CompCells(const void* a,const void* b)
// Comparison function for qsort
{
   MyCellPtr* ah=(MyCellPtr*)a;
   MyCellPtr* bh=(MyCellPtr*)b;
   MyCell* ap=*ah;
   MyCell* bp=*bh;
   return ap->CompPosition(bp);

}

/*******************************************************************
/
/                     Class Area
/
/*******************************************************************/

class Area
// An area is identified with one of its cells, and describes the size
// of the area, i.e. the number of contiguous equal-colored cells.
{
   MyCell*   ref;      // pointer to one cell in the area
   long   size;      // number of cells in area
public:
   void Init(MyCell* C,long areaSize)
   {
      ref=C;
      size=areaSize;
   }
   long Size() const {return size;}
   
   MyCellColor Color() const {return ref->Color();}
   
   MyCell* Cell() const {return ref;}
   
   void GetMove(short *moveRow,short *moveCol)
// The move is represented by the row/col coordinates of any area cell
   {
      *moveRow=ref->Row();
      *moveCol=ref->Col();
   }

};

typedef Area* AreaPtr;


/*******************************************************************
/
/                     Class Player
/
/*******************************************************************/

class Player
// Player is the main structure holding data from initialization through moves
// Player also implements almost all the game logic, calling upon MyCell and Area
// classes for utility functions.
{
private:
   long   nRows;
   long   nCols;
   long   nColors;

// My cells are stored in an array myBoard[col*nRows + row], arranged
//       to have sequential memory access for all cells in a column 

   MyCell*   myBoard;
   Area*   areas;
   long   numAreas;
// The cell list is allocated as a scratch pad for collecting the cells

//      to be removed at each move.

   MyCellPtr*   cellList;
   long   numInList;
// Move Number only serves as a source of unique tags for each move

   long    moveNr;
// A color is designated, to govern cell selection

   MyCellColor designatedColor;
   
public:
   Player(long boardSizeRows,long boardSizeCols,long numColors,

         const CellColor board[],WindowPtr wdw) :
      nRows(boardSizeRows),
      nCols(boardSizeCols),
      nColors(numColors),
      myBoard(
         new MyCell[sizeof(MyCell)*boardSizeRows*boardSizeCols]),
      areas(new Area[sizeof(Area)*(boardSizeRows*boardSizeCols)]),
      numAreas(0),
      cellList(
         new MyCellPtr[sizeof(MyCellPtr)*
                     (1+boardSizeRows*boardSizeCols/nColors)]),
      numInList(0),
      moveNr(0),
      designatedColor(0)
   {   
      win=wdw;

      long windowWidth=win->portRect.right-win->portRect.left;
      long windowHeight=win->portRect.bottom-win->portRect.top;
      long squareWidth=windowWidth/nCols;
      long squareHeight=windowHeight/nRows;

      gCellSize=(squareWidth < squareHeight) ? 
                              squareWidth : squareHeight;
      if (gCellSize>kMaxCellSize)
         gCellSize=kMaxCellSize;
      else if (gCellSize<kMinCellSize)
         gCellSize=kMinCellSize;
         
      InitCells(board);
      ShowRange(0,nCols);
   }
   
   ~Player()
   {
      delete [] cellList;
      delete [] areas;
      delete [] myBoard;
   }
   
   void InitCells(const CellColor board[])

// Copies the CellColors of board[] to MyCells in myBoard[]

//   while rearranging the row/column sequence to be more convenient

   {
      const CellColor* B=board;
      long cellSize=gCellSize;
      long   bottomRow=cellSize*(nRows-1);
      Point   spot={0,0};
      // will display row 0 at the bottom
      // will display col 0 at left
      for (long col=0;col<nCols;col++)
      {
         spot.v=bottomRow;
         for (long row=0;row<nRows;row++)
         {
            const CellColor* B=&board[row*nCols + col];
            MyCell* C=&myBoard[col*nRows + row];
            C->Init(spot,*B,row,col,cellSize);
            spot.v    -=   cellSize;
         }
         spot.h   +=   cellSize;
      }
   }
   
   void UpdateEvent(EventRecord theEvent)

// Checks validity of the event, and shows the entire board.

// Relies on caller to call BeginUpdate(..) and EndUpdate(..).

   {
      if ((theEvent.what==updateEvt) && 
               (win==(WindowPtr)theEvent.message))
      {
         // Touch all cells to ensure they are drawn
         for (int i=0;i<nRows*nCols;i++)
            myBoard[i].Touch();

         // Draw the board

         ShowRange(0,nCols);
      }
   }
   
   void RemoveCells(long row,long col,long numToRemove)

// Shifts one column down; row 0 is at the bottom

   {
      MyCell* dest=myBoard+col*nRows+row;
      MyCell* src=dest+numToRemove;
      MyCell* end=myBoard+(col+1)*nRows;
      while (src<end)
         (dest++)->CopyColor(src++);
      
      while (dest<end)
         (dest++)->ClearColor();
   }
   
   void ShowRange(long firstCol,long numColsToShow)

// Shows all cells which have been touched

   {
      if (!SHOWCELLS)
         return;
      GrafPtr   savePort;
      GetPort (&savePort);
      
      SetPort(win);      
      
      MyCell* C=myBoard + firstCol*nRows;
      for (int i=0;i<numColsToShow*nRows;i++)
         (C++)->Show();
      
      SetPort (savePort);
    }
    
   Area* GetSmallestArea1(const MyCellColor avoidColor)

// Returns the smallest area, not of "avoidColor", nearest the top, and which has a 

// shadow. 

   {
      long smallestSize=nCols*nRows;
      Area* bestArea=0;
      long topRow=-1;
      for (int i=0;i<numAreas;i++)
      {
         Area* A=&areas[i];
         if    (    (A->Size() <= smallestSize)
            &&   (A->Color() != avoidColor)
            && (A->Cell()->Row() > topRow) 
            &&   (Shadow(A->Cell(),A->Color()))
            )
         {
            bestArea=A;
            smallestSize=A->Size();
            topRow=A->Cell()->Row();
         }
      }
      UnSeeAll();
      return bestArea;
   }
   
   bool Shadow(MyCell* C,const MyCellColor theColor) 

// Returns true if the area containing C is in the "shadow" of a cell of theColor,

// i.e. there is at least one cell of theColor above the area. 

   {
      if (C->IsSeen())
         return false;
      long row=C->Row();
      long col=C->Col();
      C->See();
      if (Shade(C+1,C-row+nRows,theColor))
         return true;
         
      if ((row>0) 
         && ((-1)[C].Color()==theColor) 
         && Shadow(C-1,theColor))
            return true; 
            
      if ((row<nRows-1) 
         && ((1)[C].Color()==theColor)
         && Shadow(C+1,theColor))
            return true; 
            
      if ((col>0) 
         && ((-nRows)[C].Color()==theColor)
         && Shadow(C-nRows,theColor))
            return true; 
            
      if ((col<nCols-1)
         && ((nRows)[C].Color()==theColor)
         && Shadow(C+nRows,theColor))
            return true; 
         
      return false;
   }
   
   bool Shade(MyCell* C,MyCell* end,const MyCellColor theColor)

// Checks the column of C and above.

// Returns true if it encounters a cell of theColor. 

   {
      while ((C<end) && (C->Color()!=0))
      {
         if ((C->Color()!=theColor))
            return true;
         C++;
      }
      return false;
   }
   
   void UnSeeAll()
// Clears all "seen" flags.
   {
      for (long i=0;i<nRows*nCols;i++)
         myBoard[i].UnSee();
   }
   

   Area* GetSmallestArea2(const MyCellColor chosenColor)

// Returns the smallest area of the chosen color.

   {

      long smallestSize=nCols*nRows;
      Area* bestArea=0;
      long bottomRow=nRows;
      for (int i=0;i<numAreas;i++)
      {
         Area* A=&areas[i];
         if   (    (A->Size() < smallestSize) 
            &&   (A->Color() == chosenColor)
            )
         {
            bestArea=A;
            smallestSize=A->Size();
         }
      }
      return bestArea;
   }
   
   long MeasureArea(MyCell* C,const MyCellColor theColor)

// All cells connected to C, and of the same color, are counted and tagged.

// Recursively collects all cells of one area and returns the size of the area.

   {   

      C->Tag(moveNr);   // uses the current move number as a unique tag

      long areaSize=1;
      
      long row=C->Row();
      long col=C->Col();
      
      if ((row>0) 
         && ((-1)[C].Color()==theColor) 
         && !(-1)[C].IsTagged(moveNr))
            areaSize+=MeasureArea(C-1,theColor);    
      
      if ((row<nRows-1) 
         && ((1)[C].Color()==theColor) 
         && !(1)[C].IsTagged(moveNr))
            areaSize+=MeasureArea(C+1,theColor);       
      
      if ((col>0) 
         && ((-nRows)[C].Color()==theColor) 
         && !(-nRows)[C].IsTagged(moveNr))
            areaSize+=MeasureArea(C-nRows,theColor);        
      
      if ((col<nCols-1) 
         && ((nRows)[C].Color()==theColor) 
         && !(nRows)[C].IsTagged(moveNr))
            areaSize+=MeasureArea(C+nRows,theColor);       
      
      return areaSize;
   }
      
   long CreateAreas()

// The board is scanned and all contiguous areas are identified.

   {
      long num=0;
      MyCell* C0=myBoard;
      for (long col=0;col<nCols;col++,C0+=nRows)
      {
         MyCell* C=C0;
         for (long row=0;row<nRows;row++,C++)
         {
            if (C->IsTagged(moveNr))
               continue;   
            
            if (C->IsBlank())   // reached top of active row
               break;
               
            long areaSize=MeasureArea(C,C->Color());
            if (areaSize >= 2)
               areas[num++].Init(C,areaSize);
         }

      }   

      return num;
   }
   
   long Play(CellColor board[],short *moveRow,short *moveCol)

// The main Play() function, called once per move.

// Plays one move and returns the number of cells removed.

   {   
      moveNr++;
      
// Identify all areas.
      numAreas=CreateAreas();
      
      if (numAreas==0) // game over !
         return 0;

// Ensure we have a target color.

choose_a_color:      
      if (designatedColor==0)
         designatedColor=ChooseColor();
      
// First choice: remove a small area of another color.
        Area* area=GetSmallestArea1(designatedColor);
                              //minimum area of unreserved color
      if (0==area)
      {
// Second choice: remove smallest area of the chosen color.
         area=GetSmallestArea2(designatedColor);
                           //minimum area of reserved color
         if (0==area)
         {
// Third choice: find a new color.
            designatedColor=0;
            goto choose_a_color;
         }
      }
      
// .. and do the removal.
      long numCellsRemoved=Execute(area,board,moveRow,moveCol);
      
      return numCellsRemoved;
   }
   
   const MyCellColor ChooseColor()

// Chooses a color which we hope can be the color of a large area.

// The heuristic is to first remove all areas of other colors which are already more 
// coherent. This should then allow the smaller areas and single cells of the chosen 
// color to coalesce and form a larger single area.

   {
      long score[kMaxNumColors];
      for (int i=1;i<=nColors;i++)
         score[i]=0;
      for (int i=0;i<numAreas;i++)
      {
         long color=areas[i].Color();
         long size=areas[i].Size();
         score[color]+=size*size;
      }
      
      long lowestScore=nRows*nRows*nCols*nCols;
      MyCellColor chosenColor=0;
      for (int i=1;i<=nColors;i++)
      {
          if ((score[i] > 0) && (score[i] < lowestScore))
         {
            lowestScore=score[i];
            chosenColor=i;
         }
      }
      
      return chosenColor;
   }
   
   long Execute(Area* area,CellColor board[],
                     short *moveRow,short *moveCol)
// Removes the selected area and returns its size.
   {
      area->GetMove(moveRow,moveCol);
      numInList=0;
      MyCellColor theColor=area->Color();
      
// Collect all cells of the area into a single list
      MakeList(area->Cell(),theColor);
      
      assert(numInList==area->Size());
      
// Sort the list, so that whole clumns can be removed if possible
      qsort(cellList,numInList,sizeof(MyCellPtr),CompCells);
      
// cells in list are sorted by col,row
// we'll remove cells by col, row, num rows in col
      long minCol=nCols;
      long maxCol=-1;
      for (int i=0;i<numInList;i++)
      {
         MyCell* C=cellList[i];
         long row=C->Row();
         long col=C->Col();
         long n=1;
         // count number of contiguous cells in column for removal
         for (int k=i+1;k<numInList;k++,n++)
         {
            long nextRow=row-1;
            if ((cellList[k]->Col() != col) || 
                        (cellList[k]->Row() != nextRow))
               break;
            
            i++;
            row=nextRow;
         }
         assert(row>=0);
         assert(row+n<=nRows);
         assert(col>=0);
         assert(col<nCols);
         RemoveCells(row,col,n);

// Remember column range
         if (maxCol < col) maxCol=col;
         if (minCol > col) minCol=col;
      }
      
      assert(maxCol<nCols);
      assert(minCol>=0);

// If any empty cols result, move cols towards center, extend range
//      .. from the right

      for (long col=maxCol;(col>=(nCols-nCols/2)) && 
                        (col>=minCol);col—)
      {
         if (IsEmptyColumn(col))
         {
            ShiftLeft(col);
            maxCol=nCols-1;
         }
      }
//      .. and from the left
      for (long col=minCol;(col<=nCols/2) && (col<=maxCol);col++)
      {
         if (IsEmptyColumn(col))
         {
            ShiftRight(col);
            minCol=0;
         }
      }

// Display all touched cells in range
      ShowRange(minCol,maxCol-minCol+1);

// Let the caller know what happened: update his board[]
      CopyBackBoard(board,minCol,maxCol-minCol+1);

//    .. and return the number of cells removed.

      return numInList;
   }
   
   void CopyBackBoard(CellColor board[],long firstCol,long numColsToShow)

// Copies the cell colors of myBoard[] to the callers board[]

// Note the different array indexing.

   {
      MyCell* C=&myBoard[firstCol*nRows];
      for (long col=firstCol;col<firstCol+numColsToShow;col++)
      {
         for (long row=0;row<nRows;row++,C++)
         {
            CellColor* B=&board[row*nCols + col];
            C->CopyBack(B);
         }
      }
   }
   
   bool IsEmptyColumn(long col)
// Returns true if the first cell in a column is blank (white)
   {
      return (myBoard[col*nRows].IsBlank());
   }
   
   void ShiftRight(long destCol)
// Shifts all columns left of destCol to the right by one position
   {
      long minCol=0;
      for (;minCol<destCol;minCol++)
         if (!IsEmptyColumn(minCol))
            break;
      for (long srcCol=destCol-1;srcCol>=minCol;srcCol—,destCol—)
      {
         CopyColumn(destCol,srcCol);
      }
      ClearColumn(minCol);
   }
   
   void ShiftLeft(long destCol)
// Shifts all columns right of destCol to the left by one position
   {
      long maxCol=nCols-1;
      for (;maxCol>destCol;maxCol—)
         if (!IsEmptyColumn(maxCol))
            break;
      for (long srcCol=destCol+1;srcCol<=maxCol;srcCol++,destCol++)
      {
         CopyColumn(destCol,srcCol);
      }
      ClearColumn(maxCol);
   }
   
   void CopyColumn(long destCol,long srcCol)
// Copies one column from bottom row up, stopping when both are blank 
   {
      MyCell* dest=&myBoard[destCol*nRows];
      MyCell* src=&myBoard[srcCol*nRows];
      for (long row=0;row<nRows;row++)
      {
         if ((dest[row].IsBlank()) && (src[row].IsBlank()))
            break;
         dest[row].CopyColor(src+row);
      }
   }
   
   void ClearColumn(long col)
// Clears a column from bottom row up, stopping at first blank row
   {
      MyCell* dest=&myBoard[col*nRows];
      MyCell* end=dest+nRows;
      while (dest<end)
      {
         if (dest->IsBlank())
            break;
         (dest++)->ClearColor();
      }
   }
   
   void MakeList(MyCell* C,const MyCellColor theColor)
// Scans an area recursively, and puts a reference to each cell into cellList.
   {
      C->Tag(0);
      cellList[numInList++]=C;
      
      long row=C->Row();
      long col=C->Col();
      if ((row>0) 
         && ((-1)[C].Color()==theColor) 
         && !(-1)[C].IsTagged(0))
            MakeList(C-1,theColor); 
            
      if ((row<nRows-1) 
         && ((1)[C].Color()==theColor) 
         && !(1)[C].IsTagged(0))
            MakeList(C+1,theColor);
             
      if ((col>0) 
         && ((-nRows)[C].Color()==theColor) 
         && !(-nRows)[C].IsTagged(0))
            MakeList(C-nRows,theColor);
             
      if ((col<nCols-1) 
         && ((nRows)[C].Color()==theColor) 
         && !(nRows)[C].IsTagged(0))
            MakeList(C+nRows,theColor); 
   }
};

static Player*    P=0;

/*******************************************************************
/
/                  External Functions
/
/*******************************************************************/

void InitDownNOut(
 short boardSizeRows, /* number of rows in the game */
 short boardSizeCols, /* number of columns in the game */
 short numColors,   /* number of colors in the game */
 const CellColor board[],
  /* board[row*boardSizeCols + col] is color of cell at [row][col] */
 WindowPtr gameWindow
  /* window where results of your moves should be displayed */
)
{
   if ((boardSizeRows>0) 
      && (boardSizeCols>0) 
      && (numColors>=1)
      && (numColors+2<=kMaxNumColors) )
   P=new Player(boardSizeRows,boardSizeCols,numColors,board,gameWindow);
}

void HandleUpdateEvent(EventRecord theEvent)
{
   if (P) P->UpdateEvent(theEvent);
}

Boolean /* able to play */ PlayOneDownNOutMove(
   long score,         /* points earned prior to this move */
   CellColor board[],   /* board[row*boardSizeCols + col] is color of cell at [row][col] */
   short *moveRow,      /* return row of your next move */
   short *moveCol,      /* return col of your next move */
   long *numberOfCellsRemoved   /* self explanatory */
)
{
#pragma unused(score)
   if (P)
   {
      long numCellsRemoved=
         P->Play(board,moveRow,moveCol);
      
      if (numCellsRemoved>0)
      {
         *numberOfCellsRemoved=numCellsRemoved;
         return true;
      }
   }
   *numberOfCellsRemoved=0;
   return false;
}

void TermDownNOut(void) 
{
   delete P; 
// Deletes the only visible variable which in turn destroys its allocated data members.
   P=0;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

NetShade 8.3 - Browse privately using an...
NetShade is an anonymous proxy and VPN app+service for Mac. Unblock your Internet through NetShade's high-speed proxy and VPN servers spanning 17 countries. NetShade masks your IP address as you... Read more
Adobe Animate CC 2020 20.0.1 - Animation...
Animate CC 2020 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2020 (was Flash CC) lets you... Read more
Adobe Acrobat DC 19.021.20058 - Powerful...
Acrobat DC is available only as a part of Adobe Creative Cloud, and can only be installed and/or updated through Adobe's Creative Cloud app. Adobe Acrobat DC with Adobe Document Cloud services is... Read more
Adobe Acrobat Reader 19.021.20058 - View...
Adobe Acrobat Reader allows users to view PDF documents. You may not know what a PDF file is, but you've probably come across one at some point. PDF files are used by companies and even the IRS to... Read more
Adobe Flash Player 32.0.0.303 - Plug-in...
Adobe Flash Player is a cross-platform, browser-based application runtime that provides uncompromised viewing of expressive applications, content, and videos across browsers and operating systems.... Read more
Adobe InDesign CC 2019 15.0.1 - Professi...
InDesign CC 2019 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign CC 2019 is part of Creative Cloud.... Read more
Adobe Lightroom Classic 9.1 - Import, de...
You can download Lightroom for Mac as a part of Creative Cloud for only $9.99/month with Photoshop, included as part of the photography package. The latest version of Lightroom gives you all of the... Read more
Shredo 1.2.7 - $6.99
Shredo is a beautiful, functional file-shredding and privacy scan utility. It permanently shreds files, folders, and external volumes' contents to keep information secure and impossible for anyone to... Read more
Visual Studio Code 1.41.0 - Cross-platfo...
Visual Studio Code provides developers with a new choice of developer tool that combines the simplicity and streamlined experience of a code editor with the best of what developers need for their... Read more
calibre 4.6.0 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more

Latest Forum Discussions

See All

King's Throne, the hugely ambitious...
King's Throne: Game of Lust is a deeply immersive medieval-set idle RPG which sees you playing as an ambitious prince, and sole heir to your father's kingdom. On a seemingly ordinary night whilst wandering the king's castle, you make the shocking... | Read more »
Abyssrium Pole is an upcoming aquarium b...
FleroGames' upcoming Abyssrium Pole has recently hit one million pre-registers, which is very impressive, particularly for a fairly casual looking game. Those who have pre-registered will receive 1000 Pearl when the game launches on 8th January... | Read more »
Two Spies is pretty fun, but it's h...
Two Spies just dropped on the App Store this week, and it looks pretty neat. The game has two players capturing various cities across Europe, with the goal of eventually spotting and striking the other spy down. It may be simple-looking, but after... | Read more »
Two Spies is a turn-based game for iOS t...
There aren't too many games that feature pass and play multiplayer and there are even less where you can only play against people you know, even when playing online. But Two Spies does both of those things and you can get it for iOS right now. [... | Read more »
Solve your way through new low-poly puzz...
The best escape-the-room games don’t just test your creative problem-solving skills – they look great, too. Released in October this year by Antler (the developer of the succesful VR puzzle SVRVIVE: The Deus Helix), Krystopia offers everything you... | Read more »
Get ready for an epic adventure with Pea...
Following a hugely successful pre-registration campaign, Pearl Abyss' much-hyped MMORPG, Black Desert Mobile, has finally arrived for iOS and Android. With some of the most impressive visuals on mobile, a vast open world to explore, an in-depth... | Read more »
Elder Scrolls: Blades has ditched chest...
Elder Scrolls: Blades started out as one of the most hyped mobile games of 2019, boasting some impressive visuals and no shortage of promise. Our hopes were somewhat dashed when it eventually launched and we all became privy to its mishandled... | Read more »
Hands-On with the Pocket City December U...
At the end of last month, Codebrew Games announced an update coming to their popular city-builder, Pocket City some time this month. In this update is the promise of expanding your city out into other regions, enacting policies, and more. The full... | Read more »
Black Desert Mobile is available for pre...
Pearl Abyss' stunning open-world MMORPG, Black Desert Mobile, is set to launch for iOS and Android on December 11th at 12 AM PST (8 AM UTC). However, those looking to get in early and test out the in-depth character customisation will be able to... | Read more »
Extraordinary Ones, NetEase's innov...
NetEase's inventive 5v5 anime MOBA, Extraordinary Ones, has now opened for pre-registration ahead of its global launch in early 2020. The game seems to have received a fairly warm reception from fans after its soft-launch earlier in the year,... | Read more »

Price Scanner via MacPrices.net

Apple Watch Series 3 models on sale at Amazon...
Amazon has Apple Watch Series 3 GPS models on sale for $20 off MSRP, starting at only $179. Their prices are the lowest available for these models from any Apple reseller. Choose Amazon as the seller... Read more
Sunday AirPods Sale: Amazon drops prices to a...
Amazon has new 2019 Apple AirPods on sale today ranging up to $30 off MSRP, starting at $139. Shipping is free: – AirPods Pro: $249 $0 off MSRP – AirPods with Wireless Charging Case: $168.95 $30 off... Read more
Holiday 2019 sale: 11″ iPad Pros for up to $2...
Amazon has new Apple 11″ iPad Pros in stock today and on sale for up to $200 off Apple’s MSRP as part of their Holiday 2019 sale. These are the same iPad Pros sold by Apple in its retail and online... Read more
B&H has 12.9″ WiFi iPad Pros on sale for...
B&H Photo has new 12.9″ WiFi iPad Pros on sale for up to $150 off Apple’s MSRP as part of their Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 12.9″ 64GB WiFi iPad... Read more
Find the best Holiday 2019 prices on Apple’s...
Our Apple award-winning price trackers are the best place to look for the best deals and lowest prices on Apple gear this 2019 Holiday shopping season. Scan our price trackers for the latest... Read more
13″ 2.4GHz/256GB Silver MacBook Pro on sale f...
Amazon has the Silver 13″ 2.4GHz/256GB 4-Core Touch Bar MacBook Pro on sale for $1499.99 shipped. Their price is $300 off Apple’s MSRP, and it’s the lowest price currently available for a 13″ 2.4GHz... Read more
Sams Club one day sales event December 14th:...
Through midnight Saturday night (December 14th), Sams Club online has several Apple Watch Series 5 models on sale for $40 off MSRP as part of their One Day sales event. Choose free shipping or free... Read more
Total Wireless offers iPhone 6S models for as...
Total Wireless has Apple 32GB iPhone 6S models available starting at $99: – 32GB iPhone 6S: $99.99 – 32GB iPhone 6S Plus: $149.99 A no-contract Total Wireless prepaid plan is required with your... Read more
Get a 4 or 6-core Mac Mini for up to $170 off...
B&H Photo has 4-Core and 6-Core Mac minis on sale for up to $170 off Apple’s standard MSRP as part of their Holiday 2019 sale. Overnight shipping is free to many US addresses: – 3.6GHz Quad-Core... Read more
Amazon restocks base 13″ 1.4GHz MacBook Pro f...
Amazon has restocked the base 13″ 1.4GHz/128GB Space Gray MacBook Pro for $1099.99 shipped. Their price is $200 off Apple’s MSRP, and it’s the cheapest price available for a new MacBook Pro. Amazon... Read more

Jobs Board

*Apple* Mobility Sales Professional - Best B...
**750138BR** **Job Title:** Apple Mobility Sales Professional **Job Category:** Store Associates **Store NUmber or Department:** 000471-Mt Vernon-Store **Job Read more
*Apple* Engineering Specialist (ITC ) - Gene...
…Suitability clearance, per contract requirements. Currently, we are seeking an Apple Engineering Specialist in Washington, DC The responsibilities for candidates in Read more
Senior *Apple* Endpoint Engineer - Leidos (...
…Medicaid Service (CMS) End User environment. Perform specific duties as an Apple Endpoint Engineer in support of the infrastructure operations, hardware, software Read more
Perioperative - RN - ( *Apple* Hill Surgical...
Perioperative - RN - ( Apple Hill Surgical Center) Tracking Code 59281 Job Description Monday - Friday - Part Time - Days Possible Saturdays General Summary: Under Read more
Lead DevOps Engineer - *Apple* - Theorem, L...
Job Summary Apple is looking for a seasoned Lead DevOps Engineer that can lead multiple projects and teams while delivering high quality and performant solutions in Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.