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

NetShade 6.3.1 - Browse privately using...
NetShade is an anonymous proxy and VPN app+service for Mac. Unblock your Internet through NetShade's high-speed proxy and VPN servers spanning seven countries. NetShade masks your IP address as you... Read more
Dragon Dictate 4.0.7 - Premium voice-rec...
With Dragon Dictate speech recognition software, you can use your voice to create and edit text or interact with your favorite Mac applications. Far more than just speech-to-text, Dragon Dictate lets... Read more
Persecond 1.0.2 - Timelapse video made e...
Persecond is the easy, fun way to create a beautiful timelapse video. Import an image sequence from any camera, trim the length of your video, adjust the speed and playback direction, and you’re done... Read more
GIMP 2.8.14p2 - Powerful, free image edi...
GIMP is a multi-platform photo manipulation tool. GIMP is an acronym for GNU Image Manipulation Program. The GIMP is suitable for a variety of image manipulation tasks, including photo retouching,... Read more
Sandvox 2.10.2 - Easily build eye-catchi...
Sandvox is for Mac users who want to create a professional looking website quickly and easily. With Sandvox, you don't need to be a Web genius to build a stylish, feature-rich, standards-compliant... Read more
LibreOffice 5.0.1.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
f.lux 36.1 - Adjusts the color of your d...
f.lux makes the color of your computer's display adapt to the time of day, warm at night and like sunlight during the day. Ever notice how people texting at night have that eerie blue glow? Or wake... Read more
VirtualBox 5.0.2 - x86 virtualization so...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
File Juicer 4.43 - Extract images, video...
File Juicer is a drag-and-drop can opener and data archaeologist. Its specialty is to find and extract images, video, audio, or text from files which are hard to open in other ways. In computer... Read more
Apple MainStage 3.2 - Live performance t...
MainStage 3 makes it easy to bring to the stage all the same instruments and effects that you love in your recording. Everything from the Sound Library and Smart Controls you're familiar with from... Read more

ReBoard: Revolutionary Keyboard (Utilit...
ReBoard: Revolutionary Keyboard 1.0 Device: iOS Universal Category: Utilities Price: $1.99, Version: 1.0 (iTunes) Description: Do everything within the keyboard without switching apps! If you are in WhatsApp, how do you schedule a... | Read more »
Tiny Empire (Games)
Tiny Empire 1.1.3 Device: iOS Universal Category: Games Price: $2.99, Version: 1.1.3 (iTunes) Description: Launch cannonballs and blow tiny orcs into thousands of pieces in this intuitive fantasy-themed puzzle shooter! Embark on an... | Read more »
Astropad Mini (Productivity)
Astropad Mini 1.0 Device: iOS iPhone Category: Productivity Price: $4.99, Version: 1.0 (iTunes) Description: *** 50% off introductory price! ​*** Get the high-end experience of a Wacom tablet at a fraction of the price with Astropad... | Read more »
Emo Chorus (Music)
Emo Chorus 1.0.0 Device: iOS Universal Category: Music Price: $1.99, Version: 1.0.0 (iTunes) Description: Realistic Choir simulator ranging from simple Chorus emulation to full ensemble Choir with 128 members. ### introductory offer... | Read more »
Forest Spirit (Games)
Forest Spirit 1.0.5 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.5 (iTunes) Description: | Read more »
Ski Safari 2 (Games)
Ski Safari 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: The world's most fantastical, fun, family-friendly skiing game is back and better than ever! Play as Sven's sister Evana, share... | Read more »
Lara Croft GO (Games)
Lara Croft GO 1.0.47768 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.47768 (iTunes) Description: Lara Croft GO is a turn based puzzle-adventure set in a long-forgotten world. Explore the ruins of an ancient... | Read more »
Whispering Willows (Games)
Whispering Willows 1.23 Device: iOS Universal Category: Games Price: $4.99, Version: 1.23 (iTunes) Description: **LAUNCH SALE 50% OFF** - Whispering Willows is on sale for 50% off ($4.99) until September 9th. | Read more »
Calvino Noir (Games)
Calvino Noir 1.1 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.1 (iTunes) Description: The film noir stealth game. Calvino Noir is the exploratory, sneaking adventure through the 1930s European criminal underworld.... | Read more »
Angel Sword (Games)
Angel Sword 1.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.0 (iTunes) Description: Prepare to adventure in the most epic full scale multiplayer 3D RPG for mobile! Experience amazing detailed graphics in full HD.... | Read more »

Price Scanner via MacPrices.net

Tablet Screen Sizes Expanding as iPad Pro App...
Larger screen sizes are gaining favor as the tablet transforms into a productivity device, with shipments growing 185 percent year-over-year in 2015. According to a new Strategy Analytics’ Tablet... Read more
Today Only: Save US$50 on Adobe Elements 13;...
Keep the memories. lose the distractions. Summer’s winding down and it’s time to turn almost perfect shots into picture perfect memories with Elements 13. And get the power to edit both photos and... Read more
1.4GHz Mac mini on sale for $449, save $50
Best Buy has the 1.4GHz Mac mini on sale for $50 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Price for online orders only, in-store price may vary... Read more
12-inch 1.1GHz Gold MacBook on sale for $1149...
B&H Photo has the 12″ 1.1GHz Gold Retina MacBook on sale for $1149.99 including free shipping plus NY sales tax only. Their price is $150 off MSRP, and it’s the lowest price available for this... Read more
27-inch 3.3GHz 5K iMac on sale for $1849, sav...
Best Buy has the 27″ 3.3GHz 5K iMac on sale for $1849.99. Their price is $150 off MSRP, and it’s the lowest price available for this model. Choose free shipping or free local store pickup (if... Read more
Worldwide Tablet Shipments Expected to Declin...
Does Apple badly need a touchscreen convertible/hybrid laptop MacBook? Yes, judging from a new market forecast from the International Data Corporation (IDC) Worldwide Quarterly Tablet Tracker, which... Read more
Continued PC Shipment Shrinkage Expected Thro...
Worldwide PC shipments are expected to fall by -8.7 percent in 2015 and not stabilize until 2017, according to the latest International Data Corporation (IDC) Worldwide Quarterly PC Tracker data. The... Read more
Imminent iPhone 6s Announcement Leads To 103%...
NextWorth Solutions, with its online and in-store electronics trade-in programs including http://NextWorth.com, reports that it has experienced a 103 percent surge in quoted trade-in values over the... Read more
Weekend Deal: 13-inch Retina MacBook Pros for...
Save up to $100 on the purchase of a new 2015 13″ Retina MacBook Pro at the following resellers this weekend. Shipping is free with each model: 2.7GHz/128GB MSRP $1299 2.7GHz/... Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more

Jobs Board

Senior Payments Security Manager - *Apple*...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior payments security manager to join the Apple Pay security team. You will Read more
Software QA Engineer, *Apple* Pay Security...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
Business Process Engineer ( *Apple* Online S...
**Job Summary** The Apple Online Support Planning team is looking for an experienced Business Process engineer to lead key business process improvement initiatives 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
Product Design Engineer - *Apple* Watch - A...
**Job Summary** Product Design Engineer Job Description As a member of Apple 's Watch product design team, you will help to create the next generation of the world's Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.