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);
}
 
AAPL
$111.78
Apple Inc.
-0.87
MSFT
$47.66
Microsoft Corpora
+0.14
GOOG
$516.35
Google Inc.
+5.25

MacTech Search:
Community Search:

Software Updates via MacUpdate

CleanApp 5.0.0 Beta 5 - Application dein...
CleanApp is an application deinstaller and archiver.... Your hard drive gets fuller day by day, but do you know why? CleanApp 5 provides you with insights how to reclaim disk space. There are... Read more
Monolingual 1.6.2 - Remove unwanted OS X...
Monolingual is a program for removing unnecesary language resources from OS X, in order to reclaim several hundred megabytes of disk space. It requires a 64-bit capable Intel-based Mac and at least... Read more
NetShade 6.1 - Browse privately using an...
NetShade is an Internet security tool that conceals your IP address on the web. NetShade routes your Web connection through either a public anonymous proxy server, or one of NetShade's own dedicated... Read more
calibre 2.13 - Complete e-library manage...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Mellel 3.3.7 - Powerful word processor w...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
ScreenFlow 5.0.1 - Create screen recordi...
Save 10% with the exclusive MacUpdate coupon code: AFMacUpdate10 Buy now! ScreenFlow is powerful, easy-to-use screencasting software for the Mac. With ScreenFlow you can record the contents of your... Read more
Simon 4.0 - Monitor changes and crashes...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more
BBEdit 11.0.2 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
ExpanDrive 4.2.1 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Adobe After Effects CC 2014 13.2 - Creat...
After Effects CC 2014 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous After Effects customer). After Effects CS6 is still available... Read more

Latest Forum Discussions

See All

Make your own Tribez Figures (and More)...
Make your own Tribez Figures (and More) with Toyze Posted by Jessica Fisher on December 19th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
So Many Holiday iOS Sales Oh My Goodness...
The holiday season is in full-swing, which means a whole lot of iOS apps and games are going on sale. A bunch already have, in fact. Naturally this means we’re putting together a hand-picked list of the best discounts and sales we can find in order... | Read more »
It’s Bird vs. Bird in the New PvP Mode f...
It’s Bird vs. Bird in the New PvP Mode for Angry Birds Epic Posted by Jessica Fisher on December 19th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Telltale Games and Mojang Announce Minec...
Telltale Games and Mojang Announce Minecraft: Story Mode – A Telltale Games Series Posted by Jessica Fisher on December 19th, 2014 [ permalink ] | Read more »
WarChest and Splash Damage Annouce Their...
WarChest and Splash Damage Annouce Their New Game: Tempo Posted by Jessica Fisher on December 19th, 2014 [ permalink ] WarChest Ltd and Splash Damage Ltd are teaming up again to work | Read more »
BulkyPix Celebrates its 6th Anniversary...
BulkyPix Celebrates its 6th Anniversary with a Bunch of Free Games Posted by Jessica Fisher on December 19th, 2014 [ permalink ] BulkyPix has | Read more »
Indulge in Japanese cuisine in Cooking F...
Indulge in Japanese cuisine in Cooking Fever’s new sushi-themed update Posted by Simon Reed on December 19th, 2014 [ permalink ] Lithuanian developer Nordcurrent has yet again updated its restaurant simulat | Read more »
Badland Daydream Level Pack Arrives to C...
Badland Daydream Level Pack Arrives to Celebrate 20 Million Downloads Posted by Ellis Spice on December 19th, 2014 [ permalink ] | Read more »
Far Cry 4, Assassin’s Creed Unity, Desti...
Far Cry 4, Assassin’s Creed Unity, Destiny, and Beyond – AppSpy Takes a Look at AAA Companion Apps Posted by Rob Rich on December 19th, 2014 [ permalink ] These day | Read more »
A Bunch of Halfbrick Games Are Going Fre...
A Bunch of Halfbrick Games Are Going Free for the Holidays Posted by Ellis Spice on December 19th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

The Apple Store offering free next-day shippi...
The Apple Store is now offering free next-day shipping on all in stock items if ordered before 12/23/14 at 10:00am PT. Local store pickup is also available within an hour of ordering for any in stock... Read more
It’s 1992 Again At Sony Pictures, Except For...
Techcrunch’s John Biggs interviewed a Sony Pictures Entertainment (SPE) employee, who quite understandably wished to remain anonymous, regarding post-hack conditions in SPE’s L.A office, explaining “... Read more
Holiday sales this weekend: MacBook Pros for...
 B&H Photo has new MacBook Pros on sale for up to $300 off MSRP as part of their Holiday pricing. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1699... Read more
Holiday sales this weekend: MacBook Airs for...
B&H Photo has 2014 MacBook Airs on sale for up to $120 off MSRP, for a limited time, for the Thanksgiving/Christmas Holiday shopping season. Shipping is free, and B&H charges NY sales tax... Read more
Holiday sales this weekend: iMacs for up to $...
B&H Photo has 21″ and 27″ iMacs on sale for up to $200 off MSRP including free shipping plus NY sales tax only. B&H will also include a free copy of Parallels Desktop software: - 21″ 1.4GHz... Read more
Holiday sales this weekend: Mac minis availab...
B&H Photo has new 2014 Mac minis on sale for up to $80 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 1.4GHz Mac mini: $459 $40 off MSRP - 2.6GHz Mac mini: $629 $70 off MSRP... Read more
Holiday sales this weekend: Mac Pros for up t...
B&H Photo has Mac Pros on sale for up to $500 off MSRP. Shipping is free, and B&H charges sales tax in NY only: - 3.7GHz 4-core Mac Pro: $2599, $400 off MSRP - 3.5GHz 6-core Mac Pro: $3499, $... Read more
Save up to $400 on MacBooks with Apple Certif...
The Apple Store has Apple Certified Refurbished 2014 MacBook Pros and MacBook Airs available for up to $400 off the cost of new models. An Apple one-year warranty is included with each model, and... Read more
Save up to $300 on Macs, $30 on iPads with Ap...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
iOS and Android OS Targeted by Man-in-the-Mid...
Cloud services security provider Akamai Technologies, Inc. has released, through the company’s Prolexic Security Engineering & Research Team (PLXsert), a new cybersecurity threat advisory. The... Read more

Jobs Board

*Apple* Store Leader Program (US) - Apple, I...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on experience, Read more
Project Manager, *Apple* Financial Services...
**Job Summary** Apple Financial Services (AFS) offers consumers, businesses and educational institutions ways to finance Apple purchases. We work with national and Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.