TweetFollow Us on Twitter

Oct 92 Challenge
Volume Number:8
Issue Number:6
Column Tag: Programmers' Challenge

Programmers' Challenge

By Mike Scanlin, MacTutor Regular Contributing Author

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

Programming Challenge of the Month - NAME NO ONE MAN

This month’s challenge involves palindromes -- things that read the same backward and forward (like the letters in “name no one man” or “a toyota”). The goal is to write a routine that finds the nth palindrome greater than a given baseNumber (when it’s displayed as a base 10 integer without leading zeros). Our numeric palindromes will only consist of digits from 0 to 9 and will not be larger than 9 digits long (return -1 if the palindrome requested is larger than 999,999,999). The prototype is:

long FindNthPalindrome(baseNumber, n)
 long baseNumber;
 short  n;

Example:

Input:  baseNumber = 107
 n = 3

Output:

 function result = 131

Remember, speed is more important than size. This is a fairly simple programming challenge -- but how fast can you make it?

Congratulations

To Aaron Zick (San Francisco, CA) for winning the very first MacTutor Programming Challenge (rubber banded pegs). Among the submitted solutions yielding correct results, his was the fastest and the second smallest. He will be receiving a cool t-shirt as soon as they are available.

The key to writing a fast routine was knowing that you don’t have to use trig functions to calculate the area of a convex polygon. As William Karsh (Manteno, IL) explained in his well commented solution, the area of a “simply connected, piecewise differentiable” region can be computed as follows: For each segment going around the perimeter, bounded by points p1 to p2, calculate p1.h * (p2.v - p1.v) - p1.v * (p2.h - p1.h). The area is the sum of all of these pieces (you may need to multiply by -1 for orientation). Sorry, William, you had the right idea but your code was twice as large and 5% slower than the winning solution.

Jim Walker (Columbia, SC) deserves mention for the smallest code (half the size of the winning solution) and for reminding us that you can calculate the area of a triangle by using the following macro (which might come in handy in one of your own applications, so keep it in mind): AREA(x, y, z) = ((z.h-y.h) * (y.v-x.v) - (z.v-y.v) * (y.h-x.h)) (the sign will be negative if going from x to y to z involves a left turn). Unfortunately Jim’s easy-to-read and elegant routine was 5% to 25% slower than Aaron’s.

Here’s Aaron’s winning solution to the August Challenge (some comments have been removed for space reasons. Aaron’s complete source is on the source code disk):

/* Max holes per side of the peg board. */
#define HOLES 13
 
void GetPerimeter( Point thePegs[], short 
 numPegs, Point outerPegs[], short 
 sideLast[] );
void GetEdgePegs( Point outerPegs[], short 
 test, short last, Point edgePegs[], 
 short *numEdgePegs );
void CheckEdgePegs( Point edgePegs[], short 
 *numEdgePegs, Point newPeg, short first);
void IntegrateArea( Point edgePegs[], short 
 numEdgePegs, Fixed *area ); 
 
/*****************************************/
/* BandedPegs takes an array of points 
 * representing pegs on a pegboard and 
 * returns an array of points representing 
 * the pegs that would be touched by a 
 * rubber band surrounding as many pegs as  
 * possible. It also returns the area thus               surrounded. 
*/
void BandedPegs( short numPegs, Point thePegs[],
 short *numEdgePegs, Point edgePegs[], Fixed *area )
{
    Point   outerPegs[4*(HOLES-1)+1];
    short   sideLast[4], first, last, i;
 
    if( numPegs > 3 ) {
    
        GetPerimeter( thePegs, numPegs, outerPegs, sideLast );
        
 /* Initialize some variables and march around
  * the sides of the board. */
        *numEdgePegs = first = i = 0;
        do {
 /* If there's at least one new peg along the
  * column tops (bottoms), see which ones contact
  * the rubber band. */
            last = sideLast[i++];
            if( first < last ) {
                GetEdgePegs( outerPegs, first, last, edgePegs,
                 numEdgePegs );
                first = last;
            }
 /* Count all pegs from the last (first) column
  * as edge pegs. */
            last = sideLast[i++];
            while( first < last )
                edgePegs[(*numEdgePegs)++] = outerPegs[first++];
        } while( i < 4 ); /* Repeat for four sides. */
    }
    else { 
      /* With 3 or fewer pegs, all will touch the rubber band. */
        *numEdgePegs = numPegs;
        for( i = 0; i < numPegs; i++ ) edgePegs[i] = thePegs[i];
        if( numPegs < 3 ) {
        /* With less than 3 pegs, area must be 0. */
            *area = 0;
            return;
        }
    }
    
    IntegrateArea( edgePegs, *numEdgePegs, area );
    
 /* If there are more than 3 pegs, and they are all
  * in a straight line (indicated by a zero area),
  * the above algorithm will have counted the interior
  * points twice.  The following will remove the
  * redundant set of interior points.  Note that
  * it's also okay for 3 pegs, but no fewer. */
    if( *area == 0 )
      *numEdgePegs = (*numEdgePegs + 3)/2;
}
 
/*******************************************************/
/* This function finds the pegs which roughly
 * define the four sides of the rubber band. */
 
void GetPerimeter( Point thePegs[], short numPegs,
 Point outerPegs[], short sideLast[] )
{
    short   colmin[HOLES], colmax[HOLES],
            rowmin[HOLES], rowmax[HOLES],
            col, row, col1, col2, n;
 
    for( n = 0; n < HOLES; n++  ) {
        colmin[n] = rowmin[n] = HOLES;
        colmax[n] = rowmax[n] = -1;
    }
 /* Check each peg to see if it sets a new extreme
 * in any row or column. */
    for( n = 0; n < numPegs; n++ ) {
        row = thePegs[n].v;
        col = thePegs[n].h;
        if( col < colmin[row] ) colmin[row] = col;
        if( col > colmax[row] ) colmax[row] = col;
        if( row < rowmin[col] ) rowmin[col] = row;
        if( row > rowmax[col] ) rowmax[col] = row;
    }
 /* Collect the pegs at the tops of each column. */
    n = -1;
    for( col = 0; col < HOLES; col++ ) {
        if( (row = rowmin[col]) < HOLES ) {
            outerPegs[++n].v = row;
            outerPegs[n].h = col;
        }
    }
    sideLast[0] = n;
    col1 = outerPegs[0].h;
    col2 = outerPegs[n].h;
 /* Collect all but the top peg of the last column,
  * from top to bottom. */
    for( row = rowmin[col2] + 1; row <= rowmax[col2]; row++ ) {
        if( colmax[row] == col2 ) {
            outerPegs[++n].v = row;
            outerPegs[n].h = col2;
        }
    }
    sideLast[1] = n;
 /* From last to first, collect the pegs at the
  * bottoms of all but the last column. */
    for( col = col2 - 1; col >= col1; col-- ) {
        if( (row = rowmax[col]) >= 0 ) {
            outerPegs[++n].v = row;
            outerPegs[n].h = col;
        }
    }
    sideLast[2] = n;
 /* Collect all but the bottom peg of the first column,
  * from bottom to top. */
    for( row = rowmax[col1] - 1; row >= rowmin[col1]; row-- ) {
        if( colmin[row] == col1 ) {
            outerPegs[++n].v = row;
            outerPegs[n].h = col1;
        }
    }
    sideLast[3] = n;
}
 
/*******************************************************/
/* This function finds the pegs which would push
 * a rubber band to the left of a line between a
 * given starting point and a given ending point.
 * It counts the starting point (but not the
 * ending point) as such a peg. */
 
void GetEdgePegs( Point outerPegs[], short test, short last,
                  Point edgePegs[], short *numEdgePegs )
{
    Point   testPeg, backPeg, nextPeg;
    short   convex, first;
 
    first = *numEdgePegs;

    backPeg = edgePegs[(*numEdgePegs)++] = outerPegs[test];
    nextPeg = outerPegs[last];
 /* Loop through the array of outerPegs from the
  * one after the starting point to the one just
  * before the ending point. */
    while( ++test < last ) {
        testPeg = outerPegs[test];
 /* See if the path connecting backPeg, testPeg,
  * and nextPeg is convex, straight, or concave. */
        if( (convex = (nextPeg.v-backPeg.v)*(testPeg.h-backPeg.h)
 -(testPeg.v-backPeg.v)*(nextPeg.h-backPeg.h)) >= 0 ) {
 /* If convex or straight, count the test
  * peg as an edge peg. */
            edgePegs[(*numEdgePegs)++] = backPeg = testPeg;
 /* If convex, the rubber band's path will change,
  * so we need to check previous edge pegs to see
  * if they are still edge pegs. */
            if( convex > 0 )
              CheckEdgePegs( edgePegs, numEdgePegs, testPeg, first );
        }
    }
}
 
/*******************************************************/

/* If a peg just added to the list of edge pegs
 * has extended the rubber band, this routine will
 * search backward through the list, throwing out pegs
 * that are no longer contacted, until it finds one
 * that still is. */
 
void CheckEdgePegs( Point edgePegs[], short *numEdgePegs,
                    Point newPeg, short first )
{
    Point   testPeg, backPeg;
    short   test;
 
    test = *numEdgePegs - 1;
 /* Loop backward through the list of edge pegs,
  * starting with the one before that just added,
  * stopping before the first that can't be removed. */
    while( --test > first ) {
        testPeg = edgePegs[test];
        backPeg = edgePegs[test-1];
 /* If the path between newPeg, testPeg,
  * and backPeg is concave, remove the peg. */
        if( (newPeg.v-backPeg.v)*(testPeg.h-backPeg.h)
 -(testPeg.v-backPeg.v)*(newPeg.h-backPeg.h) < 0 )
            edgePegs[test] = edgePegs[--(*numEdgePegs)];
        else
        return;
    }
}
 
/*******************************************************/
 
/* This function integrates the area enclosed
 * by a rubber band. */
 
void IntegrateArea( Point edgePegs[],
 short numEdgePegs, Fixed *area ) 
{
    Point   thePeg, lastPeg;
    long    integral = 0;
    short   i;
 /* Starting and ending with the last peg,
  * integrate double the area under the closed path. */
    lastPeg = edgePegs[numEdgePegs-1];
    for( i = 0; i < numEdgePegs; i++ ) {
        thePeg = edgePegs[i];
        integral += (thePeg.h + lastPeg.h)*(thePeg.v - lastPeg.v);
        lastPeg = thePeg;
    }
 /* Correct a negative integral if the path was
  * counterclockwise. */
    if( integral < 0 ) integral = -integral;
 /* By shifting, simultaneously halve the integral
  * and convert it to a fixed. */
    *area = (Fixed)( integral << 15 );
}

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

FoldersSynchronizer 4.2.1 - Synchronize...
FoldersSynchronizer is a popular and useful utility that synchronizes and backs-up files, folders, disks and boot disks. On each session you can apply special options like Timers, Multiple Folders,... Read more
Simon 4.0.2 - Monitor changes and crashe...
Simon monitors websites and alerts you of crashes and changes. Select pages to monitor, choose your alert options, and customize your settings. Simon does the rest. Keep a watchful eye on your... Read more
Cocktail 8.1.2 - 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
Cyberduck 4.6.4 - FTP and SFTP browser....
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more
Herald 5.0.2 - Notification plugin for M...
Note: Versions 2.1.3 (for OS X 10.7), 3.0.6 (for OS X 10.8), and 4.0.8 (for OS X 10.9) are no longer supported by the developer. Herald is a notification plugin for Mail.app, Apple's Mac OS X email... Read more
DEVONthink Pro 2.8.3 - Knowledge base, i...
Save 10% with our exclusive coupon code: MACUPDATE10 DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research... Read more
Boom 2 1.0.1 - System-wide pro audio app...
Boom 2 is a system-wide volume booster and equalizer app that is designed especially for OS X 10.10 Yosemite. It comes with a smart interface, self-calibrates itself according to your Mac, offers... Read more
Apple Security Update 2015-001 - For OS...
Apple Security Update 2015-001 is recommended for all users and improves the security of OS X. For detailed information about the security content of this update, please visit: http://support.apple.... Read more
Drive Genius 4.0.1 - Powerful system uti...
Drive Genius 4 gives you faster performance from your Mac while also protecting it. The award-winning and improved DrivePulse feature alerts you to hard drive issues before they become major problems... Read more
Yosemite Cache Cleaner 9.0.3 - Clear cac...
Yosemite Cache Cleaner is an award-winning general purpose tool for OS X. YCC makes system maintenance simple with an easy point-and-click interface to many OS X functions. Novice and expert users... Read more

Unlock Sunshine Girl in Ironkill with th...
Unlock Sunshine Girl in Ironkill with this special 148Apps code Posted by Rob Rich on January 29th, 2015 [ permalink ] Robo-fighter Ironkill has been out on iOS a | Read more »
Crossroad Zombies Review
Crossroad Zombies Review By Jordan Minor on January 29th, 2015 Our Rating: :: CROSSWALKING DEADiPad Only App - Designed for the iPad Crossroad Zombies is a rough draft of a cool genre mash-up.   | Read more »
Blood Brothers 2 – Tips, Cheats, and Str...
War is hell: Is it the kind of hell you want to check out? Read our Blood Brothers 2 review to find out! Blood Brothers 2, DeNA’s follow-up to the original Blood Brothers, is an intriguing card collecting / role-playing / strategy hybrid. There’s... | Read more »
Blood Brothers 2 Review
Blood Brothers 2 Review By Nadia Oxford on January 29th, 2015 Our Rating: :: AN AGGRAVATING RELATIVEUniversal App - Designed for iPhone and iPad Blood Brothers 2 is built on a simple, solid foundation, but its free-to-play system... | Read more »
I AM BREAD, the Toast of the Town, is Ro...
Have you ever dreamt of being deliciously gluten-y? Do you feel passionate about Rye and Wheat? The guys at Bossa Studios do and that is why they are bringing I AM BREAD to iOS soon. The loafy app will feature all the new content that is being... | Read more »
Fahrenheit: Indigo Prophecy Remastered R...
Fahrenheit: Indigo Prophecy Remastered Review By Jennifer Allen on January 29th, 2015 Our Rating: Universal App - Designed for iPhone and iPad 10 years after its initial release and Fahrenheit: Indigo Prophecy still feels like a... | Read more »
Evolve: Hunters Quest is a Match-3 That...
Evolve: Hunters Quest is a Match-3 That Has You Hunting Up Some Big Game. Posted by Jessica Fisher on January 29th, 2015 [ permalink ] | Read more »
Destructamundo Review
Destructamundo Review By Jordan Minor on January 29th, 2015 Our Rating: :: WRECKING CREWUniversal App - Designed for iPhone and iPad Destructamundo blows up real good.   | Read more »
The Sandbox Gets Exclusive Update, Adds...
The Sandbox Gets Exclusive Update, Adds Invincible Characters Campagin Posted by Tre Lawrence on January 29th, 2015 [ permalink ] | Read more »
Mean Girls: The Game Review
Mean Girls: The Game Review By Jordan Minor on January 29th, 2015 Our Rating: :: FETCHUniversal App - Designed for iPhone and iPad A Mean Girls tower defense game makes way more sense than you’d think.   | Read more »

Price Scanner via MacPrices.net

Back in stock: Refurbished iPod nanos for $99...
The Apple Store has Apple Certified Refurbished 16GB iPod nanos available for $99 including free shipping and Apple’s standard one-year warranty. That’s $50 off the cost of new nanos. Most colors are... Read more
New Good Management Suite Simplifies Enterpri...
Good Technology has announced the availability of the Good Management Suite, a comprehensive cross-platform solution for organizations getting started with mobile business initiatives. Built on the... Read more
15-inch 2.0GHz Retina MacBook Pro (refurbishe...
The Apple Store has Apple Certified Refurbished previous-generation 15″ 2.0GHz Retina MacBook Pros available for $1489 including free shipping plus Apple’s standard one-year warranty. Their price is... Read more
15-inch 2.5GHz Retina MacBook Pro on sale for...
Amazon has the 15″ 2.5GHz Retina MacBook Pro on sale for $2319.99 including free shipping. Their price is $180 off MSRP, and it’s the lowest price available for this model from any reseller. Read more
iPad Turns Five – The ”Book Mystique
Five years ago this week, the late Steve Jobs took the stage at an Apple special press event to unveil the first Apple iPad — a slab-shaped, hand-holdable device that was to shake the personal... Read more
Sale! 15-inch Retina MacBook Pros for up to $...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for $150 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1889.99... Read more
Apple refurbished Mac minis for up to $150 of...
The Apple Store has restocked Apple Certified Refurbished 2014 Mac minis, with models available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz... Read more
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

Jobs Board

*Apple* Retail - Multiple Positions(US) - Ap...
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
*Apple* Systems Engineer - Pre Sales, Educat...
…is responsible for proactively providing technical expertise to drive sales of Apple solutions into assigned accounts. The SE architects, validates, and assists in 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...
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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.