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

FontExplorer X Pro 5.0.1 - Font manageme...
FontExplorer X Pro is optimized for professional use; it's the solution that gives you the power you need to manage all your fonts. Now you can more easily manage, activate and organize your... Read more
Calcbot 1.0.2 - Intelligent calculator a...
Calcbot is an intelligent calculator and unit converter for the rest of us. Featuring an easy-to-read history tape, expression view, intuitive conversion, and much more! Features History Tape -... Read more
MTR 5.0.0.1 - The Mac's oldest and...
MTR (was MacTheRipper)--the Mac's oldest and smartest DVD-backup app--is now updated to version 5.001 MTR -- the complete toolbox, not a one-trick, point-and-click extractor. MTR is intended for... Read more
LibreOffice 4.4.5.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Adobe Lightroom 6.1.1 - Import, develop,...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
File Juicer 4.41 - Extract images, video...
File Juicer is a drag-and-drop can opener and data archaeologist. Its specialty is to find and extract images, video, audio, or text from files which are hard to open in other ways. It finds and... Read more
A Better Finder Rename 9.52 - File, phot...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
OmniFocus 2.2.3 - GTD task manager with...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more
TinkerTool 5.4 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Tinderbox 6.3.1 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more

Gallery Doctor (Photography)
Gallery Doctor 1.0 Device: iOS iPhone Category: Photography Price: $2.99, Version: 1.0 (iTunes) Description: Free up valuable iCloud and iPhone storage with Gallery Doctor, the only iPhone cleaner that automatically identifies the... | Read more »
You Against Me (Games)
You Against Me 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: A simple game… You. Me. Claim, steal, lock, score, win! | Read more »
Yep, it's True - Angry Birds 2 is O...
The not exactly rumors were true and the birds are back. Angry Birds 2 has come to the App Store and the world will... well I suppose it'll still be the same, but now we have more bird-flinging options! [Read more] | Read more »
You Could Design Your Own Card for Chain...
If you've ever wanted to create your own item, weapon, trap, or even monster for Chainsaw Warrior: Lords of the Night, this is your chance. Auroch Digital is currently holding a contest so that fans can fight to the death (not really) to see which... | Read more »
Bitcoin Billionaire is Going Back in Tim...
If you thought you managed to buy everything there is to buy in Bitcoin Billionaire and make all the money, well you though wrong. Those of you who made it far enough might remember investing in time travel - and it looks like that investment is... | Read more »
Domino Drop (Games)
Domino Drop 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Domino Drop is a delightful new puzzle game with dominos and gravity!Learn how to play it in a minute, master it day by day.Your... | Read more »
OPERATION DRACULA (Games)
OPERATION DRACULA 1.0.1 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0.1 (iTunes) Description: 25% off launch sale!!! 'Could prove to be one of the most accurate representations of the Japanese bullet hell shmup... | Read more »
Race The Sun (Games)
Race The Sun 1.01 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.01 (iTunes) Description: You are a solar craft. The sun is your death timer. Hurtle towards the sunset at breakneck speed in a futile race against time.... | Read more »
Tap Delay (Music)
Tap Delay 1.0.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0.0 (iTunes) Description: Back in the “old days”, producers and engineers created delay and echo effects using tape machines. Tap Delay combines the warm... | Read more »
This Week at 148Apps: July 20-24, 2015
July is Heating Up 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... | Read more »

Price Scanner via MacPrices.net

Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
12-inch MacBooks in stock for $20 off, save o...
Adorama has 12″ Retina MacBooks in stock for $20 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, free 4-... Read more
College Student Deals: Additional $100 off Ma...
Take an additional $100 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through August 8, 2015. Anyone with a valid .EDU email address can take... Read more
2015 13-inch 2.7GHz Retina MacBook Pro on sal...
B&H Photo has the new 2015 13″ 2.7GHz/128GB Retina MacBook Pro on sale today for $1199 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
2.8GHz Mac mini available for $988, includes...
Adorama has the 2.8GHz Mac mini available for $988, $11 off MSRP, including a free copy of Apple’s 3-Year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax in NY & NJ... 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
High-Precision Battery Fuel Gauge IC Extends...
Renesas Electronics Corporation has announced its new lithium-ion (Li-ion) battery fuel gauge IC, the RAJ240500, designed to extend battery life for connected mobile devices such as tablets, notebook... Read more
27-inch 3.3GHz 5K iMac on sale for $1799, $20...
B&H Photo has the 27″ 3.3GHz 5K iMac on sale for $1799 including free shipping plus NY tax only. Their price is $200 off MSRP, and it’s the lowest price available for this model from any Apple... Read more
Twelve South Free Dual Screen Backgrounds Co...
Twelve South has posted a second collection of travel Desktop photos, noting: For the Twelve South team, a vacation is never just a vacation. It’s a time to try out new prototypes on the road, visit... Read more
Apple Refurbished iMacs available for up to $...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $1949 $... Read more

Jobs Board

Engineering Manager, Search Relevance, *Appl...
**Job Summary** Apple 's new Spotlight Suggestions service provides fast, relevant search results from the Inte et in Spotlight and Safari on iOS and OS X. We are looking Read more
Lead Infrastructure Engineer - *Apple* /Mac P...
…of a team * Requires proven problem solving skills Preferred Additional: * Apple Certified System Administrator (ACSA) * Apple Certified Technical Coordinator (ACTC) 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
*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
*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.