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

DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Lyn 1.5.11 - Lightweight image browser a...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
NeoOffice 2014.11 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
LaunchBar 6.4 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Remotix 3.1.4 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more
DesktopLyrics 2.6.6 - Displays current i...
DesktopLyrics is an application that displays the lyrics of the song currently playing in "iTunes" right on your desktop. The lyrics for the song have to be set in iTunes; DesktopLyrics does nothing... Read more
VOX 2.5.1 - Music player that supports m...
VOX is a beautiful music player that supports many filetypes. The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all... Read more
NetNewsWire 4.0.0 - RSS and Atom news re...
NetNewsWire is the best way to keep up with the sites and authors you read most regularly. Let NetNewsWire pull down the latest articles, and read them in a distraction-free and Mac-like way. Native... Read more
MacUpdate Desktop 6.0.6 - 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

Biz Builder Delux (Games)
Biz Builder Delux 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Ah, there's nothing like the rhythmic bustle of a burgeoning business burg... especially when you're the one building it... | Read more »
Auroch Digital is Bringing Back Games Wo...
| Read more »
Carbo - Handwriting in the Digital Age...
Carbo - Handwriting in the Digital Age 1.0 Device: iOS Universal Category: Productivity Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Draggy Dead (Games)
Draggy Dead 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Ditch your dead end job and take up a rewarding career in Grave Robbing today!Guide the recently deceased to a fun filled life of... | Read more »
Bad Dinos (Games)
Bad Dinos 1.0.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Apple Watch isn't Great as a Fi...
| Read more »
Show the World What You See With Stre.am...
Live broadcasting is getting popular on mobile devices, which is why you can now get Stre.am, by Infinite Takes. [Read more] | Read more »
PhotoTime's 2.1 Update Adds Apple W...
The latest PhotoTime update is adding even more functionality to the handy photo organizing app. Yep, including Apple Watch support. [Read more] | Read more »
Oh My Glob! Adventure Time Puzzle Quest...
Finn and Jake are taking over D3 Go!'s popular puzzle game series in the upcoming Adventure Time Puzzle Quest. [Read more] | Read more »
Earthcore: Shattered Elements - Tips, Tr...
At first glance, Earthcore: Shattered Elements seems like a rather simple card-battling game. Once you’re introduced to skills that will change quite a bit. Even more so once you start to acquire hero cards. But it’s not so complicated that we... | Read more »

Price Scanner via MacPrices.net

OtterBox Maximizes Portability, Productivity...
From the kitchen recipe book to the boarsroom presentation, the OtterBox Agility Tablet System turns tablets into one of the most versatile pieces of handheld technology available. Available now, the... Read more
Launch of New Car App Gallery and Open Develo...
Automatic, a company on a mission to bring the power of the Internet into every car, has announced the launch of the Automatic App Gallery, an app store for nearly every car or truck on the road... Read more
Memorial Day Weekend Sale: 13-inch 1.6GHz Mac...
Best Buy has the new 13″ 1.6GHz/128GB MacBook Air on sale for $849 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Memorial Day Weekend Sale: 27-inch 3.5GHz 5K...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2099.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary.... Read more
Sale! 16GB iPad mini 3 for $349, save $50
B&H Photo has the 16GB iPad mini 3 WiFi on sale for $349 including free shipping plus NY sales tax only. Their price is $50 off MSRP, and it’s the lowest price available for this model. Read more
Price drop on 2014 15-inch Retina MacBook Pro...
B&H Photo has dropped prices on 2014 15″ Retina MacBook Pros by $200. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799.99 save $200 - 15″ 2.5GHz... Read more
With a Mission to Make Mobile Free, Scratch W...
Scratch Wireless, claiming to be the world’s first truly free mobile service, has announced the availability of a new Scratch-enabled Android smartphone, the Coolpad Arise. The smartphone is equipped... Read more
First-Ever Titanium Alloy Curved iPhone 6 Scr...
One of the most common problems with mobile phones is damage to the screens. The slightest drop can cause a dreaded spider web of gashes and cracks in the glass panel surface that can cost $hundreds... Read more
Preorder new 12-inch MacBook, $10 off, save o...
Adorama has new 12″ Retina MacBooks available for preorder for $10 off MSRP including free shipping plus NY & NJ sales tax only. For a limited time, Adorama will include a free Apple USB-C to USB... Read more
Will iOS 9 Finally Bring Productivity Friendl...
Ah, the irony. From its original announcement in 2010, Apple has doggedly insisted that the iPad remain “simple,” thus arbitrarily limiting its considerable potential as a content creation and... 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
Architect / Senior Software Engineer, *Apple...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with 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
*Apple* Pay Support Readiness Project Manage...
Changing the world is all in a day039s work at Apple . If you love innovation, here039s your chance to make a career of it. You039ll work hard. But the job comes with 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.