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 );
}

 
AAPL
$112.01
Apple Inc.
-0.53
MSFT
$48.14
Microsoft Corpora
-0.31
GOOG
$528.77
Google Inc.
-1.82

MacTech Search:
Community Search:

Software Updates via MacUpdate

MegaSeg 5.9.4 - Professional MP3 DJ appl...
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
Parallels Desktop 10.1.2 - Run Windows a...
Parallels Desktop is simply the world's bestselling, top-rated, and most trusted solution for running Windows applications on your Mac. With Parallels Desktop for Mac, you can seamlessly run both... Read more
GarageSale 6.9.1 - 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
Quicksilver 1.2.2 - 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
Mac DVDRipper Pro 5.0.1 - Copy, backup,...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
ClamXav 2.7 - Free virus checker, based...
ClamXav is a free virus checker for OS X. It uses the tried, tested, and very popular ClamAV open source antivirus engine as a back end. I hope you like and use ClamXav a lot and that it helps keep... Read more
FoldersSynchronizer 4.2 - Synchronize or...
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
Waltr 1.0.6 - Drag-and-drop any media fi...
WALTR is designed to make it easy to upload and convert any music or video file to an iPad or iPhone format for native playback. It supports a huge variety of media file types, including MP3, MP4,... Read more
Tonality Pro 1.1.3 - Professional-grade...
Tonality Pro gives you the power to create stunning and dramatic black & white images. This is a complete monochrome image editor with more than 150 one-click style presets, totally unique... Read more
OS X NTP Security Update 1.0 - Addresses...
The OS X NTP Security Update addresses a critical security issue with the software that provides the Network Time Protocol service on OS X, and is recommended for all users. Version 1.0: Initial... Read more

Latest Forum Discussions

See All

Forget the Gloves – It’s a Cage Match in...
Forget the Gloves – It’s a Cage Match in Real Boxing’s Underground Update Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] | Read more »
Who Wore it Best? Best of 2014
It’s the end of the year, so it’s time for some arbitrary internet awards! In this wrap-up episode of Who Wore it Best? we present our winners for the best, worst, and flat-out weirdest cloned games that graced the App Store in 2014. [ Who... | Read more »
Now You Can Explore Mayan Temples in Ass...
Now You Can Explore Mayan Temples in Assassin’s Creed Pirates’ Newest Update Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] | Read more »
Soft Design aims to do free-to-play righ...
They say a team is only as big as its fans and that’s also certainly the case with video games, judging from the sales certain AAA ‘heavyweights’ get year-after-year. Soft Design took that principle as a core design philosophy and worked closely... | Read more »
Bogga Christmas Tree
Bogga Christmas Tree By Amy Solomon on December 23rd, 2014 Our Rating: Universal App - Designed for iPhone and iPad Bogga Christmas Tree allows young children to trim a tree, any time or place.   | Read more »
Opera Coast 4.0 Launches on iOS with 4 N...
Opera Coast 4.0 Launches on iOS with 4 New Features Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Cricket Kids: Christmas Presents
Cricket Kids: Christmas Presents By Amy Solomon on December 23rd, 2014 Our Rating: Universal App - Designed for iPhone and iPad Cricket Kids: Christmas Presents allows children to play with digital toys opened for the Christmas... | Read more »
Lara Croft & Tomb Raider Mobile Bund...
Lara Croft & Tomb Raider Mobile Bundle – Only $4.99 Posted by Jessica Fisher on December 23rd, 2014 [ permalink ] Lara Croft is coming to you in | Read more »
SimCity BuildIt Review
SimCity BuildIt Review By Nadia Oxford on December 23rd, 2014 Our Rating: :: BUILDING AN OK TOMORROWUniversal App - Designed for iPhone and iPad SimCity BuildIt is a competent city-building game, but its free-to-play trappings are... | Read more »
SimCity Buildit – Tips, Tricks, and Stra...
Hello, Budding Mayors Want to know what we made of all this upgrading and inevitable waiting? Check out our SimCity BuildIt review! SimCity BuildIt is a city-building game from EA. Your job as mayor is to build houses for people to live in, industry... | Read more »

Price Scanner via MacPrices.net

Will Apple Build An A-series ARM Processor Po...
In computer terms, it’s been a very long time since the MacBook Air had a major redesign. More than four years have elapsed since Apple recast what had originally been more a pricy boutique device... Read more
Last minute gift idea: Send an Apple Store Gi...
Send an Apple Store Gift Card by email this season, perhaps as a last minute Christmas gift. According to Apple, “Apple Store Gift Cards can be used to purchase Apple hardware and accessories at any... Read more
Share A Prayer Customizable iPhone App Launch...
Just in time for the Christmas holiday, Joe Bellissimo, founder of Share A Prayer, Inc., has announced the launch of Share A Prayer, a new iPhone app that allows Christians all over the world to... Read more
Holiday sale prices on MacBooks, $150 off sel...
 Best Buy has two MacBooks on sale today for $150 off MSRP. Both models are available for free instant in-store pickup, or choose free shipping if you aren’t concerned with receiving it by Christmas... Read more
Holiday sale prices up to $200 off on new Mac...
 B&H Photo is offering sale prices on new Macs ranging up to $200 off MSRP plus NY sales tax only. The following models qualify for free overnight delivery if ordered by 4pm ET on Dec 23rd: - 27... Read more
Apple offers free in store pickup and setup t...
Don’t want to wait for Apple to ship your order? Choose local store pickup when ordering from The Apple Store Online. Choose between shipping to your home address or local Apple Store pickup during... Read more
Apple Supply Chain Gears Up To Begin New MacB...
Digitimes’ Aaron Lee and Joseph Tsai report that with a pilot production to be completed by the year end 2014, mass production of Apple’s next-generation 12-inch MacBook Air is expected to ramp up in... Read more
Apple Releases OS X NTP Security Update For Y...
Apple has released the OS X NTP Security Update patch for OS X Mountain Lion v10.8.5, OS X Mavericks v10.9.5, OS X Yosemite v10.10.1. Interestingly OS X 10.7 Lion is not addressed by this update,... Read more
Strategy Analytics: Big Shakeup In Tablet App...
The global tablet processor market grew 30 percent year-on-year to reach $1.2 billion in Q3 2013, according to the Strategy Analytics Handset Component Technologies service report, “Tablet Apps... Read more
iFixIt Posts “How to Solder: A Beginner’s Gui...
iFixIt blogger Julia says: Sometimes, repairing electronics requires more than just spudgering up a few connectors and swapping out the offending parts. Sometimes batteries are soldered to the... Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Store Leader Program (US) - Apple, I...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on experience, Read more
Project Manager, *Apple* Financial Services...
**Job Summary** Apple Financial Services (AFS) offers consumers, businesses and educational institutions ways to finance Apple purchases. We work with national and Read more
*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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.