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

Microsoft OneNote 15.29 - Free digital n...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
Spotify 1.0.44.100. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
SpamSieve 2.9.27 - 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
VueScan 9.5.62 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Fantastical 2.3.2 - Create calendar even...
Fantastical 2 is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
PCalc 4.4.4 - Full-featured scientific c...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more
Alfred 3.2.1 - Quick launcher for apps a...
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
OmniPlan 3.6 - Robust project management...
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Backblaze 4.2.0.990 - Online backup serv...
Backblaze is an online backup service designed from the ground-up for the Mac. With unlimited storage available for $5 per month, as well as a free 15-day trial, peace of mind is within reach with... Read more
AppDelete 4.3.1 - $7.99
AppDelete is an uninstaller that will remove not only applications but also widgets, preference panes, plugins, and screensavers along with their associated files. Without AppDelete these associated... Read more

Latest Forum Discussions

See All

Galaxy on Fire 3 and four other fantasti...
Galaxy on Fire 3 - Manticore brings the series back for another round of daring space battles. It's familiar territory for folks who are familiar with the franchise. If you've beaten the game and are looking to broaden your horizons, might we... | Read more »
The best apps for your holiday gift exch...
What's that, you say? You still haven't started your holiday shopping? Don't beat yourself up over it -- a lot of people have been putting it off, too. It's become easier and easier to procrastinate gift shopping thanks to a number of apps that... | Read more »
Toca Hair Salon 3 (Education)
Toca Hair Salon 3 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Winter comes to Darkwood as Seekers Note...
MyTona, based in the chilly Siberian city of Yakutsk, has brought a little festive fun to its hidden object game Seekers Notes: Hidden Mystery. The Christmas update introduces some new inhabitants to players, and with them a chance to win plenty of... | Read more »
Bully: Anniversary Edition (Games)
Bully: Anniversary Edition 1.03.1 Device: iOS Universal Category: Games Price: $6.99, Version: 1.03.1 (iTunes) Description: *** PLEASE NOTE: This game is officially supported on the following devices: iPhone 5 and newer, iPod Touch... | Read more »
PINE GROVE (Games)
PINE GROVE 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: A pine grove where there are no footsteps of people due to continuous missing cases. The case is still unsolved and nothing has... | Read more »
Niantic teases new Pokémon announcement...
After rumors started swirling yesterday, it turns out there is an official Pokémon GO update on its way. We’ll find out what’s in store for us and our growing Pokémon collections tomorrow during the Starbucks event, but Niantic will be revealing... | Read more »
3 reasons why Nicki Minaj: The Empire is...
Nicki Minaj is as business-savvy as she is musically talented and she’s proved that by launching her own game. Designed by Glu, purveyors of other fine celebrity games like cult favorite Kim Kardashian: Hollywood, Nicki Minaj: The Empire launched... | Read more »
Clash of Clans is getting its own animat...
Riding on its unending wave of fame and success, Clash of Clans is getting an animated web series based on its Clash-A-Rama animated shorts.As opposed to the current shorts' 60 second run time, the new and improved Clash-A-Rama will be comprised of... | Read more »
Leaks hint at Pokémon GO and Starbucks C...
Leaked images from a hub for Starbucks employees suggests that a big Pokémon GO event with the coffee giant could begin this very week. The images appeared on Reddit and hint at some exciting new things to come for Niantic's smash hit game. | Read more »

Price Scanner via MacPrices.net

New 2016 13-inch Touch Bar MacBook Pros in st...
B&H Photo has stock of new 2016 Apple 13″ Touch Bar MacBook Pro models, each including free shipping plus NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro Space Gray: $1999 - 13″ 2.... Read more
New 2016 15″ Touch Bar MacBook Pros in stock...
B&H Photo has new 2016 Apple 15″ Touch Bar MacBook Pro models in stock today including free shipping plus NY sales tax only: - 15″ 2.7GHz Touch Bar MacBook Pro Space Gray: $2799 - 15″ 2.7GHz... Read more
DietSensor App Targeting Diabetes and Obesity...
DietSensor, Inc., a developer of smart food and nutrition applications designed to fight diabetes and obesity and help improve overall fitness, has announced the launch of its DietSensor app for... Read more
Holiday 2016 13-inch 2.0GHz MacBook Pro sales...
B&H has the non-Touch Bar 13″ MacBook Pros in stock today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (MLL42LL/A): $1449 $... Read more
Holiday sale: Apple TVs for $51-$40 off MSRP,...
Best Buy has dropped their price on the 64GB Apple TV to $159.99 including free shipping. That’s $40 off MSRP. 32GB Apple TVs are on sale right now for $98 on Sams Club’s online store. That’s $51 off... Read more
12-inch Retina MacBooks, Apple refurbished, n...
Apple has restocked a full line of Certified Refurbished 2016 12″ Retina MacBooks, now available for $200-$260 off MSRP. Refurbished 2015 models are available starting at $929. Apple will include a... Read more
Holiday sale: 12-inch Retina MacBook for $100...
B&H has 12″ Retina MacBooks on sale for $100 off MSRP as part of their Holiday sale. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1199 $100... Read more
Apple refurbished 13-inch MacBook Airs availa...
Apple has Certified Refurbished 13″ MacBook Airs available starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: - 13″ 1.6GHz/8GB/128GB MacBook Air: $849 $... Read more
Apple refurbished iMacs available for up to $...
Apple has 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 available: - 21″ 3.... Read more
Apple’s Education discount saves up to $300 o...
Purchase a new Mac or iPad using Apple’s Education Store 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

Jobs Board

*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
*Apple* Retail - Multiple Positions- Trumbul...
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* Retail - Multiple Positions- Philade...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions- San Ant...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Products Tester Needed - Apple (Unit...
…we therefore look forward to put out products to quality test for durability. Apple leads the digital music revolution with its iPods and iTunes online store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.