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

OS X Yosemite 10.10.2 - Apple's lat...
OS X Yosemite is Apple's newest operating system for Mac. An elegant design that feels entirely fresh, yet inherently familiar. The apps you use every day, enhanced with new features. And a... Read more
Apple iOS 8.1.3 - The latest version of...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
SpamSieve 2.9.19 - Robust spam filter fo...
SpamSieve is a robust spam filter for major email clients that uses powerful Bayesian spam filtering. SpamSieve understands what your spam looks like in order to block it all, but also learns what... Read more
RapidWeaver 6.0.5 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
Duet 1.2.2 - Use your iPad as an externa...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a $14.99 iOS companion app. Version 1.2.2:... Read more
Alfred 2.6 - 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
1Password 5.1 - Powerful password manage...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
GarageSale 6.9.2 - Create outstanding eB...
GarageSale is a slick, full-featured client application for the eBay online auction system. Create and manage your auctions with ease. With GarageSale, you can create, edit, track, and manage... Read more
calibre 2.17 - Complete e-library manage...
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 librarian... Read more
OmniGraffle Pro 6.1.2 - Create diagrams,...
OmniGraffle Pro helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use... Read more

New WOTA: U-Boat Compass ‘Wets’ Your App...
New WOTA: U-Boat Compass ‘Wets’ Your Appetite for WOTA: Wolves of the Atlantic. Posted by Jessica Fisher on January 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Warship Solitaire Review
Warship Solitaire Review By Nadia Oxford on January 27th, 2015 Our Rating: :: A WAR OF NUMBERSUniversal App - Designed for iPhone and iPad Warship Solitaire might lack frills and looks, but it offers some thought provoking... | Read more »
Keep Track of Your Hectic Work Schedule...
Keep Track of Your Hectic Work Schedule With Shifts Posted by Jessica Fisher on January 27th, 2015 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
All Star Quarterback Review
All Star Quarterback Review By Campbell Bird on January 27th, 2015 Our Rating: :: PLAY YOUR PARTUniversal App - Designed for iPhone and iPad Train your way to the Super Bowl in this free-to-play sports management game.   | Read more »
Sentinel 4: Dark Star Adds New Campaign...
Sentinel 4: Dark Star Adds New Campaign and More Posted by Ellis Spice on January 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Wheel & Deal Review
Wheel & Deal Review By Tre Lawrence on January 27th, 2015 Our Rating: :: SIMPLE FUNUniversal App - Designed for iPhone and iPad A simple arcade shooter that has a retro feel.   | Read more »
Join the NAVY in a Big New Update for WW...
Join the NAVY in a Big New Update for WW2: Sandbox. Strategy & Tactics Posted by Jessica Fisher on January 27th, 2015 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Earthworm Alchemy Review
Earthworm Alchemy Review By Campbell Bird on January 27th, 2015 Our Rating: :: FEED THE WORMUniversal App - Designed for iPhone and iPad Feed this funny looking worm and dodge bombs in this charming, free-to-play arcade game.   | Read more »
Graphic Novel App netwars – The Butterfl...
Graphic Novel App netwars – The Butterfly Attack has Received Some New Episodes Posted by Jessica Fisher on January 27th, 2015 [ permalink ] | Read more »
DataVault Password Manager Review
DataVault Password Manager Review By Jennifer Allen on January 27th, 2015 Our Rating: :: SECURE DATA STORAGEUniversal App - Designed for iPhone and iPad Store your passwords and other sensitive information safely, thanks to... | Read more »

Price Scanner via MacPrices.net

Apple Releases New Tranche Of OS Updates For...
Apple has released incremental bugfix and security updates for its most recent Mac and iOS versions. OS X Yosemite 10.10.2 Update Apple says this update includes the following improvements: Resolves... Read more
Samsung To Be Main Supplier Of A9 Chips For i...
Korea’s Maeil Business Newspaper reports that Samsung has beat out its chipmaking rivals, Taiwan’s Qualcomm and TSMC, as supplier of chipsets for the next generations of both its own Galaxy S6 and... Read more
Save up to $340 on iMacs with Apple Certified...
The Apple Store has Apple Certified Refurbished iMacs available for up to $340 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
AppleCare Protection Plans on sale for up to...
B&H Photo has 3-Year AppleCare Warranties on sale for up to $105 off MSRP including free shipping plus NY sales tax only: - Mac Laptops 15″ and Above: $244 $105 off MSRP - Mac Laptops 13″ and... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
3TB AirPort Time Capsule on sale for $349, $5...
B&H Photo has 3TB AirPort Time Capsules on sale for $349 including free shipping plus NY sales tax only. Their price is $50 off MSRP, and it’s the lowest price available for this model (except... Read more
16GB iPad Air 2 on sale for $446, save $53
Walmart has 16GB WiFi iPad Air 2s on sale for $53 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Sale prices available for online orders only, in-... Read more
Save up to $300 on a new Mac, $30 on an iPad,...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
MasterCard Brings Contactless Payment, Apple...
MasterCard, the official card of the Waste Management Phoenix Open, and the PGA TOUR are bringing the latest payment technology to the spectator experience with the introduction of contactless... Read more
Petitioning Dropbox For Mac OS X 10.4 and 10....
Last week Dropbox announced to its users that app support for Mac OS X 10.4 and 10.5 will end May 18 — disappointing news for those of us who are still getting useful service out of older PPC Macs... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
As an ambassador of the Apple brand, the ASC is accountable for driving sales performance by: Connecting with customers. Discovering customers' needs and values. Showing Read more
*Apple* Tree Children's Center is hirin...
Apple Tree Learning Center is Hiring Preschool Teachers! Phoenix Childrens Academy is a national leader in the early childhood education industry and we are currently Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
*Apple* Solutions Consultant - Retail Sales...
As an ambassador of the Apple brand, the ASC is accountable for driving sales performance by: Connecting with customers. Discovering customers' needs and values. Showing Read more
*Apple* Solutions Consultant- Retail Sales -...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Resellers store. The ASCs role is to grow Apple product Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.