May 93 Challenge
Volume Number: 9
Issue Number: 5
Column Tag: Programmers’ Challenge
Programmers’ Challenge 
By Mike Scanlin, MacTech Magazine Regular Contributing Author
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
MAGIC ADDITIONS
Thanks to WarrenPM (America Online) for suggesting this month’s Challenge:
Find all of the correct addition problems of the form: 123 + 456 = 789 using each of
the digits 1 through 9 once each in every solution. For example: 124 + 659 = 783 is
true, uses only the digits 1 through 9 and uses each only once.
The prototype of the function you write is:
unsigned short CountMagicAdditions();
You’re not required to produce the actual equations as output, only the correct
number of them. Note: This does not mean you should write a separate function that
precomputes the answer and then submit a solution that consists of return
(kNumMagicAdditions);. Also note that “124 + 659 = 783” and “659 + 124 = 783”
are the same thing and only count as 1 magic addition.
Warren says that he wrote a version in AppleSoft BASIC years ago that did lots of
string manipulation and took two days to run on his Apple ][. Hopefully your solution
in C on my Quadra 700 will run somewhat faster. If you’re really motivated, you could
make CountMagicAdditions take a parameter n which would range in value from 3 to 9
and would represent the number of digits used by each equation (and the values of the
digits are from 1 to n). For instance: “1 + 2 = 3” is the only solution when n = 3.
This more general purpose routine is not required to win the Challenge, though.
TWO MONTHS AGO WINNER
This month we have our first repeat winner of the Programmer’s Challenge.
Congratulations to Ronald Nepsund (Northridge, CA) for winning the “Count Unique
Words” challenge (Ronald previously won the Travelling Salesman challenge). Close
behind, with similar algorithms but slightly different implementations are David
Biolsi (Ithaca, NY) and Richard Parker (Irvine, CA).
Here’s a summary of the entries that didn’t crash. The bytes column is the code
size, test 1 is the ticks to complete a 17K input file yielding 796 unique words; and
test 2 is the ticks to complete a 40K input file yielding 817 unique words (each test
was run 20 times and the ticks represent the total time for all instances of each of the
two tests):
Name bytes test 1 test 2
Ronald Nepsund 660 63 127
David Biolsi 636 86 146
Richard Parker 386 96 168
Bob Boonstra 856 107 212
JohnnyL 782 124 247
Stepan Riha 418 157 248
Mark Nilsen 588 137 264
Dave Darrah 266 6180 16240
Thank you to all the people who responded to my request for feedback on this
column. I will implement as many of your good ideas as I can. The basic feeling was that
the challenges are about the right difficulty level as they are but that once in a while a
really hard or really easy one might be nice. The vote on Mac-only vs.
platform-independent Challenges is split 50/50.
Several people complained about not having enough time to work on the
challenge. Neil is working on a way to make the new challenges available electronically
before the issue that contains them arrives in your mail box. [Check the online
services for more information. See page two for info on which services we support. -
Ed.] Hopefully that will help. The other option is to separate the challenge from the
solution by three months instead of two. If the electronic option doesn’t help then we
may go that route.
I received my second complaint that I don’t provide enough info in the challenge
specification to adequately solve it. For instance, in the Count Unique Words challenge
one person wondered if he was allowed to overwrite the input buffer or not. Well, I
don’t think I’m capable of predicting all such questions up front but I will make more
of an effort to eliminate confusion. Also, in the event that I give a less than clear
specification, you can always e-mail me at one of the Challenge addresses for
clarification (which is probably better than making a really gross wrong assumption
and having your entry disqualified).
One question raised by two people that relates to the specification issue is the
ANSI compatibility issue and whether or not you’re allowed to make toolbox calls. I had
assumed that since this was a Mac magazine people would feel free to call NewPtr
instead of malloc (as many who have submitted solutions have done). I guess that was a
bad assumption. So, the rules now state that you may make toolbox calls if you want to.
There will probably be a Challenge some day that is Mac-specific and requires toolbox
interaction but you’re certainly not required to use the toolbox if arriving at the
solution doesn’t necessitate it (do whatever is fastest!).
TRAVELLING SALESMAN NOTE
Thanks to Stepan Riha (Austin, TX) for pointing out a further optimization in the
Travelling Salesman winning solution. Since you’re not really concerned with the
actual distance between points but only the relative distance between points, you don’t
need to use square root at all; you can just compare the squares of the distances instead
(which is faster). As Stepan says, “A careful analysis of a problem can often improve
performance better than careful optimization. Combination of the two gives you truly
great code!”
Here’s Ronald’s Count Unique Words winning solution:
/*****************************************************
* Unique word count by Ronald M. Nepsund
*
* The original text is uppercased with all non
* alphabetic characters turned to zero. The list of
* unique words works as follows: The word is used to
* to index into a 1024 entry hash table. The hash
* table contains pointers to the beginning of a linked
* list of word entries. Each word entry holds the
* length of the word and a pointer to the first
* occurance of the word in the original text. The
* linked list is ordered first by the length of the
* words and secondly alphabetically
****************************************************/
#define kHashMask 0x003FF
#define kHashSize 0x00400
typedef struct tNode{
short length;
Ptr wordPtr;
struct tNode *nextNode;
} WordTableRec, *WordTablePtr;
/* compare two strings */
short stringCmp(register short length,
register char *pnt1,
register char *pnt2)
{
while (-length > 0 && *pnt1==*pnt2) {
pnt1++; pnt2++;
}
return *pnt1-*pnt2;
}
CountUniqueWords(Ptr textPtr,
unsigned short byteCount)
{
Ptr endPnt,wordStartPtr;
register char *charPnt;
register long hash;
long count;
register short wordLength;
unsigned short totalWords = 0;
short i,cmp;
WordTablePtr *hashTable;
WordTablePtr wordTable;
register WordTablePtr linkPtr;
WordTablePtr last,wordTableEntry;
char charTypeTable[256];
long *zeroTblPtr;
//total possable number of words = 16556
//assuming a maximum size buffer of text
//I will use a hash table size of 1024
count = 4L * kHashSize;
//array of (NULL)Ptr’s
hashTable = (WordTablePtr *) NewPtrClear(count);
if (hashTable == 0L)
while (TRUE)
SysBeep(10); //not enough memory
count = 16556L * sizeof(WordTableRec);
wordTable = (WordTablePtr) NewPtr(count);
if (wordTable == 0L)
while (TRUE)
SysBeep(10); //not enough memory
//zero out the ‘charTypeTable’
zeroTblPtr = (long *) &charTypeTable;
for (i=0; i<64; i++)
*zeroTblPtr++ = 0;
//init lookup table used for uppercasing and
//identifying non letter characters
for (i=0;i<26; i++)
charTypeTable[i+(Byte) ‘A’] =
charTypeTable[i+(Byte) ‘a’] =
(char) (i+((Byte) ‘A’));
totalWords = 0;
charPnt = textPtr;
endPnt = textPtr + byteCount;
while (charPnt < endPnt) {
//skip spaces
while (charPnt < endPnt &&
charTypeTable[*charPnt] == 0)
charPnt++;
//pointer to begining of new word
wordStartPtr = charPnt;
hash = 0;
if (endPnt-charPnt > 255) {
//at least 255 characters left
//advance to the end of the word
//we can assume that a word is <=255 characters long
//uppercasing the text
//and doing a hash function
while (*charPnt = charTypeTable[*charPnt])
hash = (hash << 4) + *charPnt++ -
‘A’ + (hash >> 10);
}
else {
while (charPnt < endPnt &&
(*charPnt = charTypeTable[*charPnt]))
hash = (hash << 4) + *charPnt++ - ‘A’ + (hash >> 10);
}
wordLength = charPnt-wordStartPtr;
hash &= kHashMask;
linkPtr = (WordTablePtr) hashTable[hash];
last = NULL;
if (linkPtr==NULL) {
//this hash entry has not been used yet
wordTableEntry = &wordTable[totalWords++];
hashTable[hash] = wordTableEntry;
wordTableEntry->length = wordLength;
wordTableEntry->wordPtr = wordStartPtr;
wordTableEntry->nextNode = 0;
}
else {
//the entries are ordered by word length
//find the first entry that is as long or longer
while (linkPtr != NULL && linkPtr->length < wordLength)
{
last = linkPtr;
linkPtr = linkPtr->nextNode;
}
if (linkPtr == NULL) {
//no other entries as long as this one
wordTableEntry = &wordTable[totalWords++];
if (last == NULL)
hashTable[hash] = wordTableEntry;
else
last->nextNode = wordTableEntry;
wordTableEntry->length = wordLength;
wordTableEntry->wordPtr= wordStartPtr;
wordTableEntry->nextNode= NULL;
}
else if (linkPtr->length > wordLength) {
//insert betean ‘last’ and ‘linkPtr’
wordTableEntry = &wordTable[totalWords++];
if (last == NULL) {
wordTableEntry->nextNode = hashTable[hash];
hashTable[hash] = wordTableEntry;
}
else {
wordTableEntry->nextNode = last->nextNode;
last->nextNode = wordTableEntry;
}
wordTableEntry->length = wordLength;
wordTableEntry->wordPtr= wordStartPtr;
}
else {
//check entries with same word lengths
while (linkPtr != NULL &&
linkPtr->length == wordLength &&
(cmp = stringCmp(wordLength, wordStartPtr,
linkPtr->wordPtr)) <0) {
last = linkPtr;
linkPtr = linkPtr->nextNode;
}
if (linkPtr == NULL) {
//end of list and no match
wordTableEntry = &wordTable[totalWords++];
if (last == NULL)
hashTable[hash] = wordTableEntry;
else
last->nextNode = wordTableEntry;
wordTableEntry->length = wordLength;
wordTableEntry->wordPtr= wordStartPtr;
wordTableEntry->nextNode= 0;
}
else if (linkPtr->length > wordLength || cmp>0)
{
//insert word entry here
wordTableEntry = &wordTable[totalWords++];
if (last == NULL) { //hash table to point here
wordTableEntry->nextNode = hashTable[hash];
hashTable[hash] = wordTableEntry;
}
else {
wordTableEntry->nextNode= last->nextNode;
last->nextNode = wordTableEntry;
}
wordTableEntry->length = wordLength;
wordTableEntry->wordPtr = wordStartPtr;
}
}
}
}
DisposePtr((Ptr) hashTable);
DisposePtr((Ptr) wordTable);
return totalWords;
}
The Rules
Here’s how it works: Each month there will be a different programming challenge
presented here. First, you must write some code that solves the challenge. Second, you
must optimize your code (a lot). Then, submit your solution to MacTech Magazine
(formerly MacTutor). A winner will be chosen based on code correctness, speed, size
and elegance (in that order of importance) as well as the postmark of the answer. In
the event of multiple equally desirable solutions, one winner will be chosen at random
(with honorable mention, but no prize, given to the runners up). The prize for the
best solution each month is $50 and a limited edition “The Winner! MacTech Magazine
Programming Challenge” T-shirt (not to be found in stores).
In order to make fair comparisons between solutions, all solutions must be in
ANSI compatible C (i.e., don’t use Think’s Object extensions). However, you may call
any routine in the Macintosh toolbox you want (i.e., it doesn’t matter if you use
NewPtr instead of malloc). All entries will be tested with the FPU and 68020 flags
turned off in THINK C. When timing routines, the latest version of THINK C will be
used (with ANSI Settings plus “Honor ‘register’ first” and “Use Global Optimizer”
turned on) so beware if you optimize for a different C compiler.
The solution and winners for this month’s Programmers’ Challenge will be
published in the issue two months later. All submissions must be received by the 10th
day of the month printed on the front of this issue.
All solutions should be marked “Attn: Programmers’ Challenge Solution” and
sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or
preferably, e-mail - AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com,
and CompuServe: 71552,174. If you send via snail mail, please include a disk with
the solution and all related files (including contact information). See page 2 for
information on “How to Contact Xplain Corporation.”
MacTech Magazine reserves the right to publish any solution entered in the
Programming Challenge of the Month and all entries are the property of MacTech
Magazine upon submission. The submission falls under all the same conventions of an
article submission.