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.

 
AAPL
$93.94
Apple Inc.
-0.49
MSFT
$44.84
Microsoft Corpora
+0.15
GOOG
$589.47
Google Inc.
-5.61

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Yosemite 10.10 DP4 - Developer Prev...
Note: This is a Developer Preview. You must be a registered Apple Mac Developer to download this update. OS X Yosemite is Apple's newest operating system for Mac. An elegant design that feels... Read more
FinderPop 2.5.6 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
SpiderOak 5.1.7 - Secure cloud backup, s...
SpiderOak is a multi-platform secure online backup, storage, access, and sharing solution engineered for the consumer and small businesses. You must first sign up to use SpiderOak. Running natively... Read more
Espionage 3.6 - Simple, state of the art...
Espionage offers state-of-the-art encryption and plausible deniability for your confidential data. Sometimes, encrypting your data isn't enough to protect it. That's why Espionage 3 goes beyond data... Read more
calibre 1.45.0 - Complete e-library mana...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
iFFmpeg 4.3.1 - Convert multimedia files...
iFFmpeg is a graphical front-end for FFmpeg, a command-line tool used to convert multimedia files between formats. The command line instructions can be very hard to master/understand, so iFFmpeg does... Read more
Chromium 36.0.1985.125 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. FreeSMUG-Free OpenSource Mac User Group build is... Read more
pwSafe 3.0 - Secure password management...
pwSafe provides simple and secure password management across devices and computers. pwSafe uses iCloud to keep your password databases backed-up and synced between Macs and iOS devices. It is... Read more
Day One 1.9.6 - Maintain a daily journal...
Day One is the easiest and best-looking way to use a journal / diary / text-logging application for the Mac. Day One is well designed and extremely focused to encourage you to write more through... Read more
Google Chrome 36.0.1985.125 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more

Latest Forum Discussions

See All

HELMUT Review
HELMUT Review By Andrew Fisher on July 21st, 2014 Our Rating: :: TRUNDLE SIMULATOR 2014Universal App - Designed for iPhone and iPad HELMUT is a fun, fleeting time-sink that offers a momentary distraction and nothing else.   | Read more »
Walkr Review
Walkr Review By Jennifer Allen on July 21st, 2014 Our Rating: :: ORIGINAL WALKINGiPhone App - Designed for the iPhone, compatible with the iPad Walking is a bit more exciting thanks to this planet building/discovering sim reliant... | Read more »
Zombie Commando Review
Zombie Commando Review By Jennifer Allen on July 21st, 2014 Our Rating: :: MINDLESS SLAUGHTERUniversal App - Designed for iPhone and iPad Briefly fun but ultimately forgettable, Zombie Commando will scratch an itch then be... | Read more »
Swords & Poker Adventures Review
Swords & Poker Adventures Review By Jennifer Allen on July 21st, 2014 Our Rating: :: SOULLESS POKER PLAYUniversal App - Designed for iPhone and iPad Swords & Poker Adventures is a mishmash of Poker and RPGing, but it lacks... | Read more »
Warhammer 40,000: The Horus Heresy: Drop...
Warhammer 40,000: The Horus Heresy: Drop Assault Coming Soon to iOS Posted by Jennifer Allen on July 21st, 2014 [ permalink ] Coming soon to iOS will be an all-new Warhammer 40,000 tactical strategy game by the name of The Horus Heresy: Drop As | Read more »
A Life Worth Dying For Review
A Life Worth Dying For Review By Jordan Minor on July 21st, 2014 Our Rating: :: A BEAUTIFUL MINDUniversal App - Designed for iPhone and iPad A Life Worth Dying For is a fascinating portrait of a serious subject.   | Read more »
Zombie Puzzle Panic Review
Zombie Puzzle Panic Review By Jordan Minor on July 21st, 2014 Our Rating: :: THE MATCHING DEADUniversal App - Designed for iPhone and iPad Zombie Puzzle Panic puts some pretty neat undead twists on Match-3 puzzling.   | Read more »
This Week at 148Apps: July 14-18, 2014
Expert App Reviewers   So little time and so very many apps. What’s a poor iPhone/iPad lover to do? Fortunately, 148Apps is here to give you the rundown on the latest and greatest releases. And we even have a tremendous back catalog of reviews; just... | Read more »
Fallen Lords Review
Fallen Lords Review By Andrew Fisher on July 18th, 2014 Our Rating: :: FALLS SHORTiPad Only App - Designed for the iPad Fallen Lords is a decent game, but its similarity and inferiority compared to Ghost Stories makes it ultimately... | Read more »
Real Boxing’s New Combo Update is a Knoc...
Real Boxing’s New Combo Update is a Knockout Posted by Blake Grundman on July 18th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

Twelve South HiRise For MacBook – Height-Adju...
If you use your MacBook as a workhorse desktop substitute, as many of us do, a laptop stand combined with an external keyboard and pointing device are pretty much obligatory if you want to avoid... Read more
Why The Mac Was Not Included In The Apple/IBM...
TUAW’s Yoni Heisler cites Fredrick Paul of Network World whoi blogged last week that the Mac’s conspicuous absence from Apple and IBM’s landmark partnership agreement represents a huge squandered... Read more
Save $100 on 13-inch Retina MacBook Pros, plu...
Adorama has 13″ Retina MacBook Pros on sale for $100 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: - 13″ 2.4GHz/128GB MacBook Pro with Retina Display: $1199 - 13″ 2.... Read more
Blurr it 2.3 for iOS – Quickly Blurs Selected...
Hyderabad, India based TouchLabs has announced a new update of Blurr it 2.3, their photography app for iOS users. Blurr it allows you to blur part of the image to hide potentially sensitive or... Read more
MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for up to $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only... Read more
Amazon Announces Kindle Unlimited: Unlimited...
Amazon.com has introduced Kindle Unlimited — a new subscription service which allows customers to freely read as much as they want from over 600,000 Kindle books, and listen as much as they want to... Read more
New Linksys Wireless Range Extenders Boost Wi...
Linksys has announced its new lineup of Linksys Wi-Fi Range Extenders. Consumers often experience a weak wireless signal in some parts of their house or apartment caused by blocking elements such as... Read more
MacBook Airs available starting at $719
The Apple Store has Apple Certified Refurbished 2013 & 2012 MacBook Airs in stock today starting at $719. An Apple one-year warranty is included with each MacBook, and shipping is free: 2013... Read more
Get the best deals on iPad minis with Apple r...
The Apple Store has Certified Refurbished 2nd generation iPad minis with Retina Displays available for up to $130 off the cost of new models, starting at $339. Apple’s one-year warranty is included... Read more
Best Buy’s College Student Deals: $100 off Ma...
Take an additional $100 off all MacBooks and iMacs, $50 off iPad Airs and iPad minis, at Best Buy Online with their College Students Deals Savings, valid through July 25th. Anyone with a valid .EDU... Read more

Jobs Board

*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
Mac Expert - *Apple* Online Store Mexico -...
…MUST be fluent in English and Spanish to be considered for this position At Apple , we believe that hard work, a fun environment, creativity and innovation fuel the Read more
*Apple* Computer Technician - Fairfield Coun...
Company DescriptionWe are an Apple Authorized Sales and Service Provider. We have been selling and servicing Apple computers in the Fairfield County area for over 20 Read more
Mac Expert - *Apple* Online Store - Apple (...
**Job Summary** At Apple , we believe that hard work, a fun environment, creativity and innovation fuel the ultimate customer experience. We believe each customer Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.