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

Posterino 4.4 - Create posters, collages...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Chromium 119.0.6044.0 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. List of changes available here. Version for Apple... Read more
Spotify 1.2.21.1104 - 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
Tor Browser 12.5.5 - Anonymize Web brows...
Using Tor Browser you can protect yourself against tracking, surveillance, and censorship. Tor was originally designed, implemented, and deployed as a third-generation onion-routing project of the U.... Read more
Malwarebytes 4.21.9.5141 - Adware remova...
Malwarebytes (was AdwareMedic) helps you get your Mac experience back. Malwarebytes scans for and removes code that degrades system performance or attacks your system. Making your Mac once again your... Read more
TinkerTool 9.5 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Paragon NTFS 15.11.839 - Provides full r...
Paragon NTFS breaks down the barriers between Windows and macOS. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS. Write, edit, copy, move, delete files on... Read more
Apple Safari 17 - Apple's Web brows...
Apple Safari is Apple's web browser that comes bundled with the most recent macOS. Safari is faster and more energy efficient than other browsers, so sites are more responsive and your notebook... Read more
Firefox 118.0 - Fast, safe Web browser.
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
ClamXAV 3.6.1 - Virus checker based on C...
ClamXAV is a popular virus checker for OS X. Time to take control ClamXAV keeps threats at bay and puts you firmly in charge of your Mac’s security. Scan a specific file or your entire hard drive.... Read more

Latest Forum Discussions

See All

‘Monster Hunter Now’ October Events Incl...
Niantic and Capcom have just announced this month’s plans for the real world hunting action RPG Monster Hunter Now (Free) for iOS and Android. If you’ve not played it yet, read my launch week review of it here. | Read more »
Listener Emails and the iPhone 15! – The...
In this week’s episode of The TouchArcade Show we finally get to a backlog of emails that have been hanging out in our inbox for, oh, about a month or so. We love getting emails as they always lead to interesting discussion about a variety of topics... | Read more »
TouchArcade Game of the Week: ‘Cypher 00...
This doesn’t happen too often, but occasionally there will be an Apple Arcade game that I adore so much I just have to pick it as the Game of the Week. Well, here we are, and Cypher 007 is one of those games. The big key point here is that Cypher... | Read more »
SwitchArcade Round-Up: ‘EA Sports FC 24’...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for September 29th, 2023. In today’s article, we’ve got a ton of news to go over. Just a lot going on today, I suppose. After that, there are quite a few new releases to look at... | Read more »
‘Storyteller’ Mobile Review – Perfect fo...
I first played Daniel Benmergui’s Storyteller (Free) through its Nintendo Switch and Steam releases. Read my original review of it here. Since then, a lot of friends who played the game enjoyed it, but thought it was overpriced given the short... | Read more »
An Interview with the Legendary Yu Suzuk...
One of the cool things about my job is that every once in a while, I get to talk to the people behind the games. It’s always a pleasure. Well, today we have a really special one for you, dear friends. Mr. Yu Suzuki of Ys Net, the force behind such... | Read more »
New ‘Marvel Snap’ Update Has Balance Adj...
As we wait for the information on the new season to drop, we shall have to content ourselves with looking at the latest update to Marvel Snap (Free). It’s just a balance update, but it makes some very big changes that combined with the arrival of... | Read more »
‘Honkai Star Rail’ Version 1.4 Update Re...
At Sony’s recently-aired presentation, HoYoverse announced the Honkai Star Rail (Free) PS5 release date. Most people speculated that the next major update would arrive alongside the PS5 release. | Read more »
‘Omniheroes’ Major Update “Tide’s Cadenc...
What secrets do the depths of the sea hold? Omniheroes is revealing the mysteries of the deep with its latest “Tide’s Cadence" update, where you can look forward to scoring a free Valkyrie and limited skin among other login rewards like the 2nd... | Read more »
Recruit yourself some run-and-gun royalt...
It is always nice to see the return of a series that has lost a bit of its global staying power, and thanks to Lilith Games' latest collaboration, Warpath will be playing host the the run-and-gun legend that is Metal Slug 3. [Read more] | Read more »

Price Scanner via MacPrices.net

Clearance M1 Max Mac Studio available today a...
Apple has clearance M1 Max Mac Studios available in their Certified Refurbished store for $270 off original MSRP. Each Mac Studio comes with Apple’s one-year warranty, and shipping is free: – Mac... Read more
Apple continues to offer 24-inch iMacs for up...
Apple has a full range of 24-inch M1 iMacs available today in their Certified Refurbished store. Models are available starting at only $1099 and range up to $260 off original MSRP. Each iMac is in... Read more
Final weekend for Apple’s 2023 Back to School...
This is the final weekend for Apple’s Back to School Promotion 2023. It remains active until Monday, October 2nd. Education customers receive a free $150 Apple Gift Card with the purchase of a new... Read more
Apple drops prices on refurbished 13-inch M2...
Apple has dropped prices on standard-configuration 13″ M2 MacBook Pros, Certified Refurbished, to as low as $1099 and ranging up to $230 off MSRP. These are the cheapest 13″ M2 MacBook Pros for sale... Read more
14-inch M2 Max MacBook Pro on sale for $300 o...
B&H Photo has the Space Gray 14″ 30-Core GPU M2 Max MacBook Pro in stock and on sale today for $2799 including free 1-2 day shipping. Their price is $300 off Apple’s MSRP, and it’s the lowest... Read more
Apple is now selling Certified Refurbished M2...
Apple has added a full line of standard-configuration M2 Max and M2 Ultra Mac Studios available in their Certified Refurbished section starting at only $1699 and ranging up to $600 off MSRP. Each Mac... Read more
New sale: 13-inch M2 MacBook Airs starting at...
B&H Photo has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $200 off Apple’s MSRP with prices available starting at only $899. Free 1-2 day delivery is available to most US... Read more
Apple has all 15-inch M2 MacBook Airs in stoc...
Apple has Certified Refurbished 15″ M2 MacBook Airs in stock today starting at only $1099 and ranging up to $230 off MSRP. These are the cheapest M2-powered 15″ MacBook Airs for sale today at Apple.... Read more
In stock: Clearance M1 Ultra Mac Studios for...
Apple has clearance M1 Ultra Mac Studios available in their Certified Refurbished store for $540 off original MSRP. Each Mac Studio comes with Apple’s one-year warranty, and shipping is free: – Mac... Read more
Back on sale: Apple’s M2 Mac minis for $100 o...
B&H Photo has Apple’s M2-powered Mac minis back in stock and on sale today for $100 off MSRP. Free 1-2 day shipping is available for most US addresses: – Mac mini M2/256GB SSD: $499, save $100 –... Read more

Jobs Board

Licensed Dental Hygienist - *Apple* River -...
Park Dental Apple River in Somerset, WI is seeking a compassionate, professional Dental Hygienist to join our team-oriented practice. COMPETITIVE PAY AND SIGN-ON Read more
Sublease Associate Optometrist- *Apple* Val...
Sublease Associate Optometrist- Apple Valley, CA- Target Optical Date: Sep 30, 2023 Brand: Target Optical Location: Apple Valley, CA, US, 92307 **Requisition Read more
*Apple* / Mac Administrator - JAMF - Amentum...
Amentum is seeking an ** Apple / Mac Administrator - JAMF** to provide support with the Apple Ecosystem to include hardware and software to join our team and Read more
Child Care Teacher - Glenda Drive/ *Apple* V...
Child Care Teacher - Glenda Drive/ Apple ValleyTeacher Share by Email Share on LinkedIn Share on Twitter Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.