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

MacUpdate Desktop 6.0.8 - Search and ins...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more
BitTorrent Sync 2.1.1 - Sync files secur...
BitTorrent Sync allows you to sync unlimited files between your own devices, or share a folder with friends and family to automatically sync anything. File transfers are encrypted. Your information... Read more
Quicksilver 1.3.0 - Application launcher...
Quicksilver is a light, fast and free Mac application that gives you the power to control your Mac with keystrokes alone. Quicksilver allows you to find what you need quickly and easily, then act... Read more
iWatermark Pro 1.72 - Easily add waterma...
iWatermark Pro is the essential watermarking app for professional, business, and personal use. iWatermark, is the number 1 and only watermarking tool available for all 4 platforms iPhone/iPad, Mac,... Read more
RapidWeaver 6.3 - Create template-based...
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
Adobe Photoshop CC 2015 16.0.1 - Profess...
Photoshop CC 2015 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Photoshop customer). Photoshop CS6 is still available for purchase (... Read more
Together 3.4.6 - Store and organize all...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Smart storage. With simple drag-and-drop functionality,... Read more
Monosnap 3.1.0 - Versatile screenshot ut...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Capture: Capture full screen, just part of the screen, or a selected window Make your crop area pixel perfect with... Read more
Cocktail 8.5.1 - General maintenance and...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Vienna 3.0.6 :5eaf312: - RSS and Atom ne...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more

.Decluster Zero: Bullet Nocturne (Games...
.Decluster Zero: Bullet Nocturne 1.0.1 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.1 (iTunes) Description: LAUNCH SALE, 40% off for a limited time -- .Decluster is a Guide for Your Bullet-Hell Dream Tonight --... | Read more »
Five Nights at Freddy's 4 has Been...
In keeping with tradition, Five Nights at Freddy's 4 has made its way to the App Store with zero warning fanfare. Honestly I'd be disappointed it if happened any other way at this point. [Read more] | Read more »
Doom & Destiny Advanced (Games)
Doom & Destiny Advanced 2.3.4.0 Device: iOS Universal Category: Games Price: $.99, Version: 2.3.4.0 (iTunes) Description: ---SUPER GIGA LAUNCH DISCOUNT! Get it now for cheap or pay more later!---An additional 143 MB download is... | Read more »
Five Nights at Freddys 4 (Games)
Five Nights at Freddys 4 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: This time, the terror has followed you home. | Read more »
This Week at 148Apps: July 27-31, 2015
Winding Down July With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out... | Read more »
You'll Want to Keep an Eye Out for...
If you're the kind of person who had fun hunting down and completing all the codex puzzles in Assassin's Creed 2, then are you ever in for a treat. The Guides looks like it's going to be a very robust collection of similarily odd, seemingly... | Read more »
Vivid Games has Announced Real Boxing 2...
The original Real Boxing was a pretty impressive bit of fisticuffs, but if the trailer Vivid Games is showing off for GamesCom is any indication Real Boxing 2 is going to be even better. [Read more] | Read more »
PAC-MAN Championship Edition DX - Tips,...
[Read more] | Read more »
Card King: Dragon Wars - Tips, Tricks an...
[Read more] | Read more »
Pac-Man Championship Edition DX has brou...
Bandai Namco has released Pac-Man Championship Edition DX on iOS and Android, which features the classic arcade gameplay that we've all grown to love. Pac-Man Championship Edition DX can be enjoyed in much shorter bursts than the arcade versions... | Read more »

Price Scanner via MacPrices.net

Back to School Time: Outline for iPad Goes Fr...
Sacramento, California based Gorillized Corporation has announced a “Back to School” offer; the iPad version of Outline goes free for August 3-5. Outline is a smart digital notebook for iPad that... Read more
MacBook 12 Retina Pundit’s New Favorite Mac
If you’re eyeing the purchase of a new 12-inch Retina MacBook, but wondering if you can live with a single USB-C port, 2011-level CPU performance, and the unorthodox keyboard, you should find... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
Adorama has the 2015 15″ 2.2GHz Retina MacBook Pro on sale for $184 off MSRP including free shipping plus NY & NJ sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1815 $184 off Adorama will also... Read more
PDF Element Tool Kit For PDF For Windows 10,...
South Surrey, British Columbia based software developer Wondershare has posted an interesting infographic tracking the development of Microsoft’s flagship Windows operating system over the years,... Read more
27-inch 3.5GHz 5K iMac on sale for $81 off MS...
Adorama has the 27″ 3.5GHz 5K iMac on sale for $2218, $81 off MSRP, including a free copy of Apple’s 3-Year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax in NY & NJ... Read more
Back-to-School with Tablet and Smartphone Acc...
Belkin helps you prepare for the coming school year with a wide variety of the latest mobile and tablet accessories to outfit both grade school and college students. The line-up includes charging... Read more
11-inch MacBook Airs on sale for $100 off MSR...
Best Buy has 11-inch MacBook Airs on sale for $100 off MSRP. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: - 11″ 1.6GHz... Read more
iPad Air 2 on sale for up to $100 off MSRP
Best Buy has iPad Air 2s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices available for online... Read more
Sale! 13-inch MacBook Pros on sale for $100 o...
B&H Photo has 13″ MacBook Pros on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.5GHz/500GB MacBook Pro: $999.99 save $100 - 13″ 2.7GHz/128GB Retina... Read more
Sale! Save $100 on 13-inch MacBook Airs this...
B&H Photo has the 13″ 1.6GHz/128GB MacBook Air on sale for $899.99 including free shipping plus NY tax only. Their price is $100 off MSRP, and it’s the lowest price available for this model.... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Infrastructure Engineer - *Apple* /Mac - Hil...
Infrastructure Engineer - Apple /Mac Job Code: 1608 # of openings: 1 Description Our fortune 500 client is looking to hire an experienced Infrastructure Engineer to join Read more
Executive Administrative Assistant, *Apple*...
…supporting presentation development for senior leadership. * User experience with Apple hardware and software is preferred. Additional Requirements The following list Read more
*Apple* Bus Company is now hirin - Apple Bus...
Apple Bus Company is now hiring school bus drivers in the Pettis County area. Class B CDL preferred. Free training provided. No nights or weekends required. Flexible Read more
*Apple* Certified Mac Technician - Updated 6...
…and friendly, hands-on technical support to customers troubleshooting and repairing Apple /Mac products with courtesy, speed and skill. Use your problem-solving skills Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.