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.


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.


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, 
Str255  cityNames[];
Str255  *cityToFindNamePtr;
unsigned short closestMatches[];
 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;
  *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: ;


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

 (++p)->theDist = (++p)->theDist = (++p)->theDist =
 (++p)->theDist = (p)->theDist = maxDist = 255;
  *Loop thru cityNames to find closest matches.
 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.
 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;

 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] */
 q->theDist = curDist;
 q->theIndx = curIndx;
  *Process next city.
  *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;

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

AirPort Utility 6.3.6 - Set up and manag...
Note: Most recent release available only within OS X 10.11 El Capitan update. Use AirPort Utility to set up and manage your Wi-Fi network and AirPort base stations, including AirPort Express, AirPort... Read more
Quicksilver 1.3.1 - Application launcher...
Quicksilver is a light, fast and free Mac application that gives you the power to control your Mac with keystrokes alone. Quicksilver allows you to find what you need quickly and easily, then act... Read more
Tidy Up (Five Users) 4.1.5 - Find duplic...
Tidy Up is a complete duplicate finder and disk-tidiness utility. With Tidy Up you can search for duplicate files and packages by the owner application, content, type, creator, extension, time... Read more
Mellel 3.4.3 - The word processor of cho...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more
Skype - Voice-over-internet p...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
Bookends 12.6.0 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Access the power of Bookends directly from Mellel, Nisus Writer Pro, or MS Word (... Read more
Apple iBooks Author 2.4 - Create and pub...
Apple iBooks Author helps you create and publish amazing Multi-Touch books for iPad. Now anyone can create stunning iBooks textbooks, cookbooks, history books, picture books, and more for iPad. All... Read more
Web Snapper 3.3.9 - Capture entire Web p...
Web Snapper lets you capture Web pages exactly as they appear in your browser. You can send them to a file as images or vector-based, multi-page PDFs. It captures the whole Web page - eliminating the... Read more
Tunnelblick 3.6beta10 - 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
EtreCheck 2.5.1 - For troubleshooting yo...
EtreCheck is a simple little app to display the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support... Read more

Camel Up (Games)
Camel Up 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Martian: Bring Him Home (Games)
The Martian: Bring Him Home 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Based on the best selling novel and critically acclaimed film, THE MARTIAN tells the story of Astronaut Mark... | Read more »
This Week at 148Apps: September 21-30, 2...
Leap Into Fall With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above... | Read more »
Tweetbot 4 for Twitter (Social Networki...
Tweetbot 4 for Twitter 4.0 Device: iOS Universal Category: Social Networking Price: $4.99, Version: 4.0 (iTunes) Description: *** 50% off for a limited time. *** | Read more »
Mori (Games)
Mori 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Stop, rewind and unwind with Mori. Time is always running, take a moment to take control. Mori is an action puzzle game about infinitely... | Read more »
100 Years' War (Games)
100 Years' War 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Tower in the Sky (Games)
Tower in the Sky 0.0.60 Device: iOS Universal Category: Games Price: $1.99, Version: 0.0.60 (iTunes) Description: | Read more »
hocus. (Games)
hocus. 1.0.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0.0 (iTunes) Description: New, polished, mind-bending, minimal puzzle game with dozens of levels and extra-ordinary design Features:- Beautifully crafted... | Read more »
Mos Speedrun 2 (Games)
Mos Speedrun 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Mos is back, in her biggest and most exciting adventure ever! Wall-jump to victory through 30 mysterious, action packed levels... | Read more »
3D Touch could be a game-changer, but it...
Were you one of the lucky/financially secure enough ones to buy a new iPhone 6s or iPhone 6s Plus over the weekend? Yup, me too (I’m not convinced I was either of those two things, but let’s go with lucky for now), so I thought I’d delve into just... | Read more »

Price Scanner via

Apple refurbished iPad Air 2s available for u...
Apple has Certified Refurbished iPad Air 2s available for up to $140 off the price of new models. Apple’s one-year warranty is included with each model, and shipping is free: - 128GB Wi-Fi iPad Air 2... Read more
Save up to $100 on Mac AppleCare Protection P...
Adorama has 3-Year AppleCare Warranties on sale for up to $100 off MSRP including free shipping plus NY & NJ sales tax only: - Mac Laptops 15″ and Above: $249 $100 off MSRP - Mac Laptops 13″ and... Read more
Updated Mac Price Trackers
We’ve updated our Mac Price Trackers with the latest information on prices, bundles, and availability on systems from Apple’s authorized internet/catalog resellers: - 15″ MacBook Pros - 13″ MacBook... 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
15-inch 2.2GHz Retina MacBook Pro on sale for... has the 15″ 2.2GHz Retina MacBook Pro on sale for $1799 including free shipping. Their price is $200 off MSRP, and it’s the lowest price available for this model (except for Apple’s $1699... Read more
iPhone 6s and 6s Plus Feature Improved Durabi...
Upgraded components in the new iPhone 6s Plus cost $16 more than the components in the earlier iPhone 6 Plus according to a preliminary estimate from IHS Inc. The bill of materials (BOM) for an... Read more
13-inch Retina MacBook Pros on sale for up to...
Adorama has 13″ Retina MacBook Pros on sale for up to $130 off MSRP. Shipping is free, and Adorama charges sales tax for NY & NJ residents only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1199.99 $... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ 2.6GHz/128GB SSD Retina MacBook Pros available $979, $320 off original MSRP. An Apple one-year warranty is included, and shipping is free: - 13″ 2.6GHz/128GB... Read more
iOS 9 Reflections Ten Days In – The ‘Book Mys...
I’ve never been much of an early adopter by philosophy or temperament, although I did buy the iPad Air 2 I’m typing this column on last fall only about a month after Apple unveiled it. However, my... Read more
Apple refurbished Time Capsules available for...
Apple has certified refurbished Time Capsules available for $120 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $179, $120 off - 3TB... Read more

Jobs Board

Senior Payments Security Manager - *Apple*...
**Job Summary** Apple , Inc. is looking for a highly motivated, innovative and hands-on senior payments security manager to join the Apple Pay security team. You will Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Site Security Manager - Apple (Unite...
**Job Summary** The Site Security Manager is a high-profile security position at Apple . The Site Manager is the face of Apple Global Security (GS) and primary point Read more
*Apple* Fulfillment Operations Execution Ana...
**Job Summary** The AMR Apple Fulfillment Operations Team is seeking a talented team player to drive the Apple Online Store (AOS) fulfillment performance to ensure a Read more
*Apple* Distinguished Educator (ADE) Communi...
**Job Summary** Apple is seeking candidates for a new position on the Apple Distinguished Educator (ADE) Program team as ADE Community Support Manager. Join a team Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.