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

How to manage your time in Bakery Blitz
It can be tricky, especially when you risk burning your kitchen to the ground if you forget a cake in the oven, so make sure to use these time management tricks to keep your bakery running smoothly. Don’t collect the money right away [Read more] | Read more »
Model 15 (Music)
Model 15 1.0 Device: iOS iPhone Category: Music Price: $29.99, Version: 1.0 (iTunes) Description: The Moog Model 15 App is the first Moog modular synthesizer and synthesis educational tool created exclusively for iPad, iPhone and... | Read more »
How to deal with wind in Angry Birds Act...
Angry Birds Action! is a physics-based puzzler in which you're tasked with dragging and launching birds around an obstacle-littered field to achieve a set objective. It's simple enough at first, but when wind gets introduced things can get pretty... | Read more »
How to get three stars in every level of...
Angry Birds Action! is, essentially, a pinball-style take on the pull-and-fling action of the original games. When you first boot it up, you'll likely be wondering exactly what it is you have to do to get a good score. Well, never fear as 148Apps... | Read more »
The beginner's guide to Warbits
Warbits is a turn-based strategy that's clearly inspired by Nintendo's Advance Wars series. Since turn-based strategy games can be kind of tricky to dive into, see below for a few tips to help you in the beginning. Positioning is crucial [Read... | Read more »
How to upgrade your character in Spellsp...
So you’ve mastered the basics of Spellspire. By which I mean you’ve realised it’s all about spelling things in a spire. What next? Well you’re going to need to figure out how to toughen up your character. It’s all well and good being able to spell... | Read more »
5 slither.io mash-ups we'd love to...
If there's one thing that slither.io has proved, it's that the addictive gameplay of Agar.io can be transplanted onto basically anything and it will still be good fun. It wouldn't be surprising if we saw other developers jumping on the bandwagon,... | Read more »
How to navigate the terrain in Sky Charm...
Sky Charms is a whimsical match-'em up adventure that uses creative level design to really ramp up the difficulty. [Read more] | Read more »
Victorious Knight (Games)
Victorious Knight 1.3 Device: iOS Universal Category: Games Price: $1.99, Version: 1.3 (iTunes) Description: New challenges awaits you! Experience fresh RPG experience with a unique combat mechanic, packed with high quality 3D... | Read more »
Agent Gumball - Roguelike Spy Game (Gam...
Agent Gumball - Roguelike Spy Game 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Someone’s been spying on Gumball. What the what?! Two can play at that game! GO UNDERCOVERSneak past enemy... | Read more »

Price Scanner via MacPrices.net

13-inch 2.5GHz MacBook Pro on sale for $999,...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Apple refurbished 2015 iMacs available for up...
Apple now has a full line of Certified Refurbished 2015 21″ & 27″ iMacs available for up to $350 off MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are... Read more
Indian Smartphone Market Grows Annually by 12...
India’s smartphone market grew by 12 percent year-over-year, with 24.4 million units shipping in Q1 2016. The top five vendors stayed the same, with Samsung in the lead, followed by Micromax, Intex... Read more
Get Notifications When Your Friend’s Phone Ba...
Calgary, Canada based Stonelight Pictures has announced the release of Battery Share 1.0.1, its new utility for iOS 9 supported devices. The company notes that people are spending more time on their... Read more
11-inch 1.6GHz/128GB MacBook Air on sale for...
Amazon has the current-generation 11″ 1.6GHz/128GB MacBook Air (sku MJVM2LL/A) on sale for $749.99 for a limited time. Their price is $150 off MSRP, and it’s the lowest price available for this model... Read more
Price drops on clearance 2015 13-inch MacBook...
B&H Photo has dropped prices on clearance 2015 13″ MacBook Airs by up to $250. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $799, $200... Read more
Mac minis on sale for up to $100 off MSRP
B&H Photo has Mac minis on sale for up to $100 off MSRP including free shipping plus NY sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP - 2.8GHz Mac mini... Read more
13-inch Retina MacBook Pros on sale for up to...
B&H Photo has 13″ Retina MacBook Pros on sale for $130-$200 off MSRP. Shipping is free, and B&H charges NY tax only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1169 $130 off MSRP - 13″ 2.7GHz/... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
SanDisk Half-Terabyte SSD Optimized for Every...
SanDisk Corporation has announced the SanDisk Z410 SSD, a cost-competitive, half-terabyte solid state drive (SSD) that enables manufacturers to design for a broad range of desktop PCs and laptops.... Read more

Jobs Board

Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation WHY YOU LL LIKE IT You ll be the Big Apple You ll solve problems You ll get to show your ability to handle the stress and Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
*Apple* Subject Matter Expert - NTT Data, In...
…in Owings Mills, MD has a 6+ month contract position available for an Apple Subject Matter Expert. TITLE: Apple Subject Matter Expert LOCATION: Owings Mills, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.