TweetFollow Us on Twitter

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

REPLACE ALL

Have you ever done a Replace All operation in some program and thought that it was taking more time than it should to do the job? Well, this month you’ll have your chance to show those text-based applications how to do it right. The goal is to write a case-sensitive find and replace function.

The prototype of the function you write is:

long ReplaceAll(sourceHndl, 
 replaceHndl, targetHndl)
Handle  sourceHndl;
Handle  replaceHndl;
Handle  targetHndl;

The sourceHndl contains the text to search for. The replaceHndl contains the text to replace the source text with, once found, and the targetHndl contains the text to look in. You should replace each occurance of the sourceHndl text in targetHndl with the replaceHndl text. You can get the sizes of each piece by using GetHandleSize. And you can resize targetHndl as necessary with normal Mac memory manager calls.

For example, suppose targetHndl contained this text:

Perhaps this modern sorcery especially attracts those who believe in 
happy endings and fairy godmothers.

with this sourceHndl text:

fairy godmothers

and this replaceHndl text:

pink elephants

After a call to ReplaceAll targetHndl would contain:

Perhaps this modern sorcery especially attracts those who believe in 
happy endings and pink elephants.

The return value from ReplaceAll is the actual number of substitutions made (1 in this example). You must find an exact match before doing a replacement (i.e. ‘cat’ != ‘Cat’). The max size of each Handle on entry to ReplaceAll will be 255 bytes for sourceHndl and replaceHndl; and 65535 bytes for targetHndl. There is no max output size for targetHndl. You should grow or shrink targetHndl as necessary so that it’s exactly the correct size when ReplaceAll returns. If you run out of memory while trying to grow targetHndl then return -1 instead of the number of substitutions. The text you will be searching through will be mixed case English text containing punctuation.

TWO MONTHS AGO WINNER

Congratulations to Bob Boonstra (Westford, MA) for his fast and small entry in the Where In The World challenge. Tying Bob for speed but not for code size is Jeff Mallett (Hickory, NC). Jeff’s solution was a little faster than Bob’s for some cases and a little slower than Bob’s for others. I couldn’t find a pattern so I went to the second criteria, code size, to pick the winner.

Here are the sizes and times for the 16 entries that yielded correct results:

Name bytes ticks

Bob Boonstra 358 55

Jeff Mallett 728 55

Stepan Riha 514 78

Jim Bumgardner 454 86

Jeff Tupper 624 94

Russ LaValle 530 101

Jan Bruyndonckx 402 112

David Salmon 638 133

Ted Krovetz 250 136

Patrick Breen 350 137

Ricky Schrieber 286 145

Thomas Studer 488 164

Stuart McIntosh 390 230

Robert Fisher 396 268

David Rand 302 420

Bob Menteer 1224 506

Since the puzzle stated that exact matches would be passed to FindCity 2/3rds of the time it is reasonable to do an exact match search first, before starting off and trying to find the five closest matches. Bob makes this first pass by comparing the first 4 bytes of the target string with the first 4 bytes of each element in the cities array. Only if there is an exact match (which includes the length byte) does he then continue to check the remaining parts of the string (again, 4 bytes at a time through clever typecasting).

Once Bob detects that he doesn’t have an exact match, he calculates a closeness-of-match number for every entry in the cities array. But he eliminates some of the work by first comparing the difference in length bytes between the target string and the current element. If it’s greater than his current largest difference (of the 5 closest he’s keeping track of) then he skips the element completely and moves on to the next. This is a neat trick that takes advantage of the way the closeness-of-match number was defined. I like it.

Here’s Bob’s winning solution:

/* FindCity by Bob Boonstra */
 
#define kMax5
#define kSentinal0x035A5A5A
#define low3Bytes0x00FFFFFF
 
typedef struct distRec {
 short  theDist;
 unsigned short  theIndx;
} distRec;

Boolean FindCity(cityNames, cityToFindNamePtr, 
 closestMatches)
Str255  cityNames[];
Str255  *cityToFindNamePtr;
unsigned short closestMatches[];
{
 distRectheRec[kMax];
 unsigned char   *curCityP, *city2Find;
 unsigned short  curIndx;
 register short  maxDist;
  
 city2Find = *cityToFindNamePtr;
 curCityP = cityNames[0];
 /*
  *Scan for an exact match.
  */
 {
 register long toFind3;

 curIndx = 0;
 toFind3 = *(long *)city2Find & low3Bytes;
 do {
 if ( *(long *)curCityP == *(long *)city2Find ) {
 /*
  *If first 4 characters match, look at the
  *rest in chunks of 4 characters.
  */
 register short charsLeft;
 register unsigned char *s1 = curCityP+4;
 register unsigned char *s2 = city2Find+4;

 if ( (charsLeft = *curCityP-7) >= 0 ) {
 do {
 if ( *(long *)s1 != *(long *)s2 )
 goto nextOne;
 s1 += 4;  s2 += 4;
 } while ( (charsLeft-=4) >= 0 );
 }
 /*
  *If all chunks of 4 characters match, look at the
  *rest individually.
  */
 if (charsLeft+=4) {
 do {
 if (*s1++ != *s2++)
 goto nextOne;
 } while (--charsLeft);
 }
 /*
  *Exact match found.  Return index of match.
  */
 closestMatches[0] = curIndx;
 return(1);
 /*
  *Process the next city. Exit if it is greater in
  *alphabetic order (based on 1st 3 characters,
  *w/o length byte).
  *Sentinal will force exit if necessary.
  */
 nextOne: ;
 }

 ++curIndx;
 curCityP+=sizeof(Str255);

 }  while ( (*(long *)curCityP & low3Bytes) <= toFind3 );
 }
 /*
  *Initialize distance structure for 5 closest matches.
  */
 noMatch:
 {
 register distRec *p = &theRec[0];

 (++p)->theDist = (++p)->theDist = (++p)->theDist =
 (++p)->theDist = (p)->theDist = maxDist = 255;
 }
 /*
  *Loop thru cityNames to find closest matches.
  */
 curCityP=cityNames[0];
 curIndx=0;
 do {
 register short curDist;
 /*
  *Calculate dist between cityToFind and cityName[curIndx].
  */
 {
 register unsigned char *s1,*s2;
 register short lng;

 /*initialize dist to length difference */
 s2 = city2Find;
 lng = *s2++;
 if ((curDist = *(s1=curCityP) - lng) < 0) {
 curDist = -curDist;
 lng = *s1;
 }
 /*
  *Move to next city if distance exceeds the distance
  *of 5 other cities.
  *Increment dist for each nonMatching char.
  *Unroll for a little extra speed.
  */
 ++s1;
 do {
 if (*s1++ != *s2++)
 if (++curDist >= maxDist) goto nextCity;
 if (!(--lng)) break;
 if (*s1++ != *s2++)
 if (++curDist >= maxDist) goto nextCity;
 if (!(--lng)) break;
 if (*s1++ != *s2++)
 if (++curDist >= maxDist) goto nextCity;
 if (!(--lng)) break;
 if (*s1++ != *s2++)
 if (++curDist >= maxDist) goto nextCity;
 } while (--lng);
 }
 /*
  *This city is closer than at least one of the five
  *currently closest cities.  Store the distance and
  *the index in the proper place.
  *distRec[0].theIndx is the closest match, and
  *distRec[0].theDist is the associated distance
  */
 {
 register distRec *q=theRec+kMax-1;

 maxDist=curDist;
 if (curDist >= (q-1)->theDist) goto storeIt;
 *q = *(q-1);
 maxDist = q->theDist;  --q;  /* [3]-->[4] */
 if (curDist >= (q-1)->theDist) goto storeIt;
 *q = *(q-1);  --q;           /* [2]-->[3] */
 if (curDist >= (q-1)->theDist) goto storeIt;
 *q = *(q-1);  --q;           /* [1]-->[2] */
 if (curDist >= (q-1)->theDist) goto storeIt;
 *q = *(q-1);  --q;           /* [0]-->[1] */
 storeIt:
 q->theDist = curDist;
 q->theIndx = curIndx;
 }
 /*
  *Process next city.
  */
 nextCity:
 curCityP+=sizeof(Str255);
 ++curIndx;
 /*
  *Exit when sentinal is found.
  */
 } while (*(long *)curCityP != kSentinal);

 /*
  *Return indices of 5 closest cities.
  */
 {
 register unsigned short *p = closestMatches;
 register unsigned short *q = &theRec[0].theIndx;

 *p++ = *q;  q+=2;
 *p++ = *q;  q+=2;
 *p++ = *q;  q+=2;
 *p++ = *q;  q+=2;
 *p   = *q;
 }
 return(0);
}

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). Only pure C code can be used. Any entries with any assembly in them will be disqualified. 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. All code should be limited to 60 characters wide. This will aid us in dealing with e-mail gateways and page layout.

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, CompuServe: 71552,174 and America Online: MT PRGCHAL. 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

BetterTouchTool 2.07 - Customize Multi-T...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
BetterTouchTool 2.07 - Customize Multi-T...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
PDFpen 8.3.2 - $74.95
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more
DiskCatalogMaker 6.5.20 - Catalog your d...
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
Things 2.8.9 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
PDFpenPro 8.3.2 - $124.95
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Create fillable forms and tables of content... Read more
Things 2.8.9 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
DiskCatalogMaker 6.5.20 - Catalog your d...
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
PDFpenPro 8.3.2 - $124.95
PDFpenPro allows users to edit PDF's easily. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Create fillable forms and tables of content... Read more
PDFpen 8.3.2 - Edit and annotate PDFs wi...
PDFpen allows users to easily edit PDF's. Add text, images and signatures. Fill out PDF forms. Merge or split PDF documents. Reorder and delete pages. Even correct text and edit graphics! Features... Read more

Latest Forum Discussions

See All

Pokémon GO Generation 2 evolution guide
At long last, Niantic Labs finally unleashed the Generation 2 Pokémon into the wild. Pokémon GO trainers are scrambling to grab up this new set of 80 Pokémon. There are some special new tricks required to catch all of these new beasties, though.... | Read more »
The best new games we played this week
It feels as though the New Year got off to a creaking start as far as mobile games go, but that's changed over the past few weeks. The last few days alone have seen the debut of a number of wonderful games, so we thought we'd take the time to... | Read more »
Recruit more scallywags and discover new...
Get ready to show off your sea legs all over again in Oceans & Empires’ new grand update, which aims to make the act of rising to the role of seven seas ruler even more fresh and appealing, thanks to a richness of new content on both iOS and... | Read more »
Mage the Ascension: Refuge (Games)
Mage the Ascension: Refuge 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: The groundbreaking roleplaying game Mage: The Ascension manifests in our turbulent present with Refuge, an... | Read more »
Vampire: Prelude (Games)
Vampire: Prelude 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: The classic roleplaying game Vampire: The Masquerade returns to digital games with a Prelude of things to come. Experience a... | Read more »
Digby Forever Guide: How to dig to the d...
Digby Forever is a sparkling homage to arcade classics, and while you may be tiring of the number of arcade games being thrown at you, this endless digger finds many ways to stand out from the rest of the pack. The game manages to be challenging... | Read more »
The best sales on the App Store this wee...
It's been quite the week in mobile games, but if the latest releases(there were some pretty darn good ones, in case you missed out) aren't really doing the trick, perhaps some of these discounted games will. Many of these premium games had their... | Read more »
Why the new Fire Emblem Heroes update sh...
It’s exciting to see Nintendo delving into the mobile sphere, regardless of whether it’s to give fans another platform to enjoy their fans or simply a sound business venture. Two of the company's announced mobile games have finally come to... | Read more »
New Fire Emblem Heroes update adds new h...
Fire Emblem Heroes received a sizeable update first thing this morning. The update features a batch of fresh content along with a few updates to the game's systems. [Read more] | Read more »
The Deep Paths (Games)
The Deep Paths 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: 25% off launch sale!!! The Deep Paths: Labyrinth Of Andokost is a first-person, dungeon crawling RPG, with traditional grid-based... | Read more »

Price Scanner via MacPrices.net

12-inch 1.1GHz Retina MacBooks on sale for $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
InTouch Health Expands iOS And Windows Produc...
Specialty telehealth enterprise provider InTouch Health has announced an expanded range of FDA Class I listed medical devices and software solutions for ambulatory, non-acute and non-emergent... Read more
iMobie Airs World’s 1st iCloud Manager with M...
iMobie Inc., an Apple-related software company, announced their newly-updated iPhone manager AnyTrans with exclusive feature to sync and manage contents across multiple iCloud accounts. With it,... Read more
New Proactive Apple Support Professional Cert...
Watchman Monitoring has announced Proactive Support Professional Certification at MacTech Pro. Watchman Monitoring is a premier Proactive Support Software as a Service (SaaS) tool for IT... Read more
13-inch 2.7GHz Retina MacBook Pro on sale for...
B&H Photo has the 2015 13″ 2.7GHz/128GB Retina Apple MacBook Pro on sale for $100 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro (MF839LL/A): $... Read more
Back in stock: Apple refurbished 13-inch Reti...
Apple has Certified Refurbished 2015 13″ Retina MacBook Pros available for up to $360 off original MSRP, starting at $1099. An Apple one-year warranty is included with each model, and shipping is... Read more
Apple refurbished Apple TVs available for up...
Apple has Certified Refurbished 32GB and 64GB Apple TVs available for up to $30 off the cost of new models. Apple’s standard one-year warranty is included with each model, and shipping is free: -... Read more
2.6GHz Mac mini on sale for $559, $140 off MS...
Guitar Center has the 2.6GHz Mac mini (MGEN2LL/A) on sale for $559.99 including free shipping. Their price is $140 off MSRP, and it’s the lowest price available for this model. Read more
21-inch Apple iMacs on sale for $100-$150 off...
B&H Photo has 21″ iMacs on sale for up to $150 off MSRP, each including free shipping plus NY sales tax only: - 21″ 3.1GHz iMac 4K: $1349 $150 off MSRP - 21″ 2.8GHz iMac: $1189 $110 off MSRP - 21... Read more
Type Nine Keyboard 2.0 for iOS – World’s Firs...
Copenhagen, Denmark based indie developer Rasmus Porsager has released Type Nine Keyboard 2.0, an update to his keyboard utility for iOS devices. Type Nine Keyboard combines a t9 keypad layout with... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing 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
Lead Senior *Apple* (Mac) Administrator - S...
…but also to protect them. Position Summary: SC3 is actively seeking a Senior Apple (Mac) Administrator that will be responsible for providing Apple Mac 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.