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 or source code disks.

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 kHashSize0x00400

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;
}

unsigned short
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;
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;

last = 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
{
}
//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) {
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
(cmp = stringCmp(wordLength, wordStartPtr,
}
//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);

}
```

## 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.

Community Search:
MacTech Search:

## Latest Forum Discussions

Fresh From the Land Down Under – The Tou...
After a two week hiatus, we are back with another episode of The TouchArcade Show. Eli is fresh off his trip to Australia, which according to him is very similar to America but more upside down. Also kangaroos all over. Other topics this week... | Read more »
TouchArcade Game of the Week: ‘Dungeon T...
I’m a little conflicted on this week’s pick. Pretty much everyone knows the legend of Dungeon Raid, the match-3 RPG hybrid that took the world by storm way back in 2011. Everyone at the time was obsessed with it, but for whatever reason the... | Read more »
Hello gentle readers, and welcome to the SwitchArcade Round-Up for July 19th, 2024. In today’s article, we finish up the week with the unusual appearance of a review. I’ve spent my time with Hot Lap Racing, and I’m ready to give my verdict. After... | Read more »
Draknek Interview: Alan Hazelden on Thin...
Ever since I played my first release from Draknek & Friends years ago, I knew I wanted to sit down with Alan Hazelden and chat about the team, puzzle games, and much more. | Read more »
The Latest ‘Marvel Snap’ OTA Update Buff...
I don’t know about all of you, my fellow Marvel Snap (Free) players, but these days when I see a balance update I find myself clenching my… teeth and bracing for the impact to my decks. They’ve been pretty spicy of late, after all. How will the... | Read more »
‘Honkai Star Rail’ Version 2.4 “Finest D...
HoYoverse just announced the Honkai Star Rail (Free) version 2.4 “Finest Duel Under the Pristine Blue" update alongside a surprising collaboration. Honkai Star Rail 2.4 follows the 2.3 “Farewell, Penacony" update. Read about that here. | Read more »
‘Vampire Survivors+’ on Apple Arcade Wil...
Earlier this month, Apple revealed that poncle’s excellent Vampire Survivors+ () would be heading to Apple Arcade as a new App Store Great. I reached out to poncle to check in on the DLC for Vampire Survivors+ because only the first two DLCs were... | Read more »
Homerun Clash 2: Legends Derby opens for...
Since launching in 2018, Homerun Clash has performed admirably for HAEGIN, racking up 12 million players all eager to prove they could be the next baseball champions. Well, the title will soon be up for grabs again, as Homerun Clash 2: Legends... | Read more »
‘Neverness to Everness’ Is a Free To Pla...
Perfect World Games and Hotta Studio (Tower of Fantasy) announced a new free to play open world RPG in the form of Neverness to Everness a few days ago (via Gematsu). Neverness to Everness has an urban setting, and the two reveal trailers for it... | Read more »
Meditative Puzzler ‘Ouros’ Coming to iOS...
Ouros is a mediative puzzle game from developer Michael Kamm that launched on PC just a couple of months back, and today it has been revealed that the title is now heading to iOS and Android devices next month. Which is good news I say because this... | Read more »

## Price Scanner via MacPrices.net

Amazon is still selling 16-inch MacBook Pros...
Prime Day in July is over, but Amazon is still selling 16-inch Apple MacBook Pros for \$500-\$600 off MSRP. Shipping is free. These are the lowest prices available this weekend for new 16″ Apple... Read more
Walmart continues to sell clearance 13-inch M...
Walmart continues to offer clearance, but new, Apple 13″ M1 MacBook Airs (8GB RAM, 256GB SSD) online for \$699, \$300 off original MSRP, in Space Gray, Silver, and Gold colors. These are new MacBooks... Read more
Apple is offering steep discounts, up to \$600...
Apple has standard-configuration 16″ M3 Max MacBook Pros available, Certified Refurbished, starting at \$2969 and ranging up to \$600 off MSRP. Each model features a new outer case, shipping is free,... Read more
Save up to \$480 with these 14-inch M3 Pro/M3...
Apple has 14″ M3 Pro and M3 Max MacBook Pros in stock today and available, Certified Refurbished, starting at \$1699 and ranging up to \$480 off MSRP. Each model features a new outer case, shipping is... Read more
Amazon has clearance 9th-generation WiFi iPad...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for \$80-\$100 off MSRP, starting only \$249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Apple is offering a \$50 discount on 2nd-gener...
Apple has Certified Refurbished White and Midnight HomePods available for \$249, Certified Refurbished. That’s \$50 off MSRP and the lowest price currently available for a full-size Apple HomePod today... Read more
The latest MacBook Pro sale at Amazon: 16-inc...
Amazon is offering instant discounts on 16″ M3 Pro and 16″ M3 Max MacBook Pros ranging up to \$400 off MSRP as part of their early July 4th sale. Shipping is free. These are the lowest prices... Read more
14-inch M3 Pro MacBook Pros with 36GB of RAM...
B&H Photo has 14″ M3 Pro MacBook Pros with 36GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 Pro MacBook Pro (... Read more
14-inch M3 MacBook Pros with 16GB of RAM on s...
B&H Photo has 14″ M3 MacBook Pros with 16GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$150-\$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 MacBook Pro (... Read more
Amazon is offering \$170-\$200 discounts on new...
Amazon is offering a \$170-\$200 discount on every configuration and color of Apple’s M3-powered 15″ MacBook Airs. Prices start at \$1129 for models with 8GB of RAM and 256GB of storage: – 15″ M3... Read more

## Jobs Board

*Apple* Systems Engineer - Chenega Corporati...
…LLC,** a **Chenega Professional Services** ' company, is looking for a ** Apple Systems Engineer** to support the Information Technology Operations and Maintenance Read more
Solutions Engineer - *Apple* - SHI (United...
**Job Summary** An Apple Solution Engineer's primary role is tosupport SHI customers in their efforts to select, deploy, and manage Apple operating systems and Read more
*Apple* / Mac Administrator - JAMF Pro - Ame...
Amentum is seeking an ** Apple / Mac Administrator - JAMF Pro** to provide support with the Apple Ecosystem to include hardware and software to join our team and Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more