Jan 98 Challenge
Volume Number: 14
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
#else
typedef long int32;
typedef unsigned long uint32;
#endif
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
#include
#include // for malloc and free
typedef enum {
kClueNextTo,
kClueImmedRightOf,
kClueImmedLeftOf,
kClueSameRowAs,
kClueLocatedAt
} ZClueType;
kContradiction = -1,
kSolved = 0,
kUnsolved = 1
// 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;
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
// a ZType is the definition of a variable, including its name and
possible values
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