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

ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Iridient Developer 3.2.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
BusyContacts 1.2.7 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
MegaSeg 6.0.5 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
BusyContacts 1.2.7 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
MegaSeg 6.0.5 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
Iridient Developer 3.2.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more

Latest Forum Discussions

See All

The best deals on the App Store this wee...
A new week means new discounts on the App Store. This week's deals run the gamut of action-adventure titles, puzzle games, and one of the best narrative adventure series out there. If you're looking to fill out your mobile gaming library on a... | Read more »
What you need to know about Animal Cross...
We hope you've been hard at work on collecting all of those holiday items in Animal Crossing: Pocket Camp, because you're about to get a whole new list of fun things to do as the game receives its first big update sometime soon. There are a lot of... | Read more »
Reigns: Her Majesty guide - how to use e...
Ruling a kingdom isn't easy--doubly so for a queen whose every decision is questioned by the other factions seeking a slice of power. Reigns: Her Majesty builds on the original game's swipey tactics, adding items that you can use to move the story... | Read more »
The best new games we played this week -...
Friday has crept up on us once again, so it's time to honor the best new games we've played over the past few days. This past week was a pretty exciting one, with the debut of lots of beautiful new indies and some familiar faces returning to the... | Read more »
Portal Knights guide- beginner tips and...
Portal Knights is finally making the jump to iOS and Android, and it's already climbing the ranks to become the next big MMO experience on mobile. This sprawling sandbox game will let you pursue any adventure you wish, whether you want to sling... | Read more »
Reigns: Her Majesty guide - how to swipe...
Reigns: Her Majesty is storming the App Store this week, bringing more tinder-esque kingdom building to eager players everywhere. If you've played the original Reigns, you'll know that leading a kingdom is never easy. It's a careful balancing act... | Read more »
Getting Over It (Games)
Getting Over It 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: A game I madeFor a certain kind of person To hurt them. • Climb up an enormous mountain with nothing but a hammer and a pot.•... | Read more »
Reigns: Her Majesty (Games)
Reigns: Her Majesty 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Pocket Legends Adventures guide - how to...
Pocket Legends Adventures is a fun action adventure RPG that takes control when you want it to, but also opens itself for player input, too, if you're looking to tkae a more active role in combat. Regardless of play style, the game can be quite... | Read more »
Portal Knights (Games)
Portal Knights 1.2.4 Device: iOS Universal Category: Games Price: $4.99, Version: 1.2.4 (iTunes) Description: Craft your adventure. Forge your hero. Become the ultimate Portal Knight! | Read more »

Price Scanner via MacPrices.net

Green Monday deal: 15″ 2.8GHz MacBook Pro on...
B&H Photo has the 15″ 2.8GHz Space Gray MacBook Pro on sale for $250 off MSRP for today only as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax for NY... Read more
Green Monday sale: B&H offers 12″ Apple i...
B&H Photo has 12″ iPad Pros on sale for up to $150 off MSRP as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax in NY & NJ only: – 12″ 64GB WiFi iPad... Read more
Holiday deal: 21″ and 27″ Apple iMacs on sale...
MacMall has 2017 21″ and 27″ Apple iMacs on sale for up to $200 off MSRP. Shipping is free: – 21″ 2.3GHz iMac: $999 $100 off MSRP – 21″ 3.0GHz iMac: $1199 $100 off MSRP – 21″ 3.4GHz iMac: $1379 $120... Read more
Holiday deal: Apple Mac minis for up to $150...
MacMall has Mac minis on sale for up to $100 off MSRP, each including free shipping: – 1.4GHz Mac mini: $399 $100 off MSRP – 2.6GHz Mac mini: $599 $100 off MSRP – 2.8GHz Mac mini: $949 $50 off MSRP... Read more
Beats by Dr. Dre – BeatsX Earphones on sale f...
Best Buy has BeatsX Earphones on sale for $109, $40 off, on their online store. Sale price for online orders only. Choose free store pickup, if available, or choose free shipping. Read more
10″ 64GB WiFi Apple iPad Pros on sale for $59...
MacMall has 10.5″ 64GB Apple iPad Pros on sale for $599 including free shipping. That’s $50 off MSRP and among the lowest prices available for these iPads from any Apple reseller. Read more
15″ 2.2GHz MacBook Pros on sale for $200-$300...
B&H Photo has the 15″ 2.2GHz MacBook Pro available for $200 off MSRP including free shipping plus NY & NJ sales tax only: – 15″ 2.2GHz MacBook Pro (MJLQ2LL/A): $1799 $200 off MSRP Apple has... Read more
Holiday sale: 15″ MacBook Pros for $200-$420...
MacMall has 15″ MacBook Pros on sale for $220-$300 off MSRP, each including free shipping: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2179, $220 off MSRP – 15″ 2.8GHz MacBook Pro Silver (... Read more
Holiday sale: 13″ MacBook Airs for up to $150...
B&H Photo has 13″ MacBook Airs on sale for $100 off MSRP as part of their Holiday sale. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook... Read more
The best Holiday sale prices on 13″ MacBook P...
B&H Photo has 13″ MacBook Pros on sale this weekend, with models available for $100-$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz... Read more

Jobs Board

*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* Retail - Multiple Positions - Apple,...
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 - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Information Security - Security Data...
# Apple Information Security - Security Data Analyst Job Number: 113119545 Austin, Texas, United States Posted: 10-Nov-2017 Weekly Hours: 40.00 **Job Summary** This Read more
*Apple* Retail - Multiple Positions - Apple,...
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.