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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniGraffle 7.3 - Create diagrams, flow...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
OmniGraffle Pro 7.3 - Create diagrams, f...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more
DEVONthink Pro 2.9.11 - Knowledge base,...
DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research papers, your life often fills your hard drive in the... Read more
DiskCatalogMaker 6.8.1 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Tunnelblick 3.7.0 - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Adobe Dreamweaver CC 2017 17.0.2.9391 -...
Dreamweaver CC 2017 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2017 allows you to... Read more
Adobe Animate CC 2017 16.2.0 - Advanced...
Animate CC 2017 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2017 (was Flash CC) lets you... Read more
A Better Finder Rename 10.15 - File, pho...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
Creative Kit 1.1 - $149.99
Creative Kit 2016--made exclusively for Mac users--is your ticket to the most amazing images you've ever created. With a variety of powerful tools at your fingertips, you'll not only repair and fine-... Read more
iMazing 2.2.3 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more

Power Rangers: Legacy Wars beginner...
Rita Repulsa is back, but this time she's invading your mobile phone in Power Rangers: Legacy Wars. What looks to be a straightforward beat 'em up is actually a tough-as-nails multiplayer strategy game that requires some deft tactical maneuvering.... | Read more »
Hearthstone celebrates the upcoming Jour...
Hearthstone gets a new expansion, Journey to Un'Goro, in a little over a week, and they'll be welcoming the Year of the Mammoth, the next season, at the same time. There's a lot to be excited about, so Blizzard is celebrating in kind. Players will... | Read more »
4 smart and stylish puzzle games like Ty...
TypeShift launched a little over a week ago, offering some puzzling new challenges for word nerds equipped with an iOS device. Created by Zach Gage, the mind behind Spelltower, TypeShift boasts, like its predecessor, a sleak design and some very... | Read more »
The best deals on the App Store this wee...
Deals, deals, deals. We're all about a good bargain here on 148Apps, and luckily this was another fine week in App Store discounts. There's a big board game sale happening right now, and a few fine indies are still discounted through the weekend.... | Read more »
The best new games we played this week
It's been quite the week, but now that all of that business is out of the way, it's time to hunker down with some of the excellent games that were released over the past few days. There's a fair few to help you relax in your down time or if you're... | Read more »
Orphan Black: The Game (Games)
Orphan Black: The Game 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dive into a dark and twisted puzzle-adventure that retells the pivotal events of Orphan Black. | Read more »
The Elder Scrolls: Legends is now availa...
| Read more »
Ticket to Earth beginner's guide: H...
Robot Circus launched Ticket to Earth as part of the App Store's indie games event last week. If you're not quite digging the space operatics Mass Effect: Andromeda is serving up, you'll be pleased to know that there's a surprising alternative on... | Read more »
Leap to victory in Nexx Studios new plat...
You’re always a hop, skip, and a jump away from a fiery death in Temple Jump, a new platformer-cum-endless runner from Nexx Studio. It’s out now on both iOS and Android if you’re an adventurer seeking treasure in a crumbling, pixel-laden temple. | Read more »
Failbetter Games details changes coming...
Sunless Sea, Failbetter Games' dark and gloomy sea explorer, sets sail for the iPad tomorrow. Ahead of the game's launch, Failbetter took to Twitter to discuss what will be different in the mobile version of the game. Many of the changes make... | Read more »

Price Scanner via MacPrices.net

Is Apple Planning An iPhone Based Modular Doc...
Today’s more powerful and larger-screened smartphones and phablets are becoming the default anchor computing device for more and more users computing devices, but even a five or six inch panel is not... Read more
Razer Launches New Razer Blade Pro World’s Fi...
Razer, the gaming and high performance hardware specialists, have announced the new Razer Blade Pro laptop — the first laptop to be qualified for THX Mobile Certification, an accreditation reserved... Read more
Gro CRM’s Apple Small Business Mac And iOS CR...
Gro Software, developers of the Mac CRM software for small business and enterprise, are included in FinancesOnline 2017 CRM Rising Stars and Great User Experience lists by business software review... Read more
Deal alert! 15-inch and 13-inch MacBook Pros...
B&H Photo has the new 2016 15″ and 13″ Apple MacBook Pros in stock today and on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Save up to $420 on a new MacBook Pro with App...
Apple is offering Certified Refurbished 2016 15″ and 13″ MacBook Pros, including some Touch Bar models, for up to $420 off original MSRP. An Apple one-year warranty is included with each model, and... Read more
12-inch 1.2GHz Retina MacBooks on sale for $1...
B&H has 12″ 1.2GHz Retina MacBooks on sale for up to $200 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.2GHz Space Gray Retina MacBook: $1449 $150 off MSRP - 12″ 1.... Read more
Is A New 10.5-inch iPad Still Coming In April...
There was no sign or mention of a long-rumored and much anticipated 10.5-inch iPad Pro in Apple’s product announcements last week. The exciting iPad news was release of an upgraded iPad Air with a... Read more
T-Mobile’s Premium Device Protection Now Incl...
Good news for T-Mobile customers who love their iPhones and iPads. The “Un-carrier” has become the first national wireless company to give customers AppleCare Services at zero additional cost as part... Read more
FileWave Ensures Support for Latest Apple OS...
FileWave multi-platform device management providers announced support for Apple’s release yesterday of iOS 10.3, macOS Sierra 10.12.4, and tvOS 11.2. FileWave has a history of providing zero-day... Read more
Use Apple’s Education discount to save up to...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: -... Read more

Jobs Board

Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
Desktop Analyst - *Apple* Products - Montef...
…technology to improve patient care. JOB RESPONSIBILITIES: Provide day-to-day support for Apple Hardware and Software in the environment based on the team's support Read more
*Apple* Mobile Master - Best Buy (United Sta...
**493168BR** **Job Title:** Apple Mobile Master **Location Number:** 000827-Denton-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
*Apple* Mobile Master - Best Buy (United Sta...
**492889BR** **Job Title:** Apple Mobile Master **Location Number:** 000886-Norwalk-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.