TweetFollow Us on Twitter

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

WHERE IN THE WORLD?

This month’s Challenge is a real world problem previously solved without reals by real MacTech reader Allen Stenger (Gardena, CA): You are given a large array of unique city names in alphabetical order ending with a sentinel of ‘ZZZ’ and a single city name to find in this array. You are to return the index of the desired city, or if it doesn’t match exactly, a list of the five closest matches. If there are more than five closest ones, return any five of them. The closeness-of-match algorithm, for purposes of this challenge, is “differing in the fewest positions from the desired name.” Take the longest of the two strings you’re comparing and each time a position doesn’t match (or is beyond the end of the shorter string) add 1 to your difference count; the smallest difference count is considered closest.

The input city list is an array of Str255s (pascal strings) in one big block where there will be, say, 200 to 1000 unique city names (in alphabetical order, all uppercase, with the ‘ZZZ’ sentinel as the last element). The city you are to find is the uppercase string pointed to by cityToFindNamePtr. The prototype of the function you write is:

Boolean FindCity(cityNames,
 cityToFindNamePtr, closestMatches)
Str255  cityNames[];
Str255  *cityToFindNamePtr;
unsigned short   closestMatches[];

If there is an exact match, return TRUE and set closestMatches[0] equal to the zero-based index of the match. If there is not an exact match, return FALSE and set closestMatches[0..4] to the five closest matches (in order of closeness, or, if they are equally close, in any order).

Allen says that this problem came up while working on the American Airlines reservation system, SABRE, a long time ago. He says that his tests then showed that city names were misspelled about 1/3rd of the time due to either poor spelling or typing by the reservation agents (no offense intended). You can use that information in your solution if you like; I will be simulating it with test data (exact matches will occur only 33% of the time I call your routine from my test bench).

TWO MONTHS AGO WINNER

Congratulations to Steve Israelson (Vancouver, B.C.) for winning the “Rotated Bits” challenge. Right on his heels is Andy Scheck (location unknown) with an entry that was half as many bytes but which was just a little too slow in some cases to win. Jeff Mallett (Hickory, NC) deserves praise for his extremely small solution which was also near the top in terms of speed. Because it is so small, it is listed here as well, after Steve’s winning solution.

There were 16 entries to this challenge. Two of them were disqualified immediately because they were in assembly (nice try) and six others were disqualified for giving incorrect results (try testing with a 9x17 bitmap). Many people e-mailed me and asked if they could assume that rowBytes was divisible by four. The answer is: no. However, you could always case out on that case early on in your routine and then call one of two rotate functions based on if (rowBytes % 4 == 0) or not. Just so long as your solution has one entry point you can do whatever you like inside.

Here’s a summary of the eight entries that gave correct results. The bytes column is the code size, test 1 is the ticks to rotate 4000 small bitmaps (20x30 and smaller) and test 2 is the ticks to rotate 400 medium size bitmaps (300x400 pixels, approx). In all cases, the bitmaps were filled with the same random data before rotating:

Name bytes test 1 test 2

Steve Israelson 740 72 638

Andy Scheck 386 75 778

Jeff Mallett 194 91 936

Patrick Breen 668 125 902

Stepan Riha 656 122 1186

Dave Darrah 362 138 1453

Jan Bruyndonckx 490 205 1785

Dominic Mazzoni 244 630 6687

Steve’s winning solution is reasonably commented so I won’t go into detail here describing how it works. I will, however, offer some peephole optimizations to make it even better.

The first thing that the optimized eye notices about his code is that he multiplies, divides and mods by 8. It’s a dangerous assumption to make that the compiler will be smart and substitute shifts and ands where it can. I always prefer to make them explicit. Thus, I would change these lines:

 srcRowX8 = srcRowBytes * 8;
 srcData = const1 + srcX / 8;
 if (remainder = (srcWidth % 8))

to these:

 srcRowX8 = srcRowBytes << 3;
 srcData = const1 + (srcX >> 3);
 if (remainder = (srcWidth & (8 - 1)))

In addition to those, there is one point in his code where he multiplies by 7. He’d be better off by multiplying by 8 (using a shift) and then subtracting one. This:

 src += srcOffset * 7;
is faster as:

 src += srcOffset << 3;
 src -= srcOffset;

After I made these changes and then ran test 2, the time went from 638 ticks to 542 ticks (it reduced the code size by 18 bytes, too).

Here’s Steve’s winning solution, followed by Jeff’s tiny solution:

/*-------------------------------------------------
 Steve Israelson
 Motion Works Corp.
-------------------------------------------------*/
void RotateBitMapClockwise(BitMap *, BitMap *);
void rotateBlock(unsigned long *,unsigned char *,
 long,unsigned char *,long);
void rotateLimitedBlock(unsigned long *,
 unsigned char *, long,unsigned char *,long,
 short);

/*-------------------------------------------------
 Rotate the bitmap from src to dst by +90 degrees.  Make 
 a table for use in the rotate block routine.  Step through 
 the src in 8x8 blocks, starting from the bottom left.  Step 
 through dst in 8x8 blocks,  starting from the top left. 
 Handle the right edge of the bitmap specially to prevent bits 
 from being rotated into memory outside of the destination.

-------------------------------------------------*/
void RotateBitMapClockwise(BitMap *src, BitMap *dst)
{
 unsigned long table[16] =
 {0x00000000, 0x00000001, 0x00000100, 0x00000101,
  0x00010000, 0x00010001, 0x00010100, 0x00010101,
  0x01000000, 0x01000001, 0x01000100, 0x01000101,
  0x01010000, 0x01010001, 0x01010100, 0x01010101};
 /* x,y co-ord of source block */
 register short  srcX, srcY;
 /* row bytes, dereferenced for speed */
 short  srcRowBytes, dstRowBytes;
 /* src rowbytes * 8, for speed */
 short  srcRowX8;
 /* width and height of src */
 short  srcWidth, srcHeight;
 /* pointer to src and dst 8x8 blocks */
 char   *srcData, *dstData;
 /* pointer to bitmaps de-referenced for speed */
 char   *srcAddr, *dstAddr;
 /* last few pixels to do specially */
 short  remainder;
 /* a constant, pre-calculated for speed */
 char   *const1;
 
 /* de-reference some constants */
 srcRowBytes = src->rowBytes;
 dstRowBytes = dst->rowBytes;
 srcAddr = src->baseAddr;
 dstAddr = dst->baseAddr;
 
 /* calculate some values */
 srcWidth = src->bounds.right - src->bounds.left;
 srcHeight = src->bounds.bottom - src->bounds.top;
 
 srcRowX8 = srcRowBytes * 8;
 const1 = srcAddr + (srcHeight - 8) * srcRowBytes;
 
 /* loop through the source doing vertical
  * slices starting at the left */
 for (srcX = 0; srcX < srcWidth - 7; srcX += 8) {
 /* bottom edge */
 srcData = const1 + srcX / 8;
 /* left edge */
 dstData = dstAddr + srcX * dstRowBytes;
 for (srcY = srcHeight - 1; srcY >= 0;
   srcY -= 8 ) {
 rotateBlock(table, (unsigned char *)srcData,
 srcRowBytes, (unsigned char *)dstData,
 dstRowBytes);
 srcData -= srcRowX8; /* next vert block */
 ++dstData; /* next horiz block */
 }
 }
 
 /* handle the last partial row by calling
  * rotateLimitedBlock() */
 if (remainder = (srcWidth % 8)) {
 /* bottom edge */
 srcData = const1 + srcX / 8; 
 /* left edge */
 dstData = dstAddr + srcX * dstRowBytes;
 for (srcY = srcHeight - 1; srcY >= 0;
   srcY -= 8 ) {
 rotateLimitedBlock(table,
 (unsigned char *)srcData, srcRowBytes, 
 (unsigned char *)dstData, dstRowBytes,
 remainder);
 srcData -= srcRowX8;
 ++dstData;
 }
 }
}

/*-------------------------------------------------
 Rotate an 8x8 block of pixels by treating the destination
 block as 2 unsigned longs (64 bits!) and using a lookup 
 table to get a mask for the value of each row in the src 
 block.  The table essentially stretches out the source byte 
 to 8 times its size and then ORs it into the destination 
 64bits.  Since the bits are in the low bit of each byte, 
 the destination has to be shifted one position to the left 
 before each OR operation. The offset values are the 
 difference to rowBytes. If we had a 64bit data type, this
 would be easier.
-------------------------------------------------*/
void rotateBlock(unsigned long *table,
 unsigned char *src, long srcOffset, 
 unsigned char *dst, long dstOffset)
{
 register unsigned long   resultLO, resultHi;
 short  x;
 
 resultLO = resultHi = 0;
 src += srcOffset * 7;
 /* compute the rotated result */
 for (x = 0; x < 8; ++x) {
 resultLO = resultLO << 1;
 resultHi = resultHi << 1;
 resultLO |= table[(*src) >> 4];
 resultHi |= table[(*src) & 0x0F];
 src -= srcOffset;
 }
 
 /* store the rotated result */
 *dst = (resultLO & 0xFF000000) >> 24;
 dst += dstOffset;
 *dst = (resultLO & 0x00FF0000) >> 16;
 dst += dstOffset;
 *dst = (resultLO & 0x0000FF00) >> 8;
 dst += dstOffset;
 *dst = resultLO & 0x000000FF;
 dst += dstOffset;
 *dst = (resultHi & 0xFF000000) >> 24;
 dst += dstOffset;
 *dst = (resultHi & 0x00FF0000) >> 16;
 dst += dstOffset;
 *dst = (resultHi & 0x0000FF00) >> 8;
 dst += dstOffset;
 *dst = resultHi & 0x000000FF;
}

/*-------------------------------------------------
 Same as other rotateBlock, except will do a
 partial block. Useful to prevent the overwriting
 of memory outside the bitmap!
-------------------------------------------------*/
void rotateLimitedBlock(unsigned long *table,
 unsigned char *src, long srcOffset, 
 unsigned char *dst, long dstOffset, short lines)
{
 register unsigned long   resultLO, resultHi;
 short  x;
 
 resultLO = resultHi = 0;
 src += srcOffset * 7;
 for (x = 0; x < 8; ++x) {
 resultLO = resultLO << 1;
 resultHi = resultHi << 1;
 resultLO |= table[(*src) >> 4];
 resultHi |= table[(*src) & 0x0F];
 src -= srcOffset;
 }
 *dst = (resultLO & 0xFF000000) >> 24;
 dst += dstOffset; if (lines == 1) return;
 *dst = (resultLO & 0x00FF0000) >> 16;
 dst += dstOffset; if (lines == 2) return;
 *dst = (resultLO & 0x0000FF00) >> 8;
 dst += dstOffset; if (lines == 3) return;
 *dst = resultLO & 0x000000FF;
 dst += dstOffset; if (lines == 4) return;
 *dst = (resultHi & 0xFF000000) >> 24;
 dst += dstOffset; if (lines == 5) return;
 *dst = (resultHi & 0x00FF0000) >> 16;
 dst += dstOffset; if (lines == 6) return;
 *dst = (resultHi & 0x0000FF00) >> 8;
 dst += dstOffset; if (lines == 7) return;
 *dst = resultHi & 0x000000FF;
}


//*********************************************************
// RotateBitMapClockwise
// By Jeff Mallett
//
// Rotates the significant bits of the srcBitMapPtr 90°
// clockwise and stores the result in dstBitMapPtr.
//*********************************************************

#define kHighShortBit0x8000
#define kBitsPerShort16

// Creates a short from bits in different rows of
// the source bitmap.  Then copies this short into
// the destination bitmap.
#define COPY_TWO_BYTES(stopValue)  \
 data = 0, bit = kHighShortBit;    \
 do {   \
 if (*srcPos & srcBit) data |= bit;\
 srcPos += srcRowShorts;  \
 } while ( (bit >>= 1) != stopValue ); \
 *(dstPos++) = data

void RotateBitMapClockwise(BitMap *srcBitMapPtr,
 BitMap *dstBitMapPtr)
{
 register unsigned short data, *srcPos, bit;
 register int j;
 register unsigned short srcBit, *dstPos, stopBit;
 register int i;
 unsigned short *baseSrcPtr;
 // shorts per row of source
 const int srcRowShorts =
   srcBitMapPtr->rowBytes >> 1;
 const int numSrcRows =
   srcBitMapPtr->bounds.bottom - srcBitMapPtr->bounds.top;
 
 dstPos = (unsigned short *)dstBitMapPtr->baseAddr;
 srcPos = baseSrcPtr =
   (unsigned short *)srcBitMapPtr->baseAddr;
 srcBit = kHighShortBit;
 
 for (i = srcBitMapPtr->bounds.right -
   srcBitMapPtr->bounds.left; i; --i) {
 // Copy one column of source to a row of destination
 for (j = numSrcRows / kBitsPerShort; j; --j) {
 COPY_TWO_BYTES(0);
 }
 if (j = numSrcRows % kBitsPerShort) {
 stopBit = kHighShortBit >> j;
 COPY_TWO_BYTES(stopBit); // Final 2 bytes
 }
 // Prepare to copy next column of source
 if ( !(srcBit >>= 1) ) {
 srcBit = kHighShortBit;
 ++baseSrcPtr;
 }
 srcPos = baseSrcPtr;
 }
}

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

Latest Forum Discussions

See All

Six fantastic ways to spend National Vid...
As if anyone needed an excuse to play games today, I am about to give you one: it is National Video Games Day. A day for us to play games, like we no doubt do every day. Let’s not look a gift horse in the mouth. Instead, feast your eyes on this... | Read more »
Old School RuneScape players turn out in...
The sheer leap in technological advancements in our lifetime has been mind-blowing. We went from Commodore 64s to VR glasses in what feels like a heartbeat, but more importantly, the internet. It can be a dark mess, but it also brought hundreds of... | Read more »
Today's Best Mobile Game Discounts...
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links below... | Read more »
Nintendo and The Pokémon Company's...
Unless you have been living under a rock, you know that Nintendo has been locked in an epic battle with Pocketpair, creator of the obvious Pokémon rip-off Palworld. Nintendo often resorts to legal retaliation at the drop of a hat, but it seems this... | Read more »
Apple exclusive mobile games don’t make...
If you are a gamer on phones, no doubt you have been as distressed as I am on one huge sticking point: exclusivity. For years, Xbox and PlayStation have done battle, and before this was the Sega Genesis and the Nintendo NES. On console, it makes... | Read more »
Regionally exclusive events make no sens...
Last week, over on our sister site AppSpy, I babbled excitedly about the Pokémon GO Safari Days event. You can get nine Eevees with an explorer hat per day. Or, can you? Specifically, you, reader. Do you have the time or funds to possibly fly for... | Read more »
As Jon Bellamy defends his choice to can...
Back in March, Jagex announced the appointment of a new CEO, Jon Bellamy. Mr Bellamy then decided to almost immediately paint a huge target on his back by cancelling the Runescapes Pride event. This led to widespread condemnation about his perceived... | Read more »
Marvel Contest of Champions adds two mor...
When I saw the latest two Marvel Contest of Champions characters, I scoffed. Mr Knight and Silver Samurai, thought I, they are running out of good choices. Then I realised no, I was being far too cynical. This is one of the things that games do best... | Read more »
Grass is green, and water is wet: Pokémo...
It must be a day that ends in Y, because Pokémon Trading Card Game Pocket has kicked off its Zoroark Drop Event. Here you can get a promo version of another card, and look forward to the next Wonder Pick Event and the next Mass Outbreak that will be... | Read more »
Enter the Gungeon review
It took me a minute to get around to reviewing this game for a couple of very good reasons. The first is that Enter the Gungeon's style of roguelike bullet-hell action is teetering on the edge of being straight-up malicious, which made getting... | Read more »

Price Scanner via MacPrices.net

Take $150 off every Apple 11-inch M3 iPad Air
Amazon is offering a $150 discount on 11-inch M3 WiFi iPad Airs right now. Shipping is free: – 11″ 128GB M3 WiFi iPad Air: $449, $150 off – 11″ 256GB M3 WiFi iPad Air: $549, $150 off – 11″ 512GB M3... Read more
Apple iPad minis back on sale for $100 off MS...
Amazon is offering $100 discounts (up to 20% off) on Apple’s newest 2024 WiFi iPad minis, each with free shipping. These are the lowest prices available for new minis among the Apple retailers we... Read more
Apple’s 16-inch M4 Max MacBook Pros are on sa...
Amazon has 16-inch M4 Max MacBook Pros (Silver and Black colors) on sale for up to $410 off Apple’s MSRP right now. Shipping is free. Be sure to select Amazon as the seller, rather than a third-party... Read more
Red Pocket Mobile is offering a $150 rebate o...
Red Pocket Mobile has new Apple iPhone 17’s on sale for $150 off MSRP when you switch and open up a new line of service. Red Pocket Mobile is a nationwide MVNO using all the major wireless carrier... Read more
Switch to Verizon, and get any iPhone 16 for...
With yesterday’s introduction of the new iPhone 17 models, Verizon responded by running “on us” promos across much of the iPhone 16 lineup: iPhone 16 and 16 Plus show as $0/mo for 36 months with bill... Read more
Here is a summary of the new features in Appl...
Apple’s September 2025 event introduced major updates across its most popular product lines, focusing on health, performance, and design breakthroughs. The AirPods Pro 3 now feature best-in-class... Read more
Apple’s Smartphone Lineup Could Use A Touch o...
COMMENTARY – Whatever happened to the old adage, “less is more”? Apple’s smartphone lineup. — which is due for its annual refresh either this month or next (possibly at an Apple Event on September 9... Read more
Take $50 off every 11th-generation A16 WiFi i...
Amazon has Apple’s 11th-generation A16 WiFi iPads in stock on sale for $50 off MSRP right now. Shipping is free: – 11″ 11th-generation 128GB WiFi iPads: $299 $50 off MSRP – 11″ 11th-generation 256GB... Read more
Sunday Sale: 14-inch M4 MacBook Pros for up t...
Don’t pay full price! Amazon has Apple’s 14-inch M4 MacBook Pros (Silver and Black colors) on sale for up to $220 off MSRP right now. Shipping is free. Be sure to select Amazon as the seller, rather... Read more
Mac mini with M4 Pro CPU back on sale for $12...
B&H Photo has Apple’s Mac mini with the M4 Pro CPU back on sale for $1259, $140 off MSRP. B&H offers free 1-2 day shipping to most US addresses: – Mac mini M4 Pro CPU (24GB/512GB): $1259, $... Read more

Jobs Board

All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.