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

iFFmpeg 6.4.0 - Convert multimedia files...
iFFmpeg is a comprehensive media tool to convert movie, audio and media files between formats. The FFmpeg command line instructions can be very hard to master/understand, so iFFmpeg does all the hard... Read more
Thunderbird 52.2.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
Airfoil 5.6.1 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Apple Remote Desktop Client 3.9.3 - Clie...
Apple Remote Desktop Client is the best way to manage the Mac computers on your network. Distribute software, provide real-time online help to end users, create detailed software and hardware reports... Read more
jAlbum Pro 14.0 - Organize your digital...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. You can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly... Read more
jAlbum 14.0 - Create custom photo galler...
With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code! Beginner-friendly, with pro results - Simply drag and drop photos into groups, choose a design... Read more
Vitamin-R 2.48 - Personal productivity t...
Vitamin-R creates the optimal conditions for your brain to work at its best by structuring your work into short bursts of distraction-free, highly focused activity alternating with opportunities for... Read more
Beamer 3.3 - Stream any movie file from...
Beamer streams to your Apple TV.... Plays any movie file - Just like the popular desktop movie players, Beamer accepts all common formats, codecs and resolutions. AVI, MKV, MOV, MP4, WMV, FLV. To... Read more
Shredo 1.2.2 - $9.99
Shredo is a beautiful, functional file-shredding and privacy scan utility. It permanently shreds files, folders, and external volumes' contents to keep information secure and impossible for anyone to... Read more
Final Draft 10.0.3 - Industry-leading sc...
Final Draft allows you to use your creative energy to focus on the content; let Final Draft take care of the style. Final Draft is the number-one selling application specifically designed for writing... Read more

Latest Forum Discussions

See All

The House of da Vinci (Games)
The House of da Vinci 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Enter The House of Da Vinci, a new must-try 3D puzzle adventure game. Solve mechanical puzzles, discover hidden... | Read more »
Solve the disappearance of history’s gre...
Blue Brain Games invites you to indulge in an immersive hands-on 3D puzzle adventure in similar vein to The Room series, with its debut release The House of Da Vinci. Set during the historic period of the Italian Renaissance (when Leonardo himself... | Read more »
Age of Rivals (Games)
Age of Rivals 3.3 Device: iOS Universal Category: Games Price: $.99, Version: 3.3 (iTunes) Description: Deep civilization-building strategy in a fast-paced card game! | Read more »
Panthera Frontier (Games)
Panthera Frontier 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
Angry Birds Evolution beginner's gu...
Angry Birds changes things up a fair bit in its latest iteration, Angry Birds Evolution. The familiar sling-shot physics mechanics are still there, but the game now features team-based gameplay, RPG elements, and a new top-down view. With all of... | Read more »
Sega Forever is for the retro game fans
Sega is launching a new retro games service titled Sega Forever, in a move that's sure to delight games enthusiasts with a bit of nostalgia. Sega's releasing five classic games for free. The titles include Sonic the Hedgehog, Phantasy Star II,... | Read more »
The Little Acre (Games)
The Little Acre 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Lovely adventure game 'The Little A...
The Little Acre makes its way from PC to iOS today and it's a real charmer. It's a lovely little adventure game set in 1950's Ireland, gorgeously animated in a style slightly reminiscent of old Disney films. The game won a lot of praise for its... | Read more »
Futurama: Worlds of Tomorrow officially...
Futurama: Worlds of Tomorrow arrives next Thursday, and it features . . . Stephen Hawking? Turns out a few of your favorite science super stars, including Bill Nye, Neil DeGrasse Tyson, and George Takei will be making an appearance alongside the... | Read more »
MU Origin’s new update offers exciting c...
MU Origin is kicking off the summer with style. Its latest update is a real doozy, offering up plenty of fresh content. New challenges, some extra help for newcomers, and new costumes are just a few of the things you will find in the new patch. | Read more »

Price Scanner via MacPrices.net

Clearance 2016 MacBook Pros available for up...
B&H Photo has clearance 2016 13″ and 15″ MacBook Pros in stock today and on sale for up to $400 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 15″ 2.7GHz... Read more
Apple Ranks 9th In comScore Top 50 U.S. Digit...
comScore, Inc. has released its monthly ranking of U.S. online activity at the top digital media properties for May 2017 based on data from comScore Media Metrix Multi-Platform. * Entity has... Read more
10.5-inch iPad Pros available for up to $20 o...
B&H Photo has the new 2017 10.5″ iPad Pros available for up to $20 off MSRP including free shipping plus NY & NJ sales tax only: - 64GB iPad Pro WiFi: $649 - 256GB iPad Pro WiFi: $749 - 512GB... Read more
Three Off-The-Beaten-Track iOS Apps That Dese...
One of the great things about using iPads and iPhones is the vast selection of apps available for most anything you want or need to do. The three outlined in this article have been in my core app... Read more
Apple No. 1 Spot In Gartner Top 100 Vendors i...
Gartner, Inc. has unveiled the top global 100 vendors in IT in 2016 based on their revenue across IT (excluding communication services) and component market segments. In the Gartner Global Top 100:... Read more
Clearance iMacs available for up to $300 off...
B&H Photo has clearance 21″ and 27″ Apple iMacs available starting at $949, each including free shipping plus NY & NJ sales tax only: - 27″ 3.3GHz iMac 5K: $1999 $300 off original MSRP - 27″... Read more
1.4GHz Mac mini, refurbished, available for $...
The Apple Store has Apple Certified Refurbished 1.4GHz Mac minis available for $419. Apple’s one-year warranty is included, and shipping is free. Their price is $80 off MSRP, and it’s the lowest... Read more
Free Mixoo iOS Photo Editing App Gets Major U...
Button Software Technology has announced Mixoo 3.0, an important feature update to the company’s photo editor for iOS devices. Mixoo offers amazing ways to edit as well as decorate personal photo... Read more
FNable 2.0 Function Key Enabling Software Get...
Briksoftware has released FNable 2.0 With Touch Bar Support, a major new version of the function key enabling software now compatible with Touch Bar keyboards. FNable’s simplicity that allows users... Read more
Clearance 2016 12-inch Retina MacBooks, Apple...
Apple recently dropped prices on Certified Refurbished 2016 12″ Retina MacBooks, with models now available starting at $1019. Apple will include a standard one-year warranty with each MacBook, and... Read more

Jobs Board

Lead *Apple* Solutions Consultant - Apple I...
…integrity, and trust.Success Metrics/Key Performance Indicators:Quantitative* Year over Year growth in Apple Product and Beyond the Box sales in the assigned Point of Read more
*Apple* Solutions Consultant till v%u00E5r...
…ethics, integrity, and trust.Success Metrics/Key Performance Indicators:QuantitativeYear over Year growth in Apple Product and Beyond the Box sales in the assigned Point Read more
Sr. Software Engineer, *Apple* Retail - App...
Apple Retail is looking for a Software Engineer…You'll work on projects that touch all aspects of Apple Retail Point-of-Sale system, and will leverage your strong Read more
*Apple* Solutions Consultant (Asc) - PT - Cu...
…important role that the ASC serves is that of providing an excellent Apple Customer Experience. Responsibilities include:* Promoting Apple products and solutions Read more
Product Metrics Manager - *Apple* Media Pro...
- Identify blind spots in existing product metrics- Presenting on how Apple Media Products are used and perceived by our customers- Work with data science and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.