TweetFollow Us on Twitter

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

Surely one of the most interesting things about life is that it’s unpredictable. You’re never quite sure exactly what is going to happen next. Think about the possibilities: Without any warning whatsoever you could meet someone you haven’t seen for years, a meteor could slam into the side of your house, Elvis could reappear, or the MacTech Magazaine Programmers’ Challenge deadline could be moved up after it had been published. Just knowing that these types of things could happen certainly does keep one on one’s toes, no?

Surprise! Due to gremlins in the production room, the deadline for the Nov/Dec puzzle was stated as being Jan 1st instead of the correct date of Dec 1st. Our apologies. To be fair, we will honor all submissions received up until Jan 1st and if a better one than the winner given below comes in we will publish the new winner next month. Hopefully the gremlin traps we’ve set will prevent this from happening again. Or, since this is the second time this has happened, maybe this month’s Challenge should be to accurately guess its deadline date...

The if-nothing-better-comes-in-before-Jan-1st winner of the “Millions of Colors?” challenge is Tom Pinkerton (Wilmette, IL). While I applaud his use of a minimal initialization loop and hard-coded array indexes, there is one thing that could be improved. This loop:

 register long*  sInitPtr;
 register long i;

 sInitPtr = sBluListPtr;
 i = 64;
 while (i--) {
 sInitPtr[3] =
 sInitPtr[2] =
 sInitPtr[1] =
 sInitPtr[0] = -1;
 sInitPtr += 4;
 }

could be better written as:

 register long*  sInitPtr;
 register long i, minusOne;

 sInitPtr = sBluListPtr;
 minusOne = -1;
 i = 64*4;
 do {
 *sInitPtr++ = minusOne;
 } while (--i);

which executes faster and is fewer bytes. Other than that little nit, Tom’s solution is clever and well implemented.

New E-Mail Addresses!

In the quest for better ways to work the Programmers’ Challenge, we have added a series of e-mail addresses for the puzzle. Please use these addresses. AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com, and CompuServe: 71552,174.

Remember, that you cannot send files over Internet, but you can just send a message with the code in the message.

Insane Anglo Warlord

Did anyone see Sneakers? The movie itself had extremely few redeeming qualities but there was an interesting effect that they did with the credits. The movie was about secret codes. Each person’s name that came up had the letters scrambled to make valid English words which would then descramble themselves to be the person’s name (without adding or deleting any letters). For instance, Robert Redford initially came up as Fort Red Border and then descrambled to Robert Redford through a series of letter rearrangement steps.

What I’d like to do is ask you to write the routine that would come up with Fort Red Border (or any other valid set of English words) when given Robert Redford as input. But that would require the use of a large word list that I’m almost positive Neil wouldn’t want to print in this tiny little column. So, instead, I’m going to ask for a subset of this effect. Given the starting string, the ending string and the desired number of steps, the challenge is to come up with the intermediate strings in an appropriately interesting way (which may or may not involve some randomness-your decision).

The prototype of the function you write is:

void Descramble(startString, endString, numSteps, 
 stepStringPtrs)
Str255  startString, endString;
unsigned short   numSteps;
Str255  *stepStringPtrs[20];

Example:

 Input:
 startString = “\pFORT RED BORDER”
 endString = “\pROBERT REDFORD ” <note space at end>
 numSteps = 4
 stepStringPtrs = <numSteps pointers to Str255s allocated
 by the caller>

 Output:
 *stepStringPtrs[0] = “\pROOR TED BFRDER”
 *stepStringPtrs[1] = “\pRORRET D BFODER”
 *stepStringPtrs[2] = “\pROBDET R RFORED”
 *stepStringPtrs[3] = “\pROBEDT RERFORD ”

You can assume the input and output strings each have the same number of uppercase letters, which is at least twice numSteps (i.e. the minimum string length for a 4 step puzzle is 8 characters). Each intermediate string should match the final string a little bit better than the previous one (in terms of the number of letters that are in their final correct positions). There is no “correct” algorithm here-it’s up to you to devise one (i.e. your solution does not need to exactly match the example output given here). Unlike previous Programmer Challenges, this one will be judged primarily on effect, not speed. I’m looking for a smooth transition from startString to endString (and if it’s really fast and small then that’s an extra bonus).

So, who can guess what you get if you rearrange the letters in “Ronald Wilson Reagan”?

Here is Tom’s winning solution to the Nov/Dec Challenge:

// UniqueRGBValues.c:
//   A function that returns the number of
//   unique colors found in a 24-bit RGB image.
// Author: Tom Pinkerton

unsigned long
UniqueRGBValues(Ptr baseAddress,
 short numRows, short numCols)
{
 Handle sBuffers = nil;
 long   sUniquePixels = 0;

// Allocate memory for the data
// structures. We will need:
// 256 x 4 bytes for the unique blue value table.
// 256 x 256 x 8 bytes for the Red/Green
//   intersection grid.
// numRows x numCols x 4 bytes for the
//   master blue list.
 sBuffers = NewHandle((((long)numRows *
  (long)numCols) * 4L) + 525312);
 if (sBuffers != nil) {
 
 // Setup pointers to the data structures.
 long*  sBluListPtr =
  (long*)((char*)*sBuffers + 0);
 long*  sRGTablePtr =
  (long*)((char*)*sBuffers + 1024);
 long*  sRGLinksPtr =
  (long*)((char*)*sBuffers + 525312);
 long*  sRGBase = nil;
 
// Initialize the Red/Green intersection
// grid and the master Blue list with 
// -1's.
 {
 register long*  sInitPtr;
 register long i;
 
// A -1 in this table means that the blue
// value for a particular Red/Green
// combination is not yet found.
 sInitPtr = sBluListPtr;
 i = 64;
 while (i--) {
 sInitPtr[3] =
 sInitPtr[2] =
 sInitPtr[1] =
 sInitPtr[0] = -1;
 sInitPtr += 4;
 }
 
// Only the blue list link need be
// initialized (first of two longs) for
// each element. A -1 means that a unique
// Red/Green pair represented by this
// intersection has not yet been found.
 sInitPtr = sRGTablePtr;
 i = 4096;
 while (i--) {
 sInitPtr[30] =
 sInitPtr[28] =
 sInitPtr[26] =
 sInitPtr[24] =
 sInitPtr[22] =
 sInitPtr[20] =
 sInitPtr[18] =
 sInitPtr[16] =
 sInitPtr[14] =
 sInitPtr[12] =
 sInitPtr[10] =
 sInitPtr[ 8] =
 sInitPtr[ 6] =
 sInitPtr[ 4] =
 sInitPtr[ 2] =
 sInitPtr[ 0] = -1;
 sInitPtr += 32;
 }
 }
 
// Scan the image to create a linked list of blue values at 
// each unique Red/Green intersection. Each element in the
// Red/Green intersection grid consists of the first link 
// of that intersection's blue list (initially -1) and a 
// link to the next Red/Green intersection which contains 
// a blue list. Whereas the Red/Green link is a pointer 
// to the next Red/Green intersection, a blue list link 
// holds an array index in its low order 3 bytes and an 
// actual blue value in its high order byte. The blue link
// index refers to an element in the master blue list. 
// Each master blue list element then points to the next 
// blue value link within a specific blue list or terminates 
// the list with a -1 value.
 {
 register unsigned char*
 sPixelsPtr = (unsigned char*)baseAddress;
 register long* sRGPtr;
 register long*  sLinkPtr = sRGLinksPtr;
 register long sLinkIndex = 0;
 register long sNumPixels = 
 (long)numRows * (long)numCols;
 
// For each pixel in the image, do the following.
 while (sNumPixels--) {
 
// Concatenate the red and green values to create an offset 
// used to point at the unique Red/Green element in the
// Red/Green intersection grid.
 sRGPtr = sRGTablePtr +
  ((((long)sPixelsPtr[1] << 8) |
  (long)sPixelsPtr[2]) << 1);
 
// If this is the first pixel with this particular Red/Green 
// combination, then add the Red/Green intersection to the
// Red/Green linked list.
 if (sRGPtr[0] == -1) {
 sRGPtr[1] = (long)sRGBase;
 sRGBase = sRGPtr;
 }
 
// Create a new blue link with the pixel's blue value and 
// add it to Red/Green intersection's blue list.
 *sLinkPtr = sRGPtr[0];
 sRGPtr[0] = sLinkIndex | ((long)sPixelsPtr[3] << 24);
 
// Increment stuff for the next go 'round.
 ++sLinkPtr;
 ++sLinkIndex;
 sPixelsPtr += 4;
 }
 }
 
// For each list of blue values at a unique Red/Green 
// intersection,  determine the number of unique blue
// values in that list. This calculates the number of unique 
// colors that have the same Red and Green values.
// Accumulating the number of unique colors at every 
// Red/Green intersection gives us the total 
// number of unique colors.
 {
 register long*  sRGPtr = sRGBase;
 register long*  sBlueBase = nil;
 register long*  sBluePtr;
 register long   sLinkIndex;
 
// For each Red/Green intersection found above, do the 
// following.
 while (sRGPtr != nil) {
 
// Walk the list of blue values for this Red/Green pair. 
// For each one, do the following.
 sLinkIndex = sRGPtr[0];
 while (sLinkIndex != -1) {
 
// Create a pointer to the unique blue value element.
 sBluePtr = sBluListPtr +
 ((unsigned long)sLinkIndex >> 24);
 
// A -1 here means that the unique R/G and B color has not 
// yet been counted.  Therefore, mark the fact that it has
// been counted by adding the element to a linked list 
// and incrementing the unique color count. The blue value 
// linked list is used later to quickly reset itself.
 if (*sBluePtr == -1) {
 *sBluePtr = (long)sBlueBase;
 sBlueBase = sBluePtr;
 ++sUniquePixels;
 }
 
// Get the next blue list link in the blue list.
 sLinkIndex = sRGLinksPtr[sLinkIndex & 0x00FFFFFF];
 }
 
// Reset the blue count list by walking its links and 
// replacing them again with -1's.
 sBluePtr = sBlueBase;
 while (sBluePtr != nil) {
 sBlueBase = (long*)*sBluePtr;
 *sBluePtr = -1;
 sBluePtr = sBlueBase;
 }
 sBlueBase = nil;
 
// Get next Red/Green intersection.
 sRGPtr = (long*)sRGPtr[1];
 }
 }
 
 DisposHandle(sBuffers);
 }
 return(sUniquePixels);
}

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

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

Logic Pro X 10.1.1 - Music creation and...
Apple Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get... Read more
VLC Media Player 2.2.0 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Sound Studio 4.7.8 - Robust audio record...
Sound Studio lets you easily record and professionally edit audio on your Mac. Easily rip vinyls and digitize cassette tapes, or record lectures and voice memos. Prepare for live shows with live... Read more
LibreOffice 4.4.1.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
Freeway Pro 7.0.3 - Drag-and-drop Web de...
Freeway Pro lets you build websites with speed and precision... without writing a line of code! With its user-oriented drag-and-drop interface, Freeway Pro helps you piece together the website of... Read more
Cloud 3.3.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
Cyberduck 4.6.5 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Firefox 36.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and... Read more
Thunderbird 31.5.0 - Email client from M...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
VOX 2.4 - Music player that supports man...
VoxIt just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features & support for all audio formats you should ever need... Read more

Get The Whole Story – Lone Wolf Complete...
Get The Whole Story – Lone Wolf Complete is Now Available and On Sale Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Who Wore it Best? The Counting Dead vs....
Like it or not, the “clicker” genre, popularized by cute distractions like Candy Box and Cookie Clicker, seems like it’s here to stay. So Who Wore it Best? takes a look at two recent examples: The Counting Dead and AdVenture Capitalist. | Read more »
Card Crawl, the Mini Deck Building Game,...
Card Crawl, the Mini Deck Building Game, is Coming Soon Posted by Jessica Fisher on February 27th, 2015 [ permalink ] Tinytouchtales and Mexer have announced their new game, | Read more »
Witness an all new puzzle mechanic in Bl...
Well, BlastBall MAX is not one of those games and is bucking trends such as timers, elements of randomness, and tacked-on mechanics in favor of pure puzzle gameplay. When you first boot up the game you’ll see a grid made up of squares that are each... | Read more »
This Princess Has a Dragon and She isn’t...
This Princess Has a Dragon and She isn’t Afraid to Useit. | Read more »
Mecha Showdown Review
Mecha Showdown Review By Lee Hamlet on February 27th, 2015 Our Rating: :: IN A SPINUniversal App - Designed for iPhone and iPad Mecha Showdown replaces traditional buttons with a slot machine mechanic in this robot fighting game,... | Read more »
Reliance Games and Dreamworks Unveil Rea...
Reliance Games and Dreamworks Unveil Real Steel Champions Posted by Ellis Spice on February 27th, 2015 [ permalink ] Reliance Games and Dreamworks have announced that a third game in | Read more »
Sum Idea Review
Sum Idea Review By Jennifer Allen on February 27th, 2015 Our Rating: :: TAXING NUMBERSUniversal App - Designed for iPhone and iPad Sum Idea is a fairly charming but taxing puzzle game.   | Read more »
A New Badland Update Brings Daydream Lev...
A New Badland Update Brings Daydream Levels to Co-Op Posted by Ellis Spice on February 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Slashing Demons Review
Slashing Demons Review By Lee Hamlet on February 27th, 2015 Our Rating: :: IT'S A LONG WAY TO THE TOPUniversal App - Designed for iPhone and iPad Slashing Demons lacks the depth or scope to take it beyond the point of being just... | Read more »

Price Scanner via MacPrices.net

Apple CEO Tim Cook to Deliver 2015 George Was...
Apple CEO Tim Cook will deliver the George Washington University’s Commencement address to GWU grads on May 17, at which time he will also be awarded an honorary doctorate of public service from the... Read more
Apple restocks refurbished Mac minis for up t...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
Save up to $50 on iPad Air 2s, NY tax only, f...
 B&H Photo has iPad Air 2s on sale for $50 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $469.99 $30 off - 64GB iPad Air 2 WiFi: $549 $50 off - 128GB iPad Air 2... Read more
16GB iPad Air 2 on sale for $447, save $52
Walmart has the 16GB iPad Air 2 WiFi on sale for $446.99 on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale price for online orders only,... Read more
iMacs on sale for up to $205 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1029 $70 off - 21″ 2.7GHz iMac: $1199 $100 off - 21″ 2.9GHz... Read more
Apple Takes 89 Percent Share of Global Smartp...
According to the latest research from Strategy Analytics, global smartphone operating profit reached US$21 billion in Q4 2014. The Android operating system captured a record-low 11 percent global... Read more
New Travel Health App “My Travel Health” iOS...
Rochester, Minnesota based Travel Health and Wellness LLC has announced that its new iOS app help safeguard the user’s health when traveling abroad — “My Travel Health” is now available on the Apple... Read more
Sale! MacBook Airs for up to $115 off MSRP
B&H Photo has MacBook Airs on sale for up to $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 128GB MacBook Air: $799 100 off MSRP - 11″ 256GB MacBook Air: $999 $100... Read more
15-inch 2.0GHz Retina MacBook Pro (refurbishe...
The Apple Store has Apple Certified Refurbished previous-generation 15″ 2.0GHz Retina MacBook Pros available for $1489 including free shipping plus Apple’s standard one-year warranty. Their price is... Read more
Wither The iPad mini? End Of The Road Imminen...
AppleDailyReport’s Dennis Sellers predicts that the iPad mini is going to be left to wither on the vine, as it were, and then just allowed to fade away — a casualty of the IPhone 6 Plus and other... Read more

Jobs Board

Sr. Technical Services Consultant, *Apple*...
**Job Summary** Apple Professional Services (APS) has an opening for a senior technical position that contributes to Apple 's efforts for strategic and transactional Read more
Event Director, *Apple* Retail Marketing -...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global engagement strategy and team. Delivering an overarching brand Read more
*Apple* Pay - Site Reliability Engineer - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant - Retail Sales...
**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
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.