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

Adobe Muse CC 2017 2018.0.0 - Design and...
Muse CC 2018 is available as part of Adobe Creative Cloud for as little as $14.99/month (or $9.99/month if you're a previous Muse customer). Adobe Muse 2018 enables designers to create websites as... Read more
Adobe Animate CC 2017 18.0.0.107 - Anima...
Animate CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2018 (was Flash CC) lets you... Read more
Hopper Disassembler 4.3.0- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
GraphicConverter 10.5.1 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Delicious Library 3.7 - Import, browse a...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Duet 1.6.7.0 - Use your iPad as an exter...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a $14.99 iOS companion app. Version 1.6.7.0:... Read more
iExplorer 4.1.5 - View and transfer file...
iExplorer is an iPhone browser for Mac lets you view the files on your iOS device. By using a drag and drop interface, you can quickly copy files and folders between your Mac and your iPhone or... Read more
Alarm Clock Pro 10.3 - $19.95
Alarm Clock Pro isn't just an ordinary alarm clock. Use it to wake you up in the morning, send and compose e-mails, remind you of appointments, randomize the iTunes selection, control an internet... Read more
Tor Browser Bundle 7.0.7 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
Data Rescue 5.0.1 - Powerful hard drive...
Data Rescue’s new and improved features let you scan, search, and recover your files faster than ever before. We have modernized the file-preview capabilities, added new files types to the recovery... Read more

Wheels of Aurelia (Games)
Wheels of Aurelia 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: | Read more »
Halcyon 6: Starbase Commander guide - ti...
Halcyon 6 is a well-loved indie RPG with stellar tactical combat and some pretty good writing, too. It's now landed on the App Store, so mobile fans, if you're itching for a good intergalactic adventure, here's your game. Being a strategy RPG, the... | Read more »
Game of Thrones: Conquest guide - how to...
Fans of base building games might be excited to know that yet another entry in the genre has materialized - Game of Thrones: Conquest. Yes, you can now join the many kingdoms of the famed book series, or create your own, as you try to conquer... | Read more »
Halcyon 6: Starbase Commander (Games)
Halcyon 6: Starbase Commander 1.4.2.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.4.2.0 (iTunes) Description: An epic space strategy RPG with base building, deep tactical combat, crew management, alien diplomacy,... | Read more »
Legacy of Discord celebrates its 1 year...
It’s been a thrilling first year for fans of Legacy of Discord, the stunning PvP dungeon-crawling ARPG from YOOZOO Games, and now it’s time to celebrate the game’s first anniversary. The developers are amping up the festivities with some exciting... | Read more »
3 reasons to play Thunder Armada - the n...
The bygone days of the Battleship board game might have past, but naval combat simulators still find an audience on mobile. Thunder Armada is Chinese developer Chyogames latest entry into the genre, drawing inspiration from the explosive exchanges... | Read more »
Experience a full 3D fantasy MMORPG, as...
Those hoping to sink their teeth into a meaty hack and slash RPG that encourages you to fight with others might want to check out EZFun’s new Eternity Guardians. Available to download for iOS and Android, Eternity Guardians is an MMORPG that lets... | Read more »
Warhammer Quest 2 (Games)
Warhammer Quest 2 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dungeon adventures in the Warhammer World are back! | Read more »
4 of the best Halloween updates for mobi...
Halloween is certainly one of our favorite times for mobile game updates. Many popular titles celebrate this spooky season with fun festivities that can stretch from one week to even the whole month. As we draw closer and closer to Halloween, we'... | Read more »
Fire Rides guide - how to swing to succe...
It's another day, which means another Voodoo game has come to glue our hands to our mobile phones. Yes, it's been an especially prolific month for this particular mobile publisher, but we're certainly not complaining. Fire Rides is yet another... | Read more »

Price Scanner via MacPrices.net

Apple restocks full line of refurbished 13″ M...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
13″ 3.1GHz/256GB MacBook Pro on sale for $167...
Amazon has the 2017 13″ 3.1GHz/256GB Space Gray MacBook Pro on sale today for $121 off MSRP including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1678 $121 off MSRP Keep an... Read more
13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
15″ MacBook Pros on sale for up to $200 off M...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2249, $150... Read more
Roundup of Apple Certified Refurbished iMacs,...
Apple has a full line of Certified Refurbished 2017 21″ and 27″ iMacs available starting at $1019 and ranging up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free... Read more
Sale! 27″ 3.8GHz 5K iMac for $2098, save $201...
Amazon has the 27″ 3.8GHz 5K iMac (MNED2LL/A) on sale today for $2098 including free shipping. Their price is $201 off MSRP, and it’s the lowest price available for this model (Apple’s $1949... Read more
Sale! 10″ Apple WiFi iPad Pros for up to $100...
B&H Photo has 10.5″ WiFi iPad Pros in stock today and on sale for $50-$100 off MSRP. Each iPad includes free shipping, and B&H charges sales tax in NY & NJ only: – 10.5″ 64GB iPad Pro: $... Read more
Apple iMacs on sale for up to $130 off MSRP w...
B&H Photo has 21-inch and 27-inch iMacs in stock and on sale for up to $130 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2179 $... Read more
2017 3.5GHz 6-Core Mac Pro on sale for $2799,...
B&H Photo has the 2017 3.5GHz 6-Core Mac Pro (MD878LL/A) on sale today for $2799 including free shipping plus NY & NJ sales tax only . Their price is $200 off MSRP. Read more
12″ 1.2GHz Space Gray MacBook on sale for $11...
Amazon has the 2017 12″ 1.2GHz Space Gray Retina MacBook on sale for $100 off MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $1199.99 $100 off MSRP Read more

Jobs Board

Product Manager - *Apple* Pay on the *Appl...
Job Summary Apple is looking for a talented product manager to drive the expansion of Apple Pay on the Apple Online Store. This position includes a unique Read more
*Apple* Retail - Multiple Positions - Farmin...
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
Frameworks Engineer, *Apple* Watch - Apple...
Job Summary Join the team that is shaping the future of software development for Apple Watch! As a software engineer on the Apple Watch Frameworks team you will Read more
*Apple* News Product Marketing Mgr., Publish...
Job Summary The Apple News Product Marketing Manager will work closely with a cross-functional group to assist in defining and marketing new features and services. Read more
Fraud Analyst, *Apple* Advertising Platform...
Job Summary Apple Ad Platforms has an opportunity to redefine advertising on mobile devices. Apple reaches hundreds of millions of iPhone, iPod touch, and iPad Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.