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

SoftRAID 5.8.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID allows the user to create and manage RAID 4 and 5 volumes, RAID 1+0, and RAID 1 (Mirror) and... Read more
Audio Hijack 3.7.3 - Record and enhance...
Audio Hijack (was Audio Hijack Pro) drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio... Read more
CleanMyMac X 4.6.15 - Delete files that...
CleanMyMac makes space for the things you love. Sporting a range of ingenious new features, CleanMyMac lets you safely and intelligently scan and clean your entire system, delete large, unused files... Read more
Suitcase Fusion 21.2.1 - Font management...
Suitcase Fusion is the creative professional's font manager. Every professional font manager should deliver the basics: spectacular previews, powerful search tools, and efficient font organization.... Read more
Civilization VI 1.3.6 - Next iteration o...
Civilization® VI is the award-winning experience. Expand your empire across the map, advance your culture, and compete against history’s greatest leaders to build a civilization that will stand the... Read more
Dashlane 6.2042.0 - Password manager and...
Dashlane is an award-winning service that revolutionizes the online experience by replacing the drudgery of everyday transactional processes with convenient, automated simplicity - in other words,... Read more
Airfoil 5.9.2 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
VirtualBox 6.1.16 - x86 virtualization s...
VirtualBox is a family of powerful x86 virtualization products for enterprise as well as home use. Not only is VirtualBox an extremely feature rich, high performance product for enterprise customers... Read more
Xcode 12.1 - Integrated development envi...
Xcode includes everything developers need to create great applications for Mac, iPhone, iPad, and Apple Watch. Xcode provides developers a unified workflow for user interface design, coding, testing... Read more
FileZilla 3.51.0 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.51.0: Bugfixes and minor changes: Fixed import of... Read more

Latest Forum Discussions

See All

PUBG Mobile has provided yet another upd...
PUBG Mobile has been making a point of publicly mentioning all of their ongoing efforts to vanquish cheating from the popular battle royale. Today two teams within the company have provided updates on their progress. [Read more] | Read more »
Zombieland: AFK Survival is celebrating...
Zombieland: AFK Survival is currently celebrating its one-year anniversary. If you don't quite recognise the name that's because it initially launched as Zombieland: Double Tapper. Anyway, the game is celebrating turning one with two Halloween-... | Read more »
Distract Yourself With These Great Mobil...
There’s a lot going on right now, and I don’t really feel like trying to write some kind of pithy intro for it. All I’ll say is lots of people have been coming together and helping each other in small ways, and I’m choosing to focus on that as I... | Read more »
Genshin Impact Guide - Gacha Strategy: W...
If you're playing Genshin Impact without spending money, you'll always need to be looking for ways to optimize your play to maximize rewards without getting stuck in a position where you're tempted to spend. The most obvious trap here is the game'... | Read more »
Genshin Impact Adventurer's Guide
Hello and well met, fellow adventurers of Teyvat! Check out our all-in-one resource for all things Genshin Impact. We'll be sure to add more as we keep playing the game, so be sure to come back here to check for updates! [Read more] | Read more »
Genshin Impact Currency Guide - What...
Genshin Impact is great fun, but make no mistake: this is a gacha game. It is designed specifically to suck away time and money from you, and one of the ways the game does this is by offering a drip-feed of currencies you will feel compelled to... | Read more »
XCOM 2 Collection on iOS now available f...
The XCOM 2 Collection, which was recently announced to be coming to iOS in November, is now available to pre-order on the App Store. [Read more] | Read more »
Presidents Run has returned for the 2020...
IKIN's popular endless runner Presidents Run has returned to iOS and Android just in time for the 2020 election season. It will see players choosing their favourite candidate and guiding them on a literal run for presidency to gather as many votes... | Read more »
New update for Cookies Must Die adds new...
A new update for Rebel Twins’ platformer shooter Cookies Must Die is coming out this week. The update adds quite a bit to the game, including new levels and characters to play around with. [Read more] | Read more »
Genshin Impact Guide - How to Beat Pyro...
The end game of Genshin Impact largely revolves around spending resin to take on world bosses and clear domain challenges. These fights grant amazing rewards like rare artifacts and ascension materials for weapons and adventurers, but obviously... | Read more »

Price Scanner via MacPrices.net

Use our exclusive iPhone Price Trackers to fi...
Looking for a new Apple iPhone 12 or 12 Pro? Perhaps a deal on last year’s iPhone 11? Check out our iPhone Price Tracker here at MacPrices.net. We track new and clearance iPhone prices from Apple as... Read more
Weekend deal: $100 off 13″ MacBook Airs at Am...
Amazon has new 2020 13″ MacBook Airs on sale for $100 off Apple’s MSRP, starting at only $899. Their prices are the lowest available for new MacBooks from any Apple resellers. These are the same 13″... Read more
New 10.9″ 64GB Apple iPad Air on sale for $55...
Amazon has Apple’s new 2020 10.9″ 64GB WiFi iPad Air on sale today for $549.99 shipped. That’s $40 off MSRP. Pre-orders are available today at this discounted price, and Amazon states that the iPad... Read more
Get a clearance 2019 27″ 5K iMac for up to $5...
Apple has Certified Refurbished 2019 27″ 5K iMacs available starting at $1439 and up to $520 off their original MSRP. Apple’s one-year warranty is standard and shipping is free. The following... Read more
AT&T offers the Apple iPhone 11 for $10/m...
AT&T is offering Apple’s 64GB iPhone 11 for $10 per month, for customers opening a new line of service, no trade-in required. Discount is applied via monthly bill credits over a 30 month period.... Read more
Apple’s 2020 11″ iPad Pros on sale today for...
Apple reseller Expercom has new 2020 11″ Apple iPad Pros on sale for $50-$75 off MSRP, with prices starting at $749. These are the same iPad Pros sold by Apple in their retail and online stores: – 11... Read more
Did Apple Drop The Ball By Not Branding Its C...
EDITORIAL: 10.21.20 – In the branding game, your marketing strategy can either be a hit or a miss and the latter is the case for Apple when it missed out on an opportunity to brand its “SE” series of... Read more
27″ 6-core and 8-core iMacs on sale for up to...
Adorama has Apple’s 2020 27″ 6-core and 8-core iMacs on sale today for $50-$100 off MSRP, with prices starting at $1749. Shipping is free: – 27″ 3.1GHz 6-core iMac: $1749, save $50 – 27″ 3.3GHz 6-... Read more
Apple’s 16″ MacBook Pros are on sale for $300...
B&H Photo has 16″ MacBook Pros on sale today for $300-$350 off Apple’s MSRP, starting at $2099. Expedited shipping is free to many addresses in the US. Their prices are among the lowest available... Read more
Apple has 2020 13″ MacBook Airs available sta...
Apple has a full line of Certified Refurbished 2020 13″ MacBook Airs available starting at only $849 and up to $200 off the cost of new Airs. Each MacBook features a new outer case, comes with a... Read more

Jobs Board

Dental Receptionist - *Apple* Valley Clinic...
Dental Receptionist - Apple Valley Clinic + Job ID: 57314 + Department: Apple Valley Dental + City: Apple Valley, MN + Location: HP - Apple Valley Clinic Read more
*Apple* Mobility Specialist - Best Buy (Unit...
**788165BR** **Job Title:** Apple Mobility Specialist **Job Category:** Store Associates **Store Number or Department:** 001013-Virginia Commons-Store **Job Read more
Cub Foods - *Apple* Valley - Now Hiring Par...
Cub Foods - Apple Valley - Now Hiring Part Time! United States of America, Minnesota, Apple Valley Retail Post Date Oct 08, 2020 Requisition # 124800 Sign Up for Read more
*Apple* Mobility Specialist - Best Buy (Unit...
**784631BR** **Job Title:** Apple Mobility Specialist **Job Category:** Store Associates **Store Number or Department:** 000522-Baxter-Store **Job Description:** The Read more
Senior Data Engineer - *Apple* - Theorem, L...
Job Summary Apple is seeking an experienced, detail-minded data engineeringconsultant to join our worldwide business development and strategy team. If you are Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.