TweetFollow Us on Twitter

Mar 93 Challenge
Volume Number:9
Issue Number:3
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.

Count Unique Words

Most word processors these days have a Count Words command. The quality in terms of accuracy and speed of these commands varies quite a bit. I tested three leading word processors with a document containing 124,829 characters and got three different answers ranging from 18446 words to 18886 words and times ranging from 4 seconds to 11 seconds. I’m not sure what the correct answer was for that document; it depends on how you define what a word is.

For purposes of this month’s challenge, a word is defined as an unbroken set of one or more letters. The input text will only contain upper and lower case letters a to z, spaces, carriage returns, periods and commas (for a total of 56 possible byte values). No digits, hyphens, tabs, other punctuation, etc. Since counting words using this simplified definition is rather trivial, you’re going to count the number of unique words instead.

The prototype of the function you write is:

unsigned short CountUniqueWords(textPtr, byteCount)
unsigned short byteCount;

Your function should return the number of unique words (case insensitive) in the input text. The maximum word length for individual words in the input text is 255 characters.

This is my 7th programmer’s challenge that I’ve posed to MacTech readers. I have received approximately very little feedback as to what you think of these challenges. Are they too easy, too hard, too uninteresting, or what? Do you want hard core numerical analysis puzzles (like write a fast sqrt function) or do you want Mac-specific problems (like write a fast TileAndStackWindows function) or are things okay as they are? If you have any ideas for future challenges, please send them in (credit will be given in this column if I use one of your ideas). Thanks.

Two Months Ago Winner

The winner of the “Travelling Salesman” challenge is Ronald Nepsund (Northridge, CA) whose solution was the only one of the five I received which gave correct results. The time intensive part of solutions to this class of problems is the distance between two points calculation, which involves a square root. Ronald uses a precomputed sqrt table for values 0 to 25 to eliminate much of this time.

A couple of people chose the algorithm of “find the closest city to where we currently are and move to that city; repeat until all cities have been visited” which is not correct. An example set of input data that broke everyone but Ronald’s solution is: numCities = 8, startCityIndex = 5, *citiesPtr = {1,1}, {2,1}, {3,1}, {2,2}, {1,3}, {2,3}, {3,3}, {2,4}. If you draw it and work it out by hand (through trial and error) you can see that the minimum path distance is 8.66. There is more than one correct ordering for the optimal path but all of the optimal paths will have that same length.

Here is Ronald’s winning solution to the January Challenge:

// Travelling Salesman 
// by Ronald M. Nepsund

#include <math.h>

#define fracBase 0x20000000

//There are two 32 by 20 arrays of longs
//which together give the distance betwean
//any two cities.
//Instead of using Array[i,j] to access
//the array Array[(i<<5)+j] is used
//and two longs are needed to accurately
//measure the distance betwean cities
//so two arrays of longs are used.
//gDistanceFrac is used to hold the
//fractional part of distance in 1/0x20000000
//of a unit.
long  gDistanceInt[640],
//these are used to represent a path betwean
//the cities.
Byte  gNextCity[20],gOptPath[20];
//how long is the currently selected best
//path so far.
long  gBestPathLength,gFracBestPathLength;

unsignedshort  gNumCities;
unsignedshort  gStartCityIndex;

//precalculated square root for zero to 25
long  qSquTableInt[] =
//precalculated square root - fractional part
//in 1/0x20000000 of a whole unit
long  qSquTableFrac[]=
 427258795,482635936,0 };

void DoPath(short cityIndex, long InttPathLength,
 long fracPathLength);

//The recursive routien that actually finds
//the shortest path.

void  DoPath(registershort cityIndex,
 long InttPathLength,
 long fracPathLength)
 register short  i;
 long   offset;
 if (fracPathLength > fracBase)  {
 //the fractional value variable has
 //exceeded the value of one whole
 InttPathLength += 1;
 fracPathLength -= fracBase;
 //Has the path has become longer than the
 //shortest path we have already found?
 if (InttPathLength > gBestPathLength ||
 ((InttPathLength == gBestPathLength) &&
  (fracPathLength >= gFracBestPathLength)))
 //lastCity is used to tell if all the
 //cities have been visited
 lastCity = TRUE;
 //for each city
 for(i = 0; i<gNumCities; i++)
 //if not to same city or already
 //visited city
 if ( i != cityIndex &&
  gNextCity[i] == 0xFF) {
 //not at the end of the path
 lastCity = FALSE;
 //path from city ‘cityIndex’ to ‘i’
 gNextCity[cityIndex] = i;
 //offset into distance arrays
 offset = (cityIndex << 5) + i;
 //go to next city adding the
 //distance to that city to the
 //path length
 } //end if and for
 // if this is the last city in the chain and
 // is a shorter path than the previous best
 if ((lastCity) &&
 ((InttPathLength < gBestPathLength) ||
  ((InttPathLength == gBestPathLength) &&
   (fracPathLength < gFracBestPathLength))
   ) ) {
 // make this the current best path
 register long *LPnt1,*LPnt2;
 //this is the current shortest path
 //length now
 gBestPathLength = InttPathLength;
 gFracBestPathLength = fracPathLength;
 //copy path to ‘optPath’
 LPnt1 = (long *)&gNextCity;
 LPnt2 = (long *)&gOptPath;
 for (i= ((3+gNumCities) >> 2); i>0; i-)
 *LPnt2++ = *LPnt1++;
 } else 
 //this city is no longer connected to
 //the next city
 gNextCity[cityIndex] = 0xFF;

void InitDistances(unsigned short numCities
 Point *citiesPtr);

//initialize two arrays which will give the
//distance betwean any two cities.
void InitDistances(
 unsigned short numCities,
 Point  *citiesPtr)
 short  i,j,offset;
 register long *LPntl1,*LPntF1,
 long   dist;
 short  deltax,deltay;
 double X;
//The distance from city i to j is the same
//as from city j to i.
//Use pointers into the arrays
//We will add a constant to the pointers to
//step through the array
//instead of doing a multiplication to find
//the wanted entries in the array

 //how far is it betwean any two cities
 for (i=0; i<numCities; i++){
 LPntl1 = gDistanceInt  + i;
 LPntF1 = gDistanceFrac + i;
 offset = i << 5;
 LPntI2 = gDistanceInt  + offset;
 LPntF2 = gDistanceFrac + offset;
 for (j=0; j<=i; j++)
 if (i==j){
 //both pointers are pointing
 //to the same locations in the array
 //distance to the same city is zero
 *LPntI2++ = 0;
 *LPntl1 = 0;  LPntl1 += 32;
 LPntF1 += 32;
 } else {
 //calculate horizontal and vertical
 //distance betwean city ‘i’ and ‘j’
 deltax = citiesPtr[i].h-
 deltay = citiesPtr[i].v-
 //The distance betwean the cities is
 // squareRoot( deltax*deltax +
 // deltay*deltay)
 //Where you can, do multiplications
 //using shorts instead of long’s -
 //They are faster.
 if (-255< deltax && deltax<256)
 if (-255< deltay && deltay<256)
 dist = ((long)(deltax*deltax) + 
 dist = ((long)(deltax*deltax) + 
 if (-255< deltay && deltay<256)
 dist = ((long)deltax*deltax + 
 dist = ((long)deltax*deltax + 

 //do squareRoot
 if (dist <= 25) {
 //use sqrt lookup tables for
 //0 to 25
 *LPntI2++  = *LPntl1 =
  LPntl1 += 32;
 *LPntF2++  = *LPntF1 =
  LPntF1 += 32;
 } else {
        X = sqrt(dist);
 //gDistanceInt[(i<<5) + j] = X;
 //gDistanceInt[(j<<5) + i] = X;
 //integer part of distance
 // between points
 dist = X;
 *LPntl1 = *LPntI2++  = dist;
 LPntl1 += 32;
 //gDistanceFrac[i<<5 + j] =
 // (X - dist) * $20000000;
 //gDistanceFrac[j<<5 + i] =
 // (X - dist) * $20000000;
 // fractional part
 dist = (X - dist) * fracBase;
 *LPntF2++  = *LPntF1 = dist;
 LPntF1 += 32;

void OptimalPath(unsigned short numCities
 unsigned short startCityIndex,
 Point *citiesPtr,Point *optimalPathPtr);

void OptimalPath(numCities,startCityIndex,citiesPtr,
unsigned short numCities;
unsigned short startCityIndex;
Point *citiesPtr;
Point *optimalPathPtr;
 register short  i,j;
 long   time,index;
 double X;
 //generates the tables for the distances
 //betwean any two cities.
 //This routien takes up most of the time.
 //OxFF means that there is no path from
 //this city to another
 for (i=0; i<numCities; i++)
 //no paths betwean cities
 gNextCity[i] = 0xFF;
 gNumCities = numCities;
 gStartCityIndex = startCityIndex;
 //any path done by DoPath will be shorter
 //than this
 gBestPathLength = 0x7FFFFFFF;
 gFracBestPathLength = 0;

 //find the best path
 //put the best path into the form
 //desired for ‘optimalPath’
 for(i=0; i<numCities; i++) {
 optimalPathPtr[i] = citiesPtr[j];
 j = gOptPath[j];


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. 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:, 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

Between 2 Taps - Tap for Tap interview M...
Hello, and welcome back to Between 2 Taps, Tap for Tap’s Indie Dev interview series. [Read more] | Read more »
Facility 47 (Games)
Facility 47 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: You wake up alone and freezing in an icy cell. You try the cell door but it’s locked, it seems that you are stuck with no... | Read more »
The best Photoshop alternative on iPad
Instagram and Lightroom are great and all, but sometimes people need to get extra creative with their image editing.Like, Photoshop creative. If you're one of these people, take a look at our pick for the best mobile Photoshop experience on iPad... | Read more »
The Walking Dead: No Man’s Land guide -...
A new update for The Walking Dead: No Man’s Land was released last week, making it the perfect time for you to head back to your base and take out some walkers. Here’s the lowdown on what’s new to the game, and how to take advantage. [Read more] | Read more »
Goat Rider guide - Tips and tricks to st...
We've all been there. One second, we're riding high on a crazed goat, and the next, we've been tossed off it like someone who's no good at goat ridin'. [Read more] | Read more »
Real Boxing 2 CREED: How to become a gre...
Just in time for Rocky fans who can’t wait to see CREED, the latest movie, we have the official tie-in game,Real Boxing 2 CREED. It builds on the success of its predecessor and there’s lots to take in so we at 148apps thought we’d run you through... | Read more »
CoinOp Heroes 2 guide - How to build an...
CoinOp Heroes 2 justlaunched and, like all clickers, it's dangerously addictive stuff. You have to furiously tap your screen to defeat wave after wave of foes and earn an insane amount of cash to spend on character upgrades and an army of minions... | Read more »
Dr. Panda Firefighters (Education)
Dr. Panda Firefighters 1.0.1 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0.1 (iTunes) Description: FIGHT FIRES AND SAVE THE DAY!Work together with Dr. Panda and his firefighting team to rescue his trapped... | Read more »
Puddle + (Games)
Puddle + 1.0 Device: iOS iPhone Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Puddle is back in a new "+" edition featuring enhanced graphics, new videos and Apple TV support ! No IAP and No Ads. Dive into Puddle... | Read more »
Football Manager Mobile 2016 (Games)
Football Manager Mobile 2016 7.0.0 Device: iOS Universal Category: Games Price: $8.99, Version: 7.0.0 (iTunes) Description: Football Manager Mobile 2016 is designed to be played on the move and is the quickest way to manage your... | Read more »

Price Scanner via

Adorama Black Friday deals: Up to $400 off Ma...
Adorama has released their Black Friday deals for 2015. Save up to $400 on MacBook Pros, $200 on MacBooks and MacBook Airs, and $270 on iMacs. Use code RYBFDEAL during checkout to see these prices.... Read more
B&H Photo Deals: $200 off 12-inch 1.2GHz...
In addition to the B&H Photo Black Friday week sales we posted yesterday, B&H has lowered their price on two products to $200 off MSRP: - 12″ 1.2GHz Gray Retina MacBook: $1399 save $200 - 13... Read more
Best Buy Early Access: Today only, Up to $125...
Best Buy has iPad Air 2s on sale for up to $125 off MSRP and Apple Watch models on sale on their online store for up to $100 off MSRP with special codes through midnight CT tonight. Choose free... Read more
UPPERCASE DESIGNS Premium Ultra Thin Keyboard...
UPPERCASE Designs today announced its new Premium Ultra Thin Keyboard Protector and its Palm Rest Protector Set for the 12-inch MacBook. The accessories provide durable protection for the 12-inch... Read more
Al Jazeera Launches New iOS And Android Mobil...
Doha, Qatar based Al Jazeera has launched new mobile and tablet apps on the iOS and Android systems bringing the latest Al Jazeera news and programmes live together with on-demand personalisation.... Read more
B&H Photo Holiday Sale: Up to $250 off Ma...
B&H Photo has all new Macs on sale for up to $500 off MSRP as part of their Holiday sale including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799 $200 off - 15″ 2.... Read more
Free Aura ‘Ultimate’ Mac App For Gmail Update...
Miami, Florida based Crosscoded has announced Aura 1.2.0, an update to the Mac app for Gmail. Aura mixes the power of a native client with the flexibility of the Gmail web app with support for up to... Read more
Apple Will Edge Closer to Samsung in Smartpho...
Total smartphone shipments for 2015 are projected to decline by 9.7% to 1.286 billion units, according to the latest report from global market research firm TrendForce. Though Chinese vendors have... Read more
Sidefari – Split Screen Multitasking In Safar...
Francisco Cantu’s Sidefari is a simple web browser designed to act as a companion to Safari on the iPad. With multitasking in iOS 9, Sidefari uses the new Safari View Controller to show an extra... Read more
12-inch MacBooks in stock for up to $120 off,...
Adorama has 12″ Retina MacBooks in stock for up to $120 off MSRP including free shipping plus NY & NJ sales tax only. For a limited time, Adorama will include a free Apple USB-C to USB Adapter,... Read more

Jobs Board

*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
Merchant Operations Manager: *Apple* Pay -...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more than Read more
*Apple* Pay QA Manager - Apple Inc. (United...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more than Read more
Sr Software Engineer *Apple* Pay - Apple In...
Changing the world is all in a day's work at Apple . If you love innovation, here's your chance to make a career of it. You'll work hard. But the job comes with more than Read more
Hardware Systems Architect - *Apple* Watch...
# Hardware Systems Architect - Apple Watch Job Number: 38449977 Santa Clara Valley, Califo ia, United States Posted: Apr. 16, 2015 Weekly Hours: **Job Summary** The Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.