TweetFollow Us on Twitter

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.

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

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

beaTunes 4.6.12 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music Library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Tinderbox 7.0.1 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
FotoMagico 5.4 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Direct Mail 4.3.9 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
Tinderbox 7.0.1 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
Direct Mail 4.3.9 - Create and send grea...
Direct Mail is an easy-to-use, fully-featured email marketing app purpose-built for OS X. It lets you create and send great looking email campaigns. Start your newsletter by selecting from a gallery... Read more
FotoMagico 5.4 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
beaTunes 4.6.12 - Organize your music co...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music Library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
Spotify 1.0.49.125. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Eye Candy 7.2.0.50 - 30 professional Pho...
Eye Candy renders realistic effects that are difficult or impossible to achieve in Photoshop alone, such as Fire, Chrome, and the new Lightning. Effects like Animal Fur, Smoke, and Reptile Skin are... Read more

Rollercoaster Tycoon Touch Guide: How to...
| Read more »
Rabbids Crazy Rush Guide: How to unlock...
The Rabbids are back in a new endless running adventure, Rabbids Crazy Rush. It's more ridiculous cartoon craziness as you help the little furballs gather enough fuel (soda) to get to the moon. Sure, it's a silly idea, but everyone has dreams --... | Read more »
Tavern Guardians (Games)
Tavern Guardians 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Tavern Guardians is a Hack-and-Slash action game played in the style of a match-three. You can experience high pace action... | Read more »
Slay your way to glory in idle RPG Endle...
It’s a golden age for idle games on the mobile market, and those addictive little clickers have a new best friend. South Korean developer Ekkorr released Endless Frontier last year, and players have been idling away the hours in the company of its... | Read more »
Tiny Striker: World Football Guide - How...
| Read more »
Good news everyone! Futurama: Worlds of...
Futurama is finding a new home on mobile in TinyCo and Fox Interactive's new game, Futurama: Worlds of Tomorrow. They're really doing it up, bringing on board Futurama creator Matt Groening along with the original cast and writers. TinyCo wants... | Read more »
MUL.MASH.TAB.BA.GAL.GAL (Games)
MUL.MASH.TAB.BA.GAL.GAL 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ENDLESS UPGRADES. CONSTANT DANGER. ANCIENT WISDOM. BOUNCY BALLS. Launch Sale, 40% OFF for a very limited time!!! MUL.... | Read more »
Dungeon Rushers (Games)
Dungeon Rushers 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dungeon Rushers is a 2D tactical RPG combining dungeon crawler’s gameplay and turn based fights. Manage your team, loot dusty... | Read more »
Blasty Bubs is a colorful Pinball and Br...
QuickByte Games has another arcade treat in the works -- this time it's a mishmash of brick breaking and Pinball mechanics. It's called Blasty Bubs, and it's a top down brickbreaker that has you slinging balls around a board. [Read more] | Read more »
Corsola and Heracross are the new region...
Generation 2 finally launched in Pokémon GO, unleashing a brand new batch of Pokémon into the wild. Even before the update went live people were speculating on how to catch elusive Pokémon like the legendary "dogs", Unknown, and whether or not... | Read more »

Price Scanner via MacPrices.net

15-inch Touch Bar MacBook Pros on sale for up...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
12-inch Retina MacBooks on sale for $1150, $1...
B&H has 12″ 1.1GHz Retina MacBooks on sale for $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1149 $150 off MSRP - 12″ 1.1GHz... Read more
Apple restocks refurbished 11-inch MacBook Ai...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models recently discontinued by Apple), available for up to $170 off original MSRP. An Apple one-year warranty is included with each... Read more
Apple Park Opens to Employees in April With T...
Apple has announced that Apple Park, the company’s new 175-acre campus, will be ready for employees to begin occupying in April. The process of moving more than 12,000 people will take over six... Read more
Manhattan Neighbors for Safer Telecommunicati...
A new education and advocacy group focused on cell phone and wireless risks, Manhattan Neighbors for Safer Telecommunications, launched today at http://www.ManhattanNeighbors.org. Manhattan... Read more
Portable Dual DisplayPort Monitor Dock Enable...
IOGEAR has announced the launch of its USB-C Dual DisplayPort Monitor Portable Dock (GUC3CMST). The dock enables users to easily connect two DisplayPort monitors to a USB-C or Thunderbolt 3 laptop to... Read more
13-inch 2.7GHz Retina MacBook Pro on sale for...
Amazon.com has restocked the 13″ 2.7GHz/128GB Retina MacBook Pro (MF839LL/A) for $200 off MSRP including free shipping: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1099 $200 off MSRP This model tends to... Read more
Apple’s New iPad Ads Don’t Address Pro Users’...
Apple launched a new tranche of iPad Pro TV ads last week addressing actual queries and challenges from the Twitterverse, albeit using actors for the visuals. That’s great. As an iPad fan and heavy... Read more
Free Verbum Catholic Bible Study App For iOS
The Verbum mobile app runs on Logos’ powerful Bible software and is an advanced resource for mobile Catholic study. The Verbum app surrounds the Bible with the Tradition. Verbum comes with 15 free... Read more
27-inch Apple iMacs on sale for up to $200 of...
B&H Photo has 27″ Apple iMacs on sale for up to $200 off MSRP, each including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2099.99 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $... Read more

Jobs Board

*Apple* Retail - Multiple Positions- Chicago...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Manager *Apple* Systems Administration - Pu...
Req ID 3315BR Position Title Manager, Apple Systems Administration Job Description The Manager of Apple Systems Administration oversees the administration and Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Manager *Apple* Systems Administration - Pu...
Req ID 3315BR Position Title Manager, Apple Systems Administration Job Description The Manager of Apple Systems Administration oversees the administration and Read more
*Apple* Retail - Multiple Positions - Apple,...
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.