TweetFollow Us on Twitter

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

Rotated Bits

This month’s challenge is to write a routine that quickly rotates a 1-bit deep bitMap 90 degrees clockwise. You are given pointers to a source bitMap and destination bitMap. Space for the destination pixels has already been allocated (the baseAddr field is valid) and the rowBytes and bounds fields have been set up for you. All you have to do is rotate the bits.

The function prototype you write is:

void RotateBitMapClockwise(srcBitMapPtr, dstBitMapPtr)
BitMap  *srcBitMapPtr;
BitMap  *dstBitMapPtr;

To check for correctness, you might want to write a test program that rotates the same bitMap four times and then diffs the result with the original (they should be identical). Have fun.

February Winner

The winner of the “Insane Anglo Warlord” challenge is Jeremy Vineyard (Lawrence, KS) whose solution was the only one of the two I received which gave valid results (the other one gave intermediate strings that had a character not in the original strings). Remember kids: you have to play the game to have a chance at winning.

Here’s the output of Jeremy’s Descramble routine when the input strings are “INSANE ANGLO WARLORD” and “RONALD WILSON REAGAN” when the number of intermediate steps is set to 10:

INSANE ANGLO WARLORD
OIDSLNE N NGWRALORAA
 ORDLINE AWNSNLORAAG
R AODSILEWANN ORALGN
R WADOSGLNIAA RLOENN
R IWODNSALRAAL OEGNN
ROD INLASL RAWOEAGNN
RONDIL A SLORWAEAGNN
RONLDLI S AORWAEAGNN
RONDL LWASIOR AEAGNN
RONWLD AILSOR AEAGNN
RONALD WILSON REAGAN

And here is Jeremy’s code to generate those strings:

/***********************************
 * Descramble.c
 * A procedure that returns a smooth 
 * transition from one string to 
 * another with the same characters, 
 * but in a different order.
 ***********************************/

#include <stdlib.h>
#include <string.h>

void Descramble(
 Str255 startString,
 Str255 endString,
 unsigned short  numSteps,
 Str255 *stepStringPtrs[20] )
{
 short  i, j, k;
 short  strLength = startString[0];
 div_t  divResult;
 short  destination, memSwitch;
 BooleanswitchPossible;

 short  distances[256];
 short  destMap[256];
 BooleandestSwitchMap[256];
 BooleancheckList[256];
 
 /* Clear the destination switching 
  * map for use. Only clear it up to 
  * strLength to save time. */
 for (i = 1; i <= strLength; i++)
 destSwitchMap[i] = false;
 
 /* This loop searches for a duplicate 
  * char 'j' for the char 'i'. Once it  * finds a duplicate, it checks 
to 
  * see whether it is already being 
  * used as another char's 
  * destination. If not, it shows that 
  * char 'j' is char 'i's destination, 
  * sets the destMap to show that char 
  * 'j' is being used, and
  * calculates how far the char 'i' needs to travel on 
  * each step to get to its destination. */
 for (i = 1; i <= strLength; i++)
 for (j = 1; j <= strLength; j++)
 if ( startString[i] == endString[j] &&
  ! destSwitchMap[j] )
 {
 /* If destSwitchMap[j] is set, then it already has a 
  * char which is using it for a destination. */
 destSwitchMap[j] = true;
 
 /* Remember this char's dest. */
 destMap[i] = j;
 
 /* Find out how far this char should move 
  * on each step. */
 if (i == j)
 distances[i] = 0;
 else
 {
    divResult = div(j - i, numSteps);
    distances[i] = divResult.quot;
 
 /* Use the remainder to make
  * sure this char moves each step.*/ 
    if (divResult.rem != 0)
    if (divResult.rem < 0)
       distances[i] -= 1;
    else
   distances[i] += 1;
 
    /* Increment to exit loop. */
    j = 512;
 }
 }
 
 /* In this loop, each character tries to move towards its 
  * destination. Its distance is then recalculated to 
  * compensate for it being switched. This creates a 
  * 'morphing' effect, where the letters in the start string 
  * gradually change to their positions in the end string. */
 for (i = 0; i < numSteps; i++)
 {
 /* Copy the appropriate string for switching. */
 if (i > 0)
 memcpy(*stepStringPtrs[i],
  *stepStringPtrs[i - 1],
  strLength + 1);
 else
 memcpy(*stepStringPtrs[0], startString,
   strLength + 1);
 
 /* Clear the check list for use. */
 for (k = 1; k <= strLength; k++)
 checkList[k] = false;
 
 /* This loop switches characters until
  * switchPossible = false. */
 do
 {
  switchPossible = false;

  for (j = 1; j <= strLength; j++)
  {
   if (distances[j] != 0 &&
  ! checkList[j])
   {
      /* Calculate this char's intended
 * destination for this step. */
      destination = j + distances[j];
        
      if (checkList[destination])
      {
 /* If the destination has already been used, find 
  * the nearest one to it to switch to. */
          destination = -1;
          
         if (distances[j] > 0)
          for (k = destination - 1; k > j;
  k -= 1)
          if (! checkList[k] &&
  distances[k] != 0)
          {
          destination = k;
          k = 512;
          }
          else;
         else
          for (k = destination + 1; k < j;
  k++)
          if (! checkList[k] &&
  distances[k] != 0)
          {
          destination = k;
          k = 512;
          }
      }
      
      if (destination > 0)
      {
       /* If destination is a valid number, do the 
   * neccessary switching. Switch the characters
   * in the string */
        memSwitch =
   stepStringPtrs[i][0][destination];
        stepStringPtrs[i][0][destination]
   = stepStringPtrs[i][0][j];
        stepStringPtrs[i][0][j] =
   memSwitch;
        
        /* Switch the character's mapped destinations. */
        memSwitch = destMap[destination];
        destMap[destination] = destMap[j];
        destMap[j] = memSwitch;
        
        /* Show that the destination has been switched. */
        checkList[destination] = true;
        
        /* Recalculate the switched char's distance. */
        if (destMap[j] == j)
        distances[j] = 0;
        else if (i + 1 < numSteps)
        {
     divResult = div(destMap[j] - j,
  numSteps - i - 1);
     distances[j] = divResult.quot;
     if (divResult.rem != 0)
     if (divResult.rem < 0)
      distances[j] -= 1;
     else
     distances[j] += 1;
  }
  
    switchPossible = true;
      }
   }
   }
 } while (switchPossible);
 
 if (i + 1 == numSteps)
 return;
 
 /* Recalculate all distances to compensate
  * for switched char's. */
 for (k = 1; k <= strLength; k++)
 if (distances[k] != 0)
 {
 if (destMap[k] == k)
 distances[k] = 0;
 else if (i + 1 < numSteps)
 {
    /* Recalculate how far this char needs to move 
 * with the number of steps that are left. */
    divResult = div(destMap[k] - k,
  numSteps - i - 1);
    distances[k] = divResult.quot;
    if (divResult.rem != 0)
    if (divResult.rem < 0)
    distances[k] -= 1;
    else
    distances[k] += 1;
 }
 }
 }
}

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

OmniOutliner Pro 4.6 - Pro version of th...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Alfred 3.1 - Quick launcher for apps and...
Alfred is an award-winning productivity application for OS X. Alfred saves you time when you search for files online or on your Mac. Be more productive with hotkeys, keywords, and file actions at... Read more
OmniOutliner 4.6 - Organize your ideas,...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Default Folder X 5.0.6 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
Adobe Creative Cloud 3.8.0.310 - Access...
Adobe Creative Cloud costs $19.99/month for a single app, or $49.99/month for the entire suite. Introducing Adobe Creative Cloud desktop applications, including Adobe Photoshop CC and Illustrator CC... Read more
MYStuff Pro 2.0.25 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
Viber 6.2.0 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device, so... Read more
Data Rescue 4.2.3 - Powerful hard drive...
Use Data Rescue to recover: crashed, corrupted or non-mounting hard drive deleted, damaged, or lost files reformatted or erased hard drive One powerful new feature found in Data Rescue 4 is... Read more
Microsoft Remote Desktop 8.0.34 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Microsoft Remote Desktop 8.0.34 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more

Find out the story behind League of Ange...
If you’re looking for a new thrilling MMORPG to play with your friends then you’ll be excited to hear that there is a sequel to one of the most well known titles in the genre – namely League of Angels 2. With a brand new 3D engine offering... | Read more »
Naruto Shippuden: Ultimate Ninja Blazing...
I'm not sure if it's possible to say you are an anime fan but also never have seen one episode of Naruto. If it is, then I resemble that remark, and if not, I offer a hearty apology. [Read more] | Read more »
5 mobile games that let you explore spac...
No Man's Sky hasn't exactly turned out to be everything it was promised. Though its core concept of exploring an unimaginably vast universe of different planets is an intriguing one, the execution has left many PS4 and PC gamers feeling like they... | Read more »
Mummy madness in new action game Tomb He...
Hot on the tail of Bump Hero, ZPlay is giving gamers another reason to get screen bashing with a brand new release. Tomb Heroes is a challenging action game in which you battle enemies in various tombs around the world. You can select from nine... | Read more »
Siralim 2 (RPG / Roguelike) (Games)
Siralim 2 (RPG / Roguelike) 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Siralim 2 is an old-school monster catching RPG. Summon and customize hundreds of creatures to fight for you as... | Read more »
Clean Text (Productivity)
Clean Text 1.0 Device: iOS Universal Category: Productivity Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Gemini - A Journey of Two Stars (Games)
Gemini - A Journey of Two Stars 1.0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1 (iTunes) Description: *** SPECIAL LAUNCH SALE: $2.99 (25% off) *** "A mesmerizing and unexpectedly emotional journey." -- Los... | Read more »
How to get four NFL superstars for your...
Even though you're probably well on your way to building a top notch squad for the new season in Madden NFL Mobile, let's say you could beef it up by adding Rob Gronkowski, Antonio Brown, Von Miller, and Todd Gurley to your roster. That's... | Read more »
Cartoon Network Superstar Soccer: Goal!!...
Cartoon Network Superstar Soccer: Goal!!! – Multiplayer Sports Game Starring Your Favorite Characters 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Become a soccer superstar with your... | Read more »
NFL Huddle: What's new in Topps NFL...
Can you smell that? It's the scent of pigskin in the air, which either means that cliches be damned, pigs are flying in your neck of the woods, or the new NFL season is right around the corner. [Read more] | Read more »

Price Scanner via MacPrices.net

RESCUECOM 2016 Semi-Annual Computer Reliabili...
The beginning of a new school year is upon us again, in which students and parents have some very important choices to make, often including the purchase of a computer or tablet. Whether you are... Read more
VRS Design Damda Glide Series iPhone 7 and 7...
What makes the Damda Glide Series for the iPhone 7 and iPhone 7 Plus special? Case maker VRS Design says its Damda Glide Series is the first mobile case to incorporate a semi-automatic mechanism for... Read more
Apple refurbished iMacs available for up to $...
Apple has Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: - 21″ 3.... Read more
Clearance 2015 13-inch MacBook Airs available...
B&H Photo has clearance 2015 13″ MacBook Airs available for $350 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $829... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
Save $120 with Apple refurbished Time Capsule...
Apple has certified refurbished Time Capsules available for $120 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $179, $120 off (not... Read more
9-inch 32GB iPad Pros on sale for $70 off MSR...
B&H Photo has 9″ 32GB WiFi Apple iPad Pros on sale for $70 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 9″ Space Gray 32GB WiFi iPad Pro: $529 $70 off MSRP - 9... Read more
Mac minis on sale for up to $140 off MSRP
Adorama has Mac minis on sale for up to $100 off MSRP including free shipping plus NY & NJ sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP Amazon has the... Read more
Back To School with OtterBox Essentials
Back to school means back to an environment that is tough on tech. OtterBox has the back to school essentials you need to keep tech safe from drops, bumps, scratches and hallway havoc. Check out the... Read more
VRS Design Releases New iPhone 7 Plus Case Li...
With a device as large and costly as the iPhone 7 Plus, it is primal instinct to protect it from potential damage. According to a study by SquareTrade in 2012, iPhone damages cost Americans roughly $... Read more

Jobs Board

*Apple* Solutions Consultant - Apple (United...
Apple Solutions ConsultantJob Number: 51218534Pleasant Hill, California, United StatesPosted: Aug. 18, 2016Weekly Hours: 40.00Job SummaryAs an Apple Solutions Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 51218354 Fredericksburg, Virginia, United States Posted: Aug. 18, 2016 Weekly Hours: 40.00 **Job Summary** As an Apple Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* /Mac Support Engineer - GFI Digital,...
FI Digital, Inc. is currently seeking candidates for a full time Apple Support Engineer to add to our Maryland Heights, Missouri IT team. Candidates must be dynamic Read more
*Apple* Solutions Consultant - Apple (United...
Apple Solutions ConsultantJob Number: 51218534Pleasant Hill, California, United StatesPosted: Aug. 18, 2016Weekly Hours: 40.00Job SummaryAs an Apple Solutions Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.