TweetFollow Us on Twitter

Jan 98 Challenge

Volume Number: 14 (1998)
Issue Number: 1
Column Tag: Programmer's Challenge

Jan 98 - Programmer's Challenge

by Bob Boonstra, Westford, MA

Cell Selection

One year ago, the Macintosh world was full of rumors about the prospect of Apple acquiring the Be Operating System. MacTech bundled the DR8 BeOS CD-ROM with the magazine. The Challenge column invited readers to try the BeOS on their Macs and enter the first BeOS Challenge. Then, before the BeOS issue had even arrived, Apple announced its intention to buy NeXT, and the journey to Rhapsody began.

Even though BeOS has faded from the headlines, it runs better on your Mac than it ever did. In fact, Preview Release 2 is scheduled to arrive in the immediate future. My personal interest in BeOS has been reinvigorated by a recent bargain that was too good to pass up - a dual 200MHz 604e MaxPOWR 400 processor upgrade. While it is possible for developers to take advantage of multiple processors under MacOS, using a special nonsymmetric interface developed in conjunction with DayStar, multiprocessing MacOS applications are the exception rather than the rule. Not so, of course, with BeOS, where symmetric multiprocessing is an intrinsic part of the operating system.

In honor of the one-year anniversary of the MacTech BeOS issue, and in celebration of my new 2x200 MHz toy, the Challenge this month is going to encourage the use of multiple processors. You will be able to use either BeOS or MacOS. If you choose to use MacOS and wish to take advantage of the second processor on my test system, you should use the SDK found at: ftp://dev.apple.com/devworld/Development_Kits/Multiprocssing_SDK.sit.hqx.

The problem this month, suggested by Jon "h++" Wätte, is to implement a CellSelection class. CellSelection implements a two-dimensional set of cells, each of which can be "on" or "off", along with a collection of methods to manipulate cell states.

The prototype for the code you should write is:

#if __dest_os == __be_os
#include <SupportDefs.h>
#else
typedef long int32;
typedef unsigned long uint32;
#endif

struct Area {
  int32    left,top,right,bottom;
    /* Area coordinates are inclusive. {2,2,3,4} includes 6 cells. */
    /* Any area with left>right or top>bottom is empty. */
};

class CellSelection {
  private:
    /* add your methods and instance variables here */
  public:
    CellSelection(void);
      /* create an empty selection */
    ~CellSelection(void);
      /* free any allocated memory */
    bool Clear(); 
      /* make the selection empty */
    bool Add(Area area);
      /* add the area of cells to this selection */
    bool Remove(Area area); 
      /* remove the area of cells from this selection */
    bool Invert(Area area); 
      /* remove cells in the area that are also in this selection
        and add the area cells that are not in this selection */
    bool Add(const CellSelection & otherSelection); 
      /* add the otherSelection to this selection */
    bool Remove(const CellSelection & otherSelection); 
      /* remove the otherSelection from this selection */
    bool Invert(const CellSelection & otherSelection); 
      /* remove cells in the otherSelection that are also in this selection
        and add the otherSelection cells that are not in this selection */
    bool AllSelected(Area area);
      /* return TRUE if all cells in the area are selected */
    uint32 CountSelected(Area area); 
      /* count cells that are "on" */
    bool EqualSelected(const CellSelection & otherSelection); 
      /* return TRUE if otherSelection equals this selection */
};

The destructor should free any memory allocated by the constructor or by any of the methods of CellSelection. The Add method should turn on any cells in the area or otherSelection; similarly the Remove method should turn off the specified cells. Invert is an exclusive-or operator that turns off cells that are on and turns on cells that are off, provided the cell is in the specified area or otherSelection. The Clear method resets the selection to its original empty state. All of these methods return TRUE if they succeed or FALSE if they run out of memory. The AllSelected method determines whether all of the cells in the specified area are on, while the CountSelected method counts the number of cells in the specified area that are on. Finally, the EqualSelected method determines whether the selected cells in this CellSelection are the same as the selected cells in the otherSelection.

The test code will require you to create a modest number of CellSelection instances (perhaps 10 to 50) and manipulate them with a larger number of Add/Remove/Invert operations, interspersed with a modest number of AllSelected/CountSelected/EqualSelected tests.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions must be coded in C++, written for either the Macintosh operating system or the Be operating system. You can use all of the available memory in my 96MB 8500, but your code must fail gracefully if it runs out of memory. Your solution should include a complete CodeWarrior project file and test driver, compressed into a .sit or .cpt archive (for MacOS) or into a .zip, .gz archive (for BeOS). I'll evaluate your solution using the target operating system you designate, and the fastest correct solution will be the winner. Memory-inefficient solutions that fail to handle large problems will be considered less correct than memory-efficient solutions.

Three Months Ago Winner

Congratulations to Randy Boring for submitting the winning entry to the Who Owns the Zebra Challenge. Recall that this Challenge required you to parse a set of inputs representing clues like "The American lives in the house with the red door" and "The person who drinks orange juice owns the dog" and solve a problem like "Who owns the zebra?" Randy's solution was faster than the second place solution in three of four test cases, and some 25% faster in the largest test case.

Randy's solution maintains a mask matrix, gLocations[], to indicate which locations are still possible for a (solution row, location) combination. He also maintains a value matrix gValue[] to indicate which location assignments remain possible for a given (variable, value) pair. Clues that constrain location assignments manipulate these data structures directly, while clues that relate (variable, value) pairs propagate the location constraints of each pair to the other pair in the routine ApplySAME_ROW. Constraint propagation is done in the ApplyXXX routines, which should be examined to understand how this solution works. If a solution is not evident when all of the clues have been applied, the ThinkRealHard routine hypothesizes a new constraint and propagates this artificial clue, terminating when a solution is reached or when it runs out of constraint hypotheses.

I would be remiss if I did not mention the Java solution submitted by David Whitney, in a self-professed "blatant violation" of the rules. Although his solution suffered in execution time, I found it interesting. Perhaps it is time for a Java Challenge... Any ideas?

The table below lists the execution times, code size, data size, and programming language for each entry. Execution time is listed in milliseconds for each of four problem dimension values tested: 3, 5, 15, and 31. Solutions which did not solve a test case in a reasonable amount of time (several minutes) are listed with an asterisk and did not win any Challenge points. The number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges to date prior to this one.

Name                 Total   Time   Time      Time   Time    Code   Data  Lang.
                     Time 3    5     15        31      
Randy Boring (41)     728.6   0.3    0.6      31.3   696.4   8400  22530    C  
Ernst Muter (300)     972.8   1.5    2.2      29.7   939.4   6420    128   C++  
David Whitney      477247.0 134.0  410.0  476703.0      *   45010      0  Java!  
Willeke Rieken (10)      *    0.4    1.6        *       *    6920    548   C++  
Ken Slezak (20)          *    0.4     *         *       *    6340    232    C  

Top 20 Contestants

Here are the Top Contestants for the Programmer's Challenge. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank  Name                Points  Rank  Name                Points
  1.  Munter, Ernst         210    11.  Day, Mark              20
  2.  Boring, Randy          61    12.  Higgins, Charles       20
  3.  Cooper, Greg           61    13.  Larsson, Gustav        20
  4.  Lewis, Peter           57    14.  Lengyel, Eric          20
  5.  Nicolle, Ludovic       48    15.  Studer, Thomas         20
  6.  Murphy, ACC            34    16.  Saxton, Tom            17
  7.  Gregg, Xan             33    17.  Gundrum, Eric          15
  8.  Mallett, Jeff          30    18.  Hart, Alan             14
  9.  Antoniewicz, Andy      24    19.  O'Connor, Turlough     14
 10.  Picao, Miguel Cruz     21    20.  Karsh, Bill            12

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 Randy's winning solution:

Zebra.c
© 1997, Randy Boring

#include "Zebra.h"

#include <string.h>
#include <stdio.h>
#include <stdlib.h> // for malloc and free

typedef enum {
 kClueNextTo,
 kClueImmedRightOf,
 kClueImmedLeftOf,
 kClueSameRowAs,
 kClueLocatedAt
 } ZClueType;

typedef enum {
 kContradiction = -1,
 kSolved = 0,
 kUnsolved = 1
 } ZSolutionState;

// global string constants
// relations
static const CStr255 gsrISA = "ISA"; // variable membership
static const CStr255 gsrIS_LOCATED = "IS_LOCATED"; // absolute position
// relative position relations
static const CStr255 gsrNEXT_TO = "NEXT_TO";
static const CStr255 gsrIMMED_RIGHT_OF = "IMMED_RIGHT_OF";
static const CStr255 gsrIMMED_LEFT_OF = "IMMED_LEFT_OF";
// absolute position values
static const CStr255 gsvIN_MIDDLE = "IN_MIDDLE";
static const CStr255 gsvAT_RIGHT = "AT_RIGHT";
static const CStr255 gsvAT_LEFT = "AT_LEFT";
// parts of the Question
static const CStr255 gsqSOLVE = "SOLVE";
static const CStr255 gsqANSWER = "ANSWER";
static const long kMaxValues = 964;
static const long kMaxVariables = 31;

// bit array of possible locations
// has just a single bit set when location is known
typedef unsigned long ZLocation;

static const ZLocation kLeftBit = 0x80000000;
static ZLocation gMask;

typedef struct value {
 long   loc;        // index of possible locations for this value
 struct value *next;  // next ZValue of this ZType
 void   *type;  // points to the variable (ZType) that we are a possible value of
 char   *name;  // name given for this ZValue
 } ZValueRec, *ZValue;

// a ZType is the definition of a variable, including its name and possible values
typedef struct type {
 ZValue   values;      // list of possible values for this variable
 struct type  *next;    // next variable of this problem
 char   *name;        // name given for this variable
 long   order;        // print order of this variable in solution
 } ZTypeRec, *ZType;

// a ZClue is a Fact that must be used to solve the puzzle
typedef struct clue {
 struct clue  *next;   // next clue in list
 ZClueType  type;    // which kind of clue
 ZValue   firstValue;  // first variable of this clue
 ZValue   secondValue; // second variable of this clue
 } ZClueRec, *ZClue;

typedef struct q {
 ZClue  head; // front of line where things are taken off
 ZClue  tail; // back of line where things are added
 } ZQRec, *ZQ;

static unsigned long gDim;
static unsigned long gNumClues;
static unsigned long gkBlockSize;
static unsigned long gkBlockSizeInLongs;
static ZQRec gQRecUnsatisfied;
static ZQRec gQRecSatisfied;
static ZQ gQUn = &gQRecUnsatisfied;
static ZQ gQSat = &gQRecSatisfied;
static ZTypeRec gVars[kMaxVariables];  // 32 (31 is max)
static ZValueRec gValues[kMaxValues];  // (964) 31 X 31 (961) is max
static ZLocation gLocations[kMaxValues];// (964) 31 X 31 (961) is max
static ZLocation *gL = gLocations;


#define FirstVar()      (&(gVars[0]))
#define FirstValueOf(var)  ((var)->values)
#define NameOf(x)      ((x)->name)
#define SetNameOf(x, s)   ((x)->name = (s))
#define NextOf(x)      ((x)->next)
#define SetNextOf(x, y)   ((x)->next = (y))
#define LocationOf(v)    (gL[(v)->loc])
#define SetLocationOf(v, L) (gL[(v)->loc] = (L))
#define TypeOf(c)      ((c)->type)
#define SetTypeOf(c, t)   ((c)->type = (t))
#define PrintOrderOf(var)  ((var)->order)
#define SetPrintOrder(var,n) ((var)->order = (n))
#define FirstValOf(c)    ((c)->firstValue)
#define SetFirstValOf(c, v) ((c)->firstValue = (v))
#define SecondValOf(c)    ((c)->secondValue)
#define SetSecondValOf(c, v) ((c)->secondValue = (v))



InitQ
// Initialize queue q
static void
InitQ(ZQ q)
{
 q->head = nil;
 q->tail = nil;
}


#define QNotEmpty(q) ((q)->head != nil)
#define QIsEmpty(q) ((q)->head == nil)

// Add c to end of queue q
static void
EnQ(ZQ q, ZClue c)
{
 if (q->head == nil)
  q->head = c;
 else
  SetNextOf(q->tail, c);
 q->tail = c;
 SetNextOf(c, nil);
}

// Remove the clue at the front of queue q and Return it
static ZClue
DeQ(ZQ q)
{
 ZClue c = q->head;
 q->head = NextOf(c);
 SetNextOf(c, nil);
 if (q->head == nil)
  q->tail = nil;
 return c;
}

// Add the elements of the first queue to the end of the
// second queue (removing them from the first one)
static void
MergeQ(ZQ from, ZQ to)
{
 while (QNotEmpty(from))
  EnQ(to, DeQ(from));
}

static void
MoveQ(ZQ from, ZQ to)
{
 to->head = from->head;
 to->tail = from->tail;
}

static void
MakeMask(long dim)
{
 ZLocation currBit = kLeftBit;
 gMask = 0;
 while (dim--)
  {
  gMask = gMask | currBit;
  currBit >>= 1;
  }
}

AddLocations
// Make the variable field for the problem
// dim rows, each with dim types
static void
AddLocations(long dim)
{
 long vari, vali = 0, loci = 0;
 for (vari = 0; vari < dim; vari++)
  {
  long addValuesStop = vali + dim;
  gVars[vari].values = &(gValues[vali]);
  gVars[vari].next = &(gVars[vari + 1]);
  gVars[vari].name = nil;
  do {
   gL[loci] = gMask;
   gValues[vali].loc = loci++;
   gValues[vali].next = &(gValues[vali + 1]);
   gValues[vali].type = &(gVars[vari]);
   gValues[vali].name = nil;
   vali++;
   } while (vali < addValuesStop);
  gValues[vali - 1].next = nil;  // terminate the list
  }
 gVars[vari - 1].next = nil;  // terminate the list
}

InitStructure
static void
InitStructure(long numClues, long problemDimension)
{
 gkBlockSizeInLongs = problemDimension * problemDimension;
 gDim = problemDimension;
 gNumClues = numClues;
 gkBlockSize = gkBlockSizeInLongs * sizeof(ZLocation);
 MakeMask(problemDimension);
 AddLocations(gDim);
 InitQ(gQUn);
 InitQ(gQSat);
}

static void
ReleaseMemory(void)
{
 while (QNotEmpty(gQUn))
  free(DeQ(gQUn));
 while (QNotEmpty(gQSat))
  free(DeQ(gQSat));
}

static void
CopyLocations(ZLocation *from, ZLocation *to)
{
 BlockMoveData((Ptr) from, (Ptr) to, gkBlockSize);
}

// Starting at a word beginning, search for its end.
// Null-terminate the word, null-out any extra space, and
// return the location of the next word.
static char *
MakeWordBreak(char *w)
{
 while (*w != ' ' && *w)
  w++;
 while (*w == ' ')
  *w++ = 0;
 return w;
}

static ZType
FindOrCreateType(char *aVariable)
{
 ZType t = FirstVar();
 while (t != nil && NameOf(t) != nil 
   && (0 != strcmp(NameOf(t), aVariable)))
  t = NextOf(t);
 if (t != nil)
  SetNameOf(t, aVariable);
 return t;
}

static void
AddPossibleValue(ZType var, char *aValue)
{
 ZValue v = FirstValueOf(var);
 while (v != nil && NameOf(v) != nil
   && (0 != strcmp(NameOf(v), aValue)))
  v = NextOf(v);
 if (v != nil)
  SetNameOf(v, aValue);
 else
  DebugStr("\pv is nil!");
}

static ZLocation
FindLocation(char *aLocation)
{
 ZLocation loc = 0;
 if (strcmp(aLocation, gsvAT_LEFT) == 0)
  loc = kLeftBit;
 else if (strcmp(aLocation, gsvAT_RIGHT) == 0)
  loc = kLeftBit >> (gDim - 1);
 else if (strcmp(aLocation, gsvIN_MIDDLE) == 0)
  loc = kLeftBit >> (gDim >> 1);
 else
  DebugStr("\p Not a valid location!");
 return loc;
}

static ZType
FindTypeNamed(char *aVariable)
{
 ZType t = FirstVar();
 while (t != nil && (0 != strcmp(NameOf(t), aVariable)))
  t = NextOf(t);
 return t;
}

static ZType
FindTypeOrdered(long n)
{
 ZType t = FirstVar();
 while (t != nil && PrintOrderOf(t) != n)
  t = NextOf(t);
 return t;
}

FindValueNamed
// Return the ZValue that is named aValue
static ZValue
FindValueNamed(char *aValue)
{
 ZType var;
 ZValue v = nil;
 for (var = FirstVar(); var != nil; var = NextOf(var))
  {
  v = FirstValueOf(var);
  while (v != nil && (0 != strcmp(NameOf(v), aValue)))
   v = NextOf(v);
  if (v != nil)
   return v;
  }
 return v;
}

IsSolvedLoc
// Returns true if the location, n, is 'solved', that is,
// if it has exactly one bit set.
static ZSolutionState
IsSolvedLoc(ZLocation n)
{
 // no set bits found yet
 ZLocation currBit = kLeftBit;
 long i = gDim;
 if (0 == n)
  {
//  DebugStr("\p Oversolved bit!");
  return kContradiction;
  }
 while (i--)
  {
  if (currBit & n)
   break;
  currBit >>= 1;
  }
 currBit >>= 1;
 // one set bit found
 while (i--)
  {
  if (currBit & n)
   return kUnsolved;    // two set bits found!
  currBit >>= 1;
  }
 return kSolved;    // exactly one set bit was found
}

FindValueWithUnsolvedLocation
// Return the first ZValue that is has an unsolved location
// That is, the location is not just a single bit.
static ZValue
FindValueWithUnsolvedLocation(void)
{
 ZType var;
 ZValue v = nil;
 for (var = FirstVar(); var != nil; var = NextOf(var))
  {
  v = FirstValueOf(var);
  while (v != nil && (kSolved == IsSolvedLoc(LocationOf(v))))
   v = NextOf(v);
  if (v != nil)
   return v;
  }
 return v;
}

// NOTE: watch out for the typecast in here
static void
AddFactLocationAbsolute(ZLocation loc, ZValue val)
{
 ZClue c = malloc(sizeof(ZClueRec));
 SetTypeOf(c, kClueLocatedAt);
 SetFirstValOf(c, val);
 SetSecondValOf(c, (ZValue) loc); // overload!
 EnQ(gQUn, c);
}

static void
AddFactLocationRelativeNextTo(ZValue aVal, ZValue bVal)
{
 ZClue c = malloc(sizeof(ZClueRec));
 SetTypeOf(c, kClueNextTo);
 SetFirstValOf(c, aVal);
 SetSecondValOf(c, bVal);
 EnQ(gQUn, c);
}

static void
AddFactLocationRelativeOnRight(ZValue aVal, ZValue bVal)
{
 ZClue c = malloc(sizeof(ZClueRec));
 SetTypeOf(c, kClueImmedRightOf);
 SetFirstValOf(c, aVal);
 SetSecondValOf(c, bVal);
 EnQ(gQUn, c);
}

static void
AddFactLocationRelativeOnLeft(ZValue aVal, ZValue bVal)
{
 ZClue c = malloc(sizeof(ZClueRec));
 SetTypeOf(c, kClueImmedLeftOf);
 SetFirstValOf(c, aVal);
 SetSecondValOf(c, bVal);
 EnQ(gQUn, c);
}

static void
AddFactSameRow(ZValue aVal, ZValue bVal)
{
 ZClue c = malloc(sizeof(ZClueRec));
 SetTypeOf(c, kClueSameRowAs);
 SetFirstValOf(c, aVal);
 SetSecondValOf(c, bVal);
 EnQ(gQUn, c);
}

static void
AddFactImportantValue(ZValue val)
{
#pragma unused (val)
}

static void
AddFactImportantType(ZType type)
{
#pragma unused (type)
}

ProcessISA
// Associates aValue with aVariable, so that we know that
// aValue is a possible value for the ZType aVariable.
// The ZType aVariable is created if it doesn't already exist.
static void
ProcessISA(char *aValue, char *aVariable)
{
 ZType v;
 v = FindOrCreateType(aVariable);
 AddPossibleValue(v, aValue);
}

ProcessIS_LOCATED
// Associates aValue with aLocation, so that we know that
// aValue is at the location aLocation.
static void
ProcessIS_LOCATED(char *aValue, char *aLocation)
{
 ZLocation loc;
 ZValue val;
 
 loc = FindLocation(aLocation);
 val = FindValueNamed(aValue);
 AddFactLocationAbsolute(loc, val);
}

ProcessNEXT_TO
// Associates aValue with bValue, so that we know that aValue is located next to 
// bValue. (This also implies that bValue is next to aValue)
static void
ProcessNEXT_TO(char *aValue, char *bValue)
{
 ZValue a, b;
 a = FindValueNamed(aValue);
 b = FindValueNamed(bValue);
 AddFactLocationRelativeNextTo(a, b);
}

ProcessIMMED_RIGHT_OF
// Associates aValue with bValue, so that we know that aValue is located to the 
// immediate right of bValue. (Also, bValue is to the immediate left of aValue)
static void
ProcessIMMED_RIGHT_OF(char *aValue, char *bValue)
{
 ZValue a, b;
 a = FindValueNamed(aValue);
 b = FindValueNamed(bValue);
 AddFactLocationRelativeOnRight(a, b);
}

ProcessIMMED_LEFT_OF
// Associates aValue with bValue, so that we know that aValue is located to the 
// immediate left of bValue. (Also, bValue is to the immediate right of aValue)
static void
ProcessIMMED_LEFT_OF(char *aValue, char *bValue)
{
 ZValue a, b;
 a = FindValueNamed(aValue);
 b = FindValueNamed(bValue);
 AddFactLocationRelativeOnLeft(a, b);
}
static void
DoubleNullTerminate(char *line)
{
 long len = strlen(line);
 line[len + 1] = 0;
}

ProcessSOLVE
// Remembers that the remaining words are important, both values and  
// variables. The solution is done when every value mentioned here is known 
// for certain, and every variable has a compatible (if not guaranteed) value.
static void
ProcessSOLVE(char *currWord, char *nextWord)
{
 DoubleNullTerminate(nextWord);
 while (*currWord)
  {
  ZValue val = FindValueNamed(currWord);
  if (val)
   AddFactImportantValue(val);
  else
   {
   ZType type = FindTypeNamed(currWord);
   if (type)
    AddFactImportantType(type);
   // else it was a relation
   }
  currWord = nextWord;
  nextWord = MakeWordBreak(nextWord);
  }
}

ProcessANSWER
// Remembers the ordering of the remaining words.
// This is the order that the fields in the solution lines 
// are filled with variable values. (zero-based)
static void
ProcessANSWER(char *currWord, char *nextWord)
{
 long i = 0;
 ZType type;
 DoubleNullTerminate(nextWord);
 while (*currWord)
  {
  type = FindTypeNamed(currWord);
  if (!type)
   DebugStr("\pCan't find this type!");
  else
   {
   SetPrintOrder(type, i);
   i++;
   }
  currWord = nextWord;
  nextWord = MakeWordBreak(nextWord);
  }
}

ProcessRelation
static void
ProcessRelation(char *firstWord, char *relation, char *thirdWord)
{
#pragma unused (relation)
 ZValue aVal;
 ZValue bVal;
 aVal = FindValueNamed(firstWord);
 if (!aVal)
  return; // this is probably a meaningless 'variable relation variable' clue
 bVal = FindValueNamed(thirdWord);
 if (!bVal)
  {
  DebugStr("\pNot a known value!");
  return; // this is probably an error!
  }
 AddFactSameRow(aVal, bVal);
}

ProcessAClue
static void
ProcessAClue(CStr255 clue)
{
 char *firstWord = clue, *secondWord, *nextWord;
 secondWord = MakeWordBreak(firstWord);
 nextWord = MakeWordBreak(secondWord);
 if (0 == strcmp(gsrISA, secondWord))
  ProcessISA(firstWord, nextWord);
 else if (0 == strcmp(gsrIS_LOCATED, secondWord))
  ProcessIS_LOCATED(firstWord, nextWord);
 else if (0 == strcmp(gsrNEXT_TO, secondWord))
  ProcessNEXT_TO(firstWord, nextWord);
 else if (0 == strcmp(gsrIMMED_RIGHT_OF, secondWord))
  ProcessIMMED_RIGHT_OF(firstWord, nextWord);
 else if (0 == strcmp(gsrIMMED_LEFT_OF, secondWord))
  ProcessIMMED_LEFT_OF(firstWord, nextWord);
 else if (0 == strcmp(gsqSOLVE, firstWord))
  ProcessSOLVE(secondWord, nextWord);
 else if (0 == strcmp(gsqANSWER, firstWord))
  ProcessANSWER(secondWord, nextWord);
 else
  ProcessRelation(firstWord, secondWord, nextWord);
}

void PropogateUniqueLocInColumn(ZValue val);

ClearColumn
// Clear this bit in every value in this variable Except 'skip' (the 
// source of clearing the others) Propogate newly solved locations, 
// too. Don't propogate contradictions (zeroes)
static void
ClearColumn(ZType column, ZLocation bit, ZValue skip)
{
 const ZLocation clearMask = ~bit;
 ZValue v;
 for (v = FirstValueOf(column); v != nil; v = NextOf(v))
  if (v == skip)
   continue;
  else {
   ZLocation originalLoc = LocationOf(v);
   ZLocation newLoc = originalLoc & clearMask;
   if (newLoc != originalLoc)
    {
    ZSolutionState st = IsSolvedLoc(newLoc);
    SetLocationOf(v, newLoc);
    if (newLoc && st == kSolved)
     PropogateUniqueLocInColumn(v);
    //else if (st == kContradiction)
    //else if (st == KUnsolved)
    }
   }
}

PropogateUniqueLocInColumn
// Erases this value's location bit from every other value
// of this variable/column/type
static void
PropogateUniqueLocInColumn(ZValue val)
{
 ZLocation loc = LocationOf(val);
 SetLocationOf(val, loc);
 ClearColumn((ZType)TypeOf(val), loc, val);
}

typedef enum {
 kResultContradiction,
 kResultProgress,
 kResultSolvedFirst,
 kResultSolvedSecond,
 kResultSolvedBoth,
 kResultNoProgress
 } ZApplyResult;

CalculateApplyResult
static ZApplyResult
CalculateApplyResult(ZLocation result1, ZLocation result2,
  ZLocation original1, ZLocation original2)
{
 if (!result1 || !result2)
  return kResultContradiction;
 if (result1 != original1)
  if (IsSolvedLoc(result1) == kSolved)
   if (result2 != original2)
    if (IsSolvedLoc(result2) == kSolved)
     return kResultSolvedBoth;
    else
     return kResultSolvedFirst; // and progress on 2nd
   else
    return kResultSolvedFirst;
  else // progress on first
   if (result2 != original2)
    if (IsSolvedLoc(result2) == kSolved)
     return kResultSolvedSecond; // and progress on 1st
    else
     return kResultProgress;
   else
    return kResultProgress;
 else if (result2 != original2)
  if (IsSolvedLoc(result2) == kSolved)
   return kResultSolvedSecond;
  else
   return kResultProgress;
 else
  return kResultNoProgress;
}

ApplyNEXT_TO
static ZApplyResult
ApplyNEXT_TO(ZValue first, ZValue second)
{
 ZLocation original1, original2;
 ZLocation result1 = original1 = LocationOf(first);
 ZLocation result2 = original2 = LocationOf(second);
 ZLocation temp1, temp2;
 do {
  temp1 = result1;
  temp2 = result2;
  // first is to right or left of second
  result1 &= ((temp2 << 1) | (temp2 >> 1));
  // second is to right or left of first
  result2 &= ((temp1 << 1) | (temp1 >> 1));
  } while ((temp1 != result1) || (temp2 != result2));
 SetLocationOf(first, result1);
 SetLocationOf(second, result2);
 return CalculateApplyResult(result1, result2, 
          original1, original2);
}

ApplyRIGHT_OF
static ZApplyResult
ApplyRIGHT_OF(ZValue first, ZValue second)
{
 ZLocation original1, original2;
 ZLocation result1 = original1 = LocationOf(first);
 ZLocation result2 = original2 = LocationOf(second);
 ZLocation temp1, temp2;
 do {
  temp1 = result1;
  temp2 = result2;
  // first is to right of second
  result1 &= (temp2 >> 1);
  // second is to left of first
  result2 &= (temp1 << 1);
  } while ((temp1 != result1) || (temp2 != result2));
 SetLocationOf(first, result1);
 SetLocationOf(second, result2);
 return CalculateApplyResult(result1, result2, 
          original1, original2);
}

ApplyLEFT_OF
static ZApplyResult
ApplyLEFT_OF(ZValue first, ZValue second)
{
 ZLocation original1, original2;
 ZLocation result1 = original1 = LocationOf(first);
 ZLocation result2 = original2 = LocationOf(second);
 ZLocation temp1, temp2;
 do {
  temp1 = result1;
  temp2 = result2;
  // first is to left of second
  result1 &= (temp2 << 1);
  // second is to right of first
  result2 &= (temp1 >> 1);
  } while ((temp1 != result1) || (temp2 != result2));
 SetLocationOf(first, result1);
 SetLocationOf(second, result2);
 return CalculateApplyResult(result1, result2, 
          original1, original2);
}

ApplySAME_ROW
static ZApplyResult
ApplySAME_ROW(ZValue first, ZValue second)
{
 ZLocation original1 = LocationOf(first);
 ZLocation original2 = LocationOf(second);
 // first is in the same row as the second
 ZLocation result = (original1 & original2);
 SetLocationOf(first, result);
 SetLocationOf(second, result);
 return CalculateApplyResult(result, result, 
          original1, original2);
}

ApplyLOCATED_AT
// Set this values location to be loc
// NOTE: Clearing this bit in every other value in this variable/column happens later
static ZApplyResult
ApplyLOCATED_AT(ZValue first, ZLocation loc)
{
 // first is located at loc
 SetLocationOf(first, loc);
 return kResultSolvedFirst;
}

ApplyAClue
static ZApplyResult
ApplyAClue(ZClue clue)
{
 ZValue first = FirstValOf(clue);
 ZValue second = SecondValOf(clue);
 ZApplyResult rslt;
 switch(TypeOf(clue))
  {
  case kClueNextTo: rslt =
   ApplyNEXT_TO(first, second);
   break;
  case kClueImmedRightOf: rslt =
   ApplyRIGHT_OF(first, second);
   break;
  case kClueImmedLeftOf: rslt =
   ApplyLEFT_OF(first, second);
   break;
  case kClueSameRowAs: rslt =
   ApplySAME_ROW(first, second);
   break;
  case kClueLocatedAt: rslt =
   ApplyLOCATED_AT(first, (ZLocation) second);
   break;
  }
 switch (rslt)
  {
  case kResultSolvedBoth:
   PropogateUniqueLocInColumn(first);
      // fall through for second, too
  case kResultSolvedSecond:
   PropogateUniqueLocInColumn(second);
   break;
  case kResultSolvedFirst:
   PropogateUniqueLocInColumn(first);
   break;
  default:
  case kResultContradiction:
  case kResultProgress:
  case kResultNoProgress:
   break;
  }
 return rslt;
}

IsSatisfied
// Returns true if the clue has been satisfied
// ASSUMES it has just been applied (thus several check only one value)
static ZSolutionState
IsSatisfied(ZClue clue)
{
 ZSolutionState satisfied;
 switch(TypeOf(clue))
  {
  case kClueNextTo: satisfied =
   IsSolvedLoc(LocationOf(FirstValOf(clue)));
   if (satisfied == kSolved)
    satisfied =
     IsSolvedLoc(LocationOf(SecondValOf(clue)));
   break;
  case kClueImmedRightOf:
  case kClueImmedLeftOf:
  case kClueSameRowAs:
  case kClueLocatedAt: satisfied =
   IsSolvedLoc(LocationOf(FirstValOf(clue)));
   break;
  }
 return satisfied;
}

CheckLocations
// Check one column, col, for newly unique locations. Check only the locations 
// left in val. Check only the values below/after val, since the others were 'solved' (had 
// unique solutions already) Stop after finding the first one (and making it unique)
// Return whether any changes were made
static Boolean
CheckLocations(ZType col, ZValue val)
{
 ZLocation currBit = kLeftBit;
 const ZLocation tryLocs = LocationOf(val);
 while (gMask & currBit) // for each location in puzzle
  {
  ZValue tryv;
  if (currBit & tryLocs != 0) // just locations in val
      {
      // check remaining values for this location
      for (tryv = NextOf(val); tryv != nil; tryv = NextOf(tryv))
    if (LocationOf(tryv) & currBit)
     break;    // found another value that could be in this location
   if (!tryv)    // a unique location!
    {
    SetLocationOf(val, currBit);
    ClearColumn(col, currBit, val);
    return true;
    }
   }
  currBit >>= 1;
  }
 return false;
}

CheckColumns
// Check each column for newly unique locations
// Return whether any changes were made
static Boolean
CheckColumns(void)
{
  ZType var;
  ZValue v = nil;
  Boolean changes = false;
  for (var = FirstVar(); var != nil; var = NextOf(var))
    {
    v = FirstValueOf(var);
    while (v != nil && (kSolved == IsSolvedLoc(LocationOf(v))))
      v = NextOf(v);
    if (v != nil)
      changes = changes || CheckLocations(var, v);
    }
  return changes;
}

ApplyEachUnsatisfiedClue
// Apply each clue in the 'unsatisfied' queue. Return what progress was made, unless 
// a contradiction was made, then return false to stop. Move satisfied clues to qSat.
static Boolean
ApplyEachUnsatisfiedClue(ZQ qSat)
{
 Boolean progress = false;
 ZQRec stillUnsatisfied;
 InitQ(&stillUnsatisfied);
 while (QNotEmpty(gQUn))
  {
  ZClue clue = DeQ(gQUn);
  ZApplyResult rslt = ApplyAClue(clue);
  if (rslt == kResultContradiction)
   {
   EnQ(qSat, clue);
   MergeQ(&stillUnsatisfied, gQUn);
   return false;    // contradiction reached
   }
  if ((rslt == kResultSolvedBoth) ||
   (rslt == kResultSolvedFirst &&
    TypeOf(clue) == kClueLocatedAt))
   {
   progress = true;
   EnQ(qSat, clue);
   }
  else if (rslt == kResultNoProgress)
   EnQ(&stillUnsatisfied, clue);
  else {
   progress = true;
   EnQ(&stillUnsatisfied, clue);
   }
  }
 MoveQ(&stillUnsatisfied, gQUn);
 if (!progress)
  progress = CheckColumns();
 return progress;
}

VerifyCluesStillSatisfied
// Verify each clue in the queue. Return true if no clues fail to say they are satisfied
static Boolean
VerifyCluesStillSatisfied(ZQ q)
{
#pragma unused(q)
 return true;
}

VerifyNoContradictions
// Verify each location in the current block, gL
// Return true if no locations are zero (i.e., impossible)
static Boolean
VerifyNoContradictions(void)
{
 ZLocation *currLoc = gL;
 ZLocation *stop = gL + gkBlockSizeInLongs;
 while (currLoc < stop)
  if (*currLoc++ == 0)
   return false;
 return true;
}

WriteRow
// 'loc' has just the bit set in the row position that we're looking for
static void
WriteRow(CStr255 row, ZLocation loc)
{
 ZValue v;
 long i;
 row[0] = 0;
 for(i = 0; i < gDim; i++)
  {
  ZType t = FindTypeOrdered(i);
  for (v = FirstValueOf(t); v != nil; v = NextOf(v))
   if ((LocationOf(v) & loc) != 0)
    { // add the value's name to the line
    long len;
    strcat(row, NameOf(v));
    len = strlen(row);
    row[len] = 0x20;    // space between words
    row[len+1] = 0;      // re-null-terminate
    }
  }
}

WriteDownProblem
static void
WriteDownProblem(CStr255 clues[], long numClues, long dim)
{
 long i;
 InitStructure(numClues, dim);
 for (i = 0; i < numClues; i ++)
  ProcessAClue(clues[i]);
}

ThinkRealHard
// Apply clues until no more progress can be made, then enumerate all 
// remaining possible configurations and test them recursively. Set the top-level 
// location block to the first configuration that does not contradict any facts.
static Boolean
ThinkRealHard(ZLocation *myBlock)
{
 ZQRec newlySatisfied;
 ZQ qNew = &newlySatisfied;
 ZValue vtry;
 ZLocation trylocs;
 ZLocation currBit;
 long i;
 Boolean progressMade;
 InitQ(qNew);
    // Apply knowledge
 do progressMade = ApplyEachUnsatisfiedClue(qNew);
 while (progressMade);
    // Test all locations for impossibility (zero possible
    // locations for a value means there was a contradiction)
 if (false == VerifyNoContradictions())
  {  // we have reached a contradiction
      // put the newly 'satisfied' clues back in the
      // unsatisfied list
  MergeQ(qNew, gQUn);
  return false;
  }
  // Generate-and-Test
 vtry = FindValueWithUnsolvedLocation();
 if (!vtry)
  {  // we have no more unsolved locations; done!
  MergeQ(qNew, gQUn);  // put them back so they can be freed
  return true;        // might be a solution
  }
 trylocs = LocationOf(vtry);
 currBit = kLeftBit;
 for (i = 0; i < gDim; i++, currBit >>= 1)
  if (currBit & trylocs)
   {
   ZLocation newBlock[kMaxValues];
   CopyLocations(myBlock, newBlock);
   gL = newBlock;
      // try new configuration by faking a clue
   ApplyLOCATED_AT(vtry, currBit);
   PropogateUniqueLocInColumn(vtry);
   if (true == ThinkRealHard(newBlock))
    {    // this configuration worked
    gL = myBlock;
    if (VerifyCluesStillSatisfied(qNew))
     {  // and verifies, so far, up to this level
     CopyLocations(newBlock, myBlock);
     MergeQ(qNew, gQUn);  // put them back so they can be freed
     return true;        // looks like a solution
     }
    MergeQ(qNew, gQUn);    // put them back so they can be freed
    return false;          // failed verify
    }
   gL = myBlock;
   }
 MergeQ(qNew, gQUn);
 return false;  // exhausted all configurations, none worked
}

WriteOutSolution
static void
WriteOutSolution(CStr255 solution[])
{
 long i = 0;
 for (i = 0; i < gDim; i++)
  WriteRow(solution[i], kLeftBit >> i);
 ReleaseMemory();
}

WhoOwnsZebra
void WhoOwnsZebra(
 long problemDimension,  /* number of problem variables */
 long numClues,        /* number of clues provided */
 CStr255 clues[],      /* the clues */
 CStr255 solution[]    /* storage for problemDimension result strings */
) {
 // Dr. Richard Feynmann's Problem-Solving Algorithm:
 WriteDownProblem(clues, numClues, problemDimension);
 ThinkRealHard(gL);
 WriteOutSolution(solution);
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

MarsEdit 3.6.8 - Quick and convenient bl...
MarsEdit is a blog editor for OS X that makes editing your blog like writing email, with spell-checking, drafts, multiple windows, and even AppleScript support. It works with with most blog services... Read more
BBEdit 11.0.3 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
Microsoft Office Preview 15.8 - Popular...
Welcome to the new and modern Microsoft Office for Mac. You will receive regular updates automatically until the official release in the second half of 2015. With the redesigned Ribbon and your... Read more
Yosemite Cache Cleaner 9.0.5 - Clear cac...
Yosemite Cache Cleaner is an award-winning general purpose tool for OS X. YCC makes system maintenance simple with an easy point-and-click interface to many OS X functions. Novice and expert users... Read more
ExpanDrive 4.3.2 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
RapidWeaver 6.0.8 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
Artlantis Studio 5.1.2.7 - 3D rendering...
Artlantis Studio is a unique and ideal tool for performing very high resolution rendering easily and in real time. The new FastRadiosity engine now lets you compute images in radiosity-even in... Read more
MacUpdate Desktop 6.0.5 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
BitTorrent Sync 2.0.82 - Sync files secu...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Google Drive 1.20 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more

Bored? MyLeisure FreeTime Maximizer Will...
Bored? MyLeisure FreeTime Maximizer Will Take Care of That! Posted by Jessica Fisher on March 5th, 2015 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
New Publisher Allstar Games Heads West w...
Allstar Games has announced its first mobile title designed for western audiences, Allstar Heroes. The game will be a massive online battle arena (MOBA) that offers dozens of heroes for you to collect and pit against your opponents. As each hero has... | Read more »
RAD Boarding Review
RAD Boarding Review By Jennifer Allen on March 5th, 2015 Our Rating: :: NEARLY RADUniversal App - Designed for iPhone and iPad RAD Boarding isn’t quite one of the greats, but it has potential.   | Read more »
Presenting the International Mobile Gami...
11th Annual International Mobile Gaming Awards ceremony, hosted by actress Allison Haislip, gathered mobile game developers and publishers from around the world. They chose 13 winners out of the 93 nominations. British studio USTWO won the the Grand... | Read more »
AG Drive Review
AG Drive Review By Tre Lawrence on March 5th, 2015 Our Rating: :: FUTURISTIC STREET RACING.Universal App - Designed for iPhone and iPad Futuristic racing… interstellar style.   | Read more »
GDC 2015 – Nightmare Guardians is an Int...
GDC 2015 – Nightmare Guardians is an Interesting Hybrid of MOBA and Lane Defense Posted by Rob Rich on March 5th, 2015 [ permalink ] I have to say that lane defense (i.e. | Read more »
Overkill 3 Review
Overkill 3 Review By Tre Lawrence on March 5th, 2015 Our Rating: :: WHO'S NEXT?Universal App - Designed for iPhone and iPad Cover system gameplay in the third-person.   Developer: Craneballs Price: Free Version Reviewed: 1.1.6... | Read more »
Warner Bros. Interactive Entertainment A...
Warner Bros. has some exciting games coming down the pipe! | Read more »
GDC 2015 – Star Trek Timelines will Prob...
GDC 2015 – Star Trek Timelines will Probably Make Your Inner Trekkie Squeal With Glee Posted by Rob Rich on March 4th, 2015 [ permalink ] Any popular fictional universe has its fair share of fan fiction – where belo | Read more »
Protect Yourself from an Onslaught of Ca...
Surprise Attack Games has announced a Cat-astrophic new physics puzzler called Fort Meow! In the game, a young girl named Nia finds her grandfather’s journal which triggers an all mighty feline attack! Why do the cats want the journal? Who knows,... | Read more »

Price Scanner via MacPrices.net

Apple restocks refurbished 15-inch Retina Mac...
The Apple Store has restocked Apple Certified Refurbished 2014 15″ Retina MacBook Pros, available for up to $400 off the cost of new models. An Apple one-year warranty is included with each model,... Read more
Roundup of MacBook Air sale prices, models up...
B&H Photo has MacBook Airs on sale for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 100 off MSRP - 11″ 256GB MacBook Air: $999 $100... Read more
New Firstrade Mobile App Enables On-The-Go Tr...
Firstrade Securities Inc. has announced its new mobile app, which gives investors immediate access to the company’s trading platform on all mobile devices. The app was developed in-house and was... Read more
Sonnet Introduces USB 3.0 + eSATA Thunderbolt...
Sonnet has announced the launch of its new USB 3.0 + eSATA Thunderbolt Adapter for easy connectivity to USB 3.0 devices and eSATA storage, and USB 3.0 + Gigabit Ethernet Thunderbolt Adapter for easy... Read more
Apple restocks refurbished 27-inch 5K iMacs f...
The Apple Store has restocked Apple Certified Refurbished 27″ 3.5GHz 5K iMacs for $2119 including free shipping. Their price is $380 off the cost of new models, and it’s the lowest price available... Read more
Free Clean Reader Mobile App Hides Swear Word...
The new Clean Reader app, now available in the Apple App Store and Google Play, delivers the opportunity of reading any book without being exposed to profanity. By selecting how clean they want their... Read more
Kinsa Launches “Groups” App to Monitor Illnes...
Kinsa, makers of the first FDA approved app-enabled smartphone thermometer thst won the 2013 Cleveland Clinic Medical Innovation Grand Prize and recently appeared in Apple’s “Parenthood” TV... Read more
iPad: A More Positive Outlook – The ‘Book Mys...
It’s good to hear someone saying positive things about the iPad. I’ve been trying to bend my mind around how Apple’s tablet could have gone from zero to bestselling personal computing device on the... Read more
Mac Pros on sale for up to $279 off MSRP
Amazon has Mac Pros in stock and on sale for up to $279 off MSRP. Shipping is free: - 4-Core Mac Pro: $2725.87, $273 off MSRP (9%) - 6-Core Mac Pro: $3719.99, $279 off MSRP (7%) Read more
Sale! 13-inch Retina MacBook Pros for up to $...
B&H Photo has 13″ Retina MacBook Pros on sale for up to $205 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.6GHz/128GB Retina MacBook Pro: $1219.99 save $80 - 13″ 2.... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.