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)
PtrtextPtr;
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],
 gDistanceFrac[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[] =
 {0,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3,
  4,4,4,4,4,4,4,4,4,
  5,5,5,5,5,5,5,5,5,5,5};
//precalculated square root - fractional part
//in 1/0x20000000 of a whole unit
long  qSquTableFrac[]=
 {0,0,222379212,393016784,0,126738030,
 241317968,346685095,444758425,0,
 87122155,169986639,249162657,
 325102865,398174277,468679365,0,
 66091829,130266726,192682403,
 253476060,312767944,370664138,
 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;
 BooleanlastCity;
 long   offset;
 
 if (fracPathLength > fracBase)  {
 //the fractional value variable has
 //exceeded the value of one whole
 //unit
 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)))
   return;
 
 //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
 DoPath(i,
  InttPathLength+gDistanceInt[offset],
  fracPathLength+gDistanceFrac[offset]);
 } //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,
 *LPntI2,*LPntF2;
 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;
 *LPntF2++;
 LPntF1 += 32;
 } else {
 //calculate horizontal and vertical
 //distance betwean city ‘i’ and ‘j’
 deltax = citiesPtr[i].h-
 citiesPtr[j].h;
 deltay = citiesPtr[i].v-
 citiesPtr[j].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) + 
 (long)(deltay*deltay));
 else
 dist = ((long)(deltax*deltax) + 
 (long)deltay*deltay);
 else
 if (-255< deltay && deltay<256)
 dist = ((long)deltax*deltax + 
 (long)(deltay*deltay));
 else
 dist = ((long)deltax*deltax + 
 (long)deltay*deltay);

 //do squareRoot
 if (dist <= 25) {
 //use sqrt lookup tables for
 //0 to 25
 *LPntI2++  = *LPntl1 =
 qSquTableInt[dist];
  LPntl1 += 32;
 *LPntF2++  = *LPntF1 =
 qSquTableFrac[dist];
  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,
 optimalPathPtr)
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.
 InitDistances(numCities,citiesPtr);
 
 //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
 DoPath(startCityIndex,0,0);  
 
 //put the best path into the form
 //desired for ‘optimalPath’
 j=startCityIndex;
 for(i=0; i<numCities; i++) {
 optimalPathPtr[i] = citiesPtr[j];
 j = gOptPath[j];
 }
}

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

 
AAPL
$97.67
Apple Inc.
+0.64
MSFT
$44.50
Microsoft Corpora
+0.10
GOOG
$589.02
Google Inc.
-4.33

MacTech Search:
Community Search:

Software Updates via MacUpdate

TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Autopano Giga 3.6 - Stitch multiple imag...
Autopano Giga allows you to stitch 2, 20, or 2,000 images. Version 3.0 integrates impressive new features that will definitely make you adopt Autopano Pro or Autopano Giga: Choose between 9... Read more
Airfoil 4.8.7 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Microsoft Remote Desktop 8.0.8 - Connect...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
xACT 2.30 - Audio compression toolkit. (...
xACT stands for X Aaudio Compression Toolkit, an application that encodes and decodes FLAC, SHN, Monkey’s Audio, TTA, Wavpack, and Apple Lossless files. It also can encode these formats to MP3, AAC... Read more
Firefox 31.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals... Read more
Little Snitch 3.3.3 - Alerts you to outg...
Little Snitch gives you control over your private outgoing data. Track background activityAs soon as your computer connects to the Internet, applications often have permission to send any... Read more
Thunderbird 31.0 - Email client from Moz...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more

Latest Forum Discussions

See All

Reddme for iPhone - The Reddit Client (...
Reddme for iPhone - The Reddit Client 1.0 Device: iOS iPhone Category: News Price: $.99, Version: 1.0 (iTunes) Description: Reddme for iPhone is an iOS 7-optimized Reddit client that offers a refreshing new way to experience Reddit... | Read more »
Jacob Jones and the Bigfoot Mystery : Ep...
Jacob Jones and the Bigfoot Mystery : Episode 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Jacob Jones is back in Episode 2 of one of Apples 'Best of 2013' games and an App Store... | Read more »
New Trailer For Outcast Odyssey, A New K...
New Trailer For Outcast Odyssey, A New Kind of Card Battler Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Out this Fall is a new kind of card battle game: Outcast Odyssey. | Read more »
Garfield: Survival of the Fattest Coming...
Garfield: Survival of the Fattest Coming to iOS this Fall Posted by Jennifer Allen on July 25th, 2014 [ permalink ] Who loves lasagna? Me. Also everyone’s favorite grumpy fat cat, Garfield. | Read more »
Happy Flock Review
Happy Flock Review By Andrew Fisher on July 25th, 2014 Our Rating: :: HERD IT ALL BEFOREUniversal App - Designed for iPhone and iPad Underneath the gloss of Happy Flock’s visuals is a game of very little substance. It’s cute, but... | Read more »
Square Register Updates Adds Offline Pay...
Square Register Updates Adds Offline Payments Posted by Ellis Spice on July 25th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Looking For Group – Hearthstone’s Curse...
For the first time since its release (which has thankfully been a much shorter window for iPad players than their PC counterparts), Blizzard’s wildly successful Hearthstone: Heroes of Warcraft CCG is sporting some brand new content: the single... | Read more »
Poptile Review
Poptile Review By Jennifer Allen on July 25th, 2014 Our Rating: :: SIMPLY FUNUniversal App - Designed for iPhone and iPad Simple yet a little bit glorious, Poptile is a satisfying entertaining puzzle game with oodles of the ‘one... | Read more »
Modern Combat 5: Blackout Review
Modern Combat 5: Blackout Review By Brittany Vincent on July 25th, 2014 Our Rating: :: LESS QQ, MORE PEW PEWUniversal App - Designed for iPhone and iPad The fifth entry into the blockbuster Modern Combat series is what mobile... | Read more »
Watch and Share Mobile Gameplay Videos W...
Watch and Share Mobile Gameplay Videos With Kamcord Posted by Jennifer Allen on July 25th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »

Price Scanner via MacPrices.net

Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more
iMacs on sale for $150 off MSRP, $250 off for...
Best Buy has iMacs on sale for up to $160 off MSRP for a limited time. Choose free home shipping or free instant local store pickup (if available). Prices are valid for online orders only, in-store... Read more
Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more
Save on 5th generation refurbished iPod touch...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
What Should Apple’s Next MacBook Priority Be;...
Stabley Times’ Phil Moore says that after expanding its iMac lineup with a new low end model, Apple’s next Mac hardware decision will be how it wants to approach expanding its MacBook lineup as well... Read more
ArtRage For iPhone Painting App Free During C...
ArtRage for iPhone is currently being offered for free (regularly $1.99) during Comic-Con San Diego #SDCC, July 24-27, in celebration of the upcoming ArtRage 4.5 and other 64-bit versions of the... Read more
With The Apple/IBM Alliance, Is The iPad Now...
Almost since the iPad was rolled out in 2010, and especially after Apple made a 128 GB storage configuration available in 2012, there’s been debate over whether the iPad is a serious tool for... Read more

Jobs Board

WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.