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.

 
AAPL
$104.83
Apple Inc.
+1.84
MSFT
$45.02
Microsoft Corpora
+0.64
GOOG
$543.98
Google Inc.
+11.27

MacTech Search:
Community Search:

Software Updates via MacUpdate

Delicious Library 3.3.2 - Import, browse...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more
Live Interior 3D Pro 2.9.6 - Powerful an...
Live Interior 3D Pro is a powerful yet very intuitive interior designing application. View Video Tutorials It has every feature of Live Interior 3D Standard, plus some exclusive ones: Create multi... Read more
The Hit List 1.1.7 - Advanced reminder a...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
jAlbum Pro 12.2.4 - Organize your digita...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more
jAlbum 12.2.4 - Create custom photo gall...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results Simply drag and drop photos into groups, choose a design... Read more
ExpanDrive 4.1.7 - Access remote files o...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
OmniOutliner Pro 4.1.3 - Pro version of...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It'... Read more
Evernote 5.6.2 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
OmniOutliner 4.1.3 - Organize your ideas...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more

Latest Forum Discussions

See All

A Few Days Left (Games)
A Few Days Left 1.01 Device: iOS Universal Category: Games Price: $3.99, Version: 1.01 (iTunes) Description: Screenshots are in compliance to App Store's 4+ age rating! Please see App Preview for real game play! **Important: Make... | Read more »
Toca Boo (Education)
Toca Boo 1.0.2 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0.2 (iTunes) Description: BOO! Did I scare you!? My name is Bonnie and my family loves to spook! Do you want to scare them back? Follow me and I'll... | Read more »
Intuon (Games)
Intuon 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Join the battle with your intuition in a new hardcore game Intuon! How well do you trust your intuition? Can you find a needle in a... | Read more »
Ravenous Rampage (Games)
Ravenous Rampage 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: | Read more »
Partia 2 (Games)
Partia 2 1.0.1 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0.1 (iTunes) Description: Partia 2 is a SRPG (Strategy Role-playing) video game inspired by Fire Emblem and Tear Ring Saga series. In a high fantasy... | Read more »
Puzzle to the Center of the Earth Review
Puzzle to the Center of the Earth Review By Campbell Bird on October 23rd, 2014 Our Rating: :: SPELUNKING PUZZLESUniversal App - Designed for iPhone and iPad Do some puzzles to make some platforms in this smart and fun free-to-play... | Read more »
Sleep Attack TD Review
Sleep Attack TD Review By Jennifer Allen on October 23rd, 2014 Our Rating: :: A TRUE TWISTUniversal App - Designed for iPhone and iPad Sleep Attack TD is a tower defense game with a difference – you can rotate the layout – and it’s... | Read more »
Mecanic (Education)
Mecanic 1.0 Device: iOS Universal Category: Education Price: $1.99, Version: 1.0 (iTunes) Description: Plates, screws, wheels ... Everything you need to achieve whatever you want... MECHANICWith 'MECANIC' kids will have fun... | Read more »
Earn Your Master Camper Badge in Camp Po...
Earn Your Master Camper Badge in Camp Pokemon Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Garruk Gets His Revenge in a New Magic 2...
Garruk Gets His Revenge in a New Magic 2015 Expansion, Coming This November Posted by Jessica Fisher on October 23rd, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $949,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $949.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $150 off MSRP. Price is... Read more
Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more
Save with Best Buy’s College Student Deals
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through November 1st. Anyone with a valid .EDU email address can take advantage... Read more
iPad Air 2 & iPad mini 3 Best Tablets Yet...
The new iPads turned out to be pretty much everything I’d been hoping for and more than I’d expected.”More” particularly in terms of a drinking-from-a-firehose choice of models and configurations,... Read more
Drafts 4 Reinvents iOS Productivity App
N Richland Hills, Texas based Agile Tortoise has announced the release of Drafts 4 for iPhone and iPad. Drafts is a quick capture note taking app with flexible output actions. Drafts 4 scales from... Read more
AT&T accepting preorders for new iPads fo...
AT&T Wireless is accepting preorders for the new iPad Air 2 and iPad mini 3, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB... Read more
Apple offering refurbished Mac Pros for up to...
The Apple Store is offering Apple Certified Refurbished 2013 Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more

Jobs Board

*Apple* Solutions Consultant - Apple Inc. (U...
…important role that the ASC serves is that of providing an excellent Apple Customer Experience. Responsibilities include: * Promoting Apple products and solutions Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, 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
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
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.