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

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
KeyCue 9.8 - Displays all menu shortcut...
KeyCue has always been a handy tool for learning and remembering keyboard shortcuts. With a simple keystroke or click, KeyCue displays a table with all available keyboard shortcuts, system-wide... Read more
AppCleaner 3.5.1 - Uninstall your apps e...
AppCleaner allows you to uninstall your apps easily. It searches the files created by the applications and you can delete them quickly. Version 3.5.1: Fixed a code-signing issue causing AppCleaner... Read more
A Better Finder Attributes 7.03 - Change...
A Better Finder Attributes allows you to change JPEG & RAW shooting dates, JPEG EXIF meta-data tags, file creation & modification dates, file flags and deal with invisible files. Correct EXIF... Read more
Postbox 7.0.33 - Powerful and flexible e...
Postbox is a desktop feature-stuffed email client, news application, and feed reader that helps you manage your work life and increase productivity. Now you can organize all your email accounts in... Read more
Adobe InCopy 16.0 - Create streamlined e...
InCopy is available as part of Adobe Creative Cloud for $52.99/month (or $4.99/month for InCopy app only). Adobe InCopy, ideal for large team projects involving both written copy and design work,... Read more
Steam 2.0 - Multiplayer and communicatio...
Steam is a digital distribution, digital rights management, multiplayer and communications platform developed by Valve Corporation. It is used to distribute a large number of games and related media... Read more
Adobe Lightroom Classic 10.0 - Import, d...
You can download Lightroom for Mac as a part of Creative Cloud for only $9.99/month with Photoshop, included as part of the photography package. The latest version of Lightroom gives you all of the... Read more
Adobe InDesign 16.0 - Professional print...
InDesign is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign is part of Creative Cloud. That means you... Read more
Adobe After Effects 17.5 - Create profes...
After Effects is available as part of Adobe Creative Cloud for $52.99/month (or $20.99/month for a single app license). The new, more connected After Effects can make the impossible possible. Get... Read more

Latest Forum Discussions

See All

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 »
Moto Rider GO has received a huge update...
Moto Rider GO: Highway Traffic is a popular free-to-play racing game that initially launched back in 2017 and has since racked up over 100 million downloads. Today it has received a sizeable update that introduces several KTM and Husqvarna... | Read more »
ORDESA is a spooky interactive film that...
French studio Cinétévé Experience and ARTE have released interactive movie ORDESA for iOS and Android today. It arrives at the perfect time of year, telling a story about a mysterious haunted house that the viewer suddenly finds themselves lost in... | Read more »
Genshin Impact Guide - How to Beat Storm...
If you've followed our progression guide for Genshin Impact up to Adventure Rank 25, you have reached the point where you can face off against Stormterror on a weekly basis for some pretty sweet rewards. Beating this deadly dragon isn't as easy as... | Read more »

Price Scanner via MacPrices.net

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
These major wireless carriers will give you a...
Apple’s wireless partners are offering several deals on iPhone 12 pre-orders right now. If you’re willing to switch carriers, you can get a free iPhone 12 right now. Here’s where to take advantage of... Read more
4 day sale at Sams Club: Save $24-$29 on Appl...
Sams Club has Apple Watch Series 6 GPS models on sale this week for $24-$29 off Apple’s MSRP, starting at $374. Sale ends this Thursday, October 22nd: – 40mm Apple Watch Series 6 GPS: $374.98, save $... Read more
US Cellular offers Apple iPhone 12 Pro for $8...
US Cellular has the 2020 128GB iPhone 12 Pro available for $829 off MSRP for new customers signing up for an Unlimited data plan, or $5.66 per month. Cost of the phone is spread over a 30 month... Read more
Buy one Apple Watch SE or Series 6 at AT&...
Buy one Apple Watch SE or Series 6 at AT&T, and get $200 off the price of a second Apple Watch. One new line required, and price discounted reflected in bill credits over a 30 month period. The... Read more
AT&T offers free iPhone 12, $800 off iPho...
AT&T is offering Apple’s new iPhone 12 for free, or up to $800 off the iPhone 12 Pro, for customers opening a new line of service plus an eligible trade-in. Discount is applied via monthly bill... Read more

Jobs Board

*Apple* Endpoint Engineer - Argonne National...
Apple Endpoint Engineer **Requisition Number:** **408932** **Location:** **Lemont, IL** **Functional Area:** **Information Technology** **Division:** **BIS\-Business Read more
Core *Apple* Computing Pro - Best Buy (Unit...
**786358BR** **Job Title:** Core Apple Computing Pro **Job Category:** Store Associates **Store Number or Department:** 001080-Lake Charles-Store **Job Read more
Department Manager- Tech Shop/ *Apple* Stor...
…their parents want, and our faculty needs. As a Department Manager in our Tech Shop/ Apple Store you will spend the majority of your time on the sales floor engaging Read more
Geek Squad *Apple* Consultation Professiona...
**782284BR** **Job Title:** Geek Squad Apple Consultation Professional **Job Category:** Store Associates **Store Number or Department:** 000140-San Carlos-Store Read more
*Apple* /Mac IT Support - Randstad (United St...
Apple /Mac IT Support **job details:** + location:San Francisco, CA + salary:$45 - $50 per hour + date posted:Thursday, October 8, 2020 + job type:Contract + Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.