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

Viber 11.9.1 - Send messages and make fr...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Vallum 3.3.2 - $15.00
Vallum is a little tool that helps you monitor and block apps connections and throttle apps bandwidth. It is able to intercept connections at the application layer, and hold them while you decide... Read more
Microsoft OneNote 16.31 - Free digital n...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
Apple Pages 8.2.1 - Apple's word pr...
Apple Pages is a powerful word processor that gives you everything you need to create documents that look beautiful. And read beautifully. It lets you work seamlessly between Mac and iOS devices, and... Read more
Numbers 6.2.1 - Apple's spreadsheet...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
f.lux 39.9873 - Adjusts the color of you...
f.lux makes the color of your computer's display adapt to the time of day, warm at night and like sunlight during the day. Ever notice how people texting at night have that eerie blue glow? Or wake... Read more
Deeper 2.5.0 - Enable hidden features in...
Deeper is a personalization utility for macOS which allows you to enable and disable the hidden functions of the Finder, Dock, QuickTime, Safari, iTunes, login window, Spotlight, and many of Apple's... Read more
NTFS 15.5.71 - Provides full read and wr...
NTFS breaks down the barriers between Windows and macOS. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS. Write, edit, copy, move, delete files on NTFS... Read more
MTR 5.3.0.0 - The Mac's oldest and...
MTR (was MacTheRipper)--the Mac's oldest and smartest DVD-backup app. MTR - the complete toolbox, not a one-trick, point-and-click extractor. MTR is intended for making fair-use, backup copies of... Read more
Keynote 9.2.1 - Apple's presentatio...
Easily create gorgeous presentations with the all-new Keynote, featuring powerful yet easy-to-use tools and dazzling effects that will make you a very hard act to follow. The Theme Chooser lets you... Read more

Latest Forum Discussions

See All

Black Desert Mobile gets an official rel...
Pearl Abyss has just announced that its highly-anticipated MMO, Black Desert Mobile, will launch globally for iOS and Android on December 11th. [Read more] | Read more »
Another Eden receives new a episode, cha...
Another Eden, WFS' popular RPG, has received another update that brings new story content to the game alongside a few new heroes to discover. [Read more] | Read more »
Overdox guide - Tips and tricks for begi...
Overdox is a clever battle royale that changes things up by adding MOBA mechanics and melee combat to the mix. This new hybrid game can be quite a bit to take in at first, so we’ve put together a list of tips to help you get a leg up on the... | Read more »
Roterra Extreme - Great Escape is a pers...
Roterra Extreme – Great Escape has been described by developers Dig-It Games as a mini-sequel to their acclaimed title Roterra: Flip the Fairytale. It continues that game's tradition of messing with which way is up, tasking you with solving... | Read more »
Hearthstone: Battlegrounds open beta lau...
Remember earlier this year when auto battlers were the latest hotness? We had Auto Chess, DOTA Underlords, Chess Rush, and more all gunning for our attention. They all had their own reasons to play, but, at least from where I'm standing, most... | Read more »
The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »
Arcade classic R-Type Dimensions EX blas...
If you're a long time fan of shmups and have been looking for something to play lately, Tozai Games may have just released an ideal game for you on iOS. R-Type Dimensions EX brings the first R-Type and its sequel to iOS devices. [Read more] | Read more »
Intense VR first-person shooter Colonicl...
Our latest VR obsession is Colonicle, an intense VR FPS, recently released on Oculus and Google Play, courtesy of From Fake Eyes and Goboogie Games. It's a pulse-pounding multiplayer shooter which should appeal to genre fanatics and newcomers alike... | Read more »
PUBG Mobile's incoming update bring...
PUGB Mobile's newest Royale Pass season they're calling Fury of the Wasteland arrives tomorrow and with it comes a fair chunk of new content to the game. We'll be seeing a new map, weapon and even a companion system. [Read more] | Read more »

Price Scanner via MacPrices.net

Weekend Sale: Apple AirPods Pro for $234.98 a...
Abt Electronics has Apple’s new AirPods Pro in stock and on sale today for $234.98 including free shipping and free returns. Their price is $15 off Apple’s MSRP for these AirPods and tie Amazon... Read more
New 2019 16″ MacBook Pros on sale for $100 of...
Apple Authorized Reseller Adorama has new 2019 16″ MacBook Pros on sale today for $100 off Apple’s MSRP, each including free shipping. In addition, Adorama charges sales tax for NY & NJ residents... Read more
Apple Watch Series 3 GPS models on sale for l...
Amazon has Apple Watch Series 3 GPS models on sale starting at only $179. There prices are the lowest we’ve ever seen for these models from any Apple reseller. Choose Amazon as the seller rather than... Read more
iOS Bug In Facebook News Feed Lets Device Ca...
NEWS: 11.15.19- Users of the Facebook social media platform’s mobile app running on iOS devices won’t, like, this piece of news one bit in where a bug in the News Feed gave access to the camera... Read more
16″ MacBook Pros on sale! Preorder at Amazon...
Apple’s new 16″ MacBook Pros were only introduced yesterday, but Amazon is already offering a $100 discount on preorders. Prices for the base 6-Core 16″ MacBook Pros start at $2299: – 2019 16″ 2.6GHz... Read more
Use our exclusive MacBook Price Trackers to f...
Our Apple award-winning MacBook price trackers are the best place to look for the best sales & lowest prices on new and clearance MacBook Airs and MacBook Pros–including Apple’s new 16″ MacBook... Read more
New November Verizon iPhone deal: Get an iPho...
Verizon has the 64GB iPhone Xr on sale for 50% off for a limited time, plus they will include a free $200 prepaid MasterCard and a free Amazon Echo Dot. That reduces their price for the 64GB iPhone... Read more
Apple cuts prices on clearance, refurbished 2...
Apple has clearance 2018 15″ 6-Core Touch Bar MacBook Pros, Certified Refurbished, now available starting at only $1829. Each model features a new outer case, shipping is free, and an Apple 1-year... Read more
Up to $450 price drop on clearance 15″ MacBoo...
B&H Photo has dropped prices Apple’s 2019 15″ 6-Core and 8-Core MacBook Pros by $400-$450 off original MSRP, starting at $1999, with free overnight shipping available to many addresses in the US... Read more
Here’s how to save $200 on Apple’s new 16″ Ma...
Apple has released details of their Education discount associated with the new 2019 16″ 6-Core and 8-Core MacBook Pros. Take $200 off the price of the new 8-Core model (now $2599) and $200 off the 16... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**746887BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 001512-Ankeny-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**746836BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Store NUmber or Department:** 000341-Scranton-Store **Job Description:** **What Read more
QA Manager, *Apple* - CBS Corporation (Unit...
# QA Manager, Apple **REF#:** 35331 **CBS BUSINESS UNIT:** CBS Interactive **JOB TYPE:** Full-Time Staff **JOB SCHEDULE:** **JOB LOCATION:** Burbank, CA **ABOUT Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**744315BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000662-Auburn AL-Store **Job Description:** At Best Read more
Nurse Practitioner - Field Based (San Bernard...
Nurse Practitioner - Field Based (San Bernardino, CA, Apple Valley, Hesperia) **Location:** **United States** **New** **Requisition #:** PS30312 **Post Date:** 4 Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.