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:

Time Out 2.4 - Break reminder tool with...
Time Out helps remind you to take work breaks throughout the day. It has two kinds of breaks: a "Normal" break, typically for 10 minutes after 50 minutes of work, so you can move about and relax,... Read more
Smultron 10.1.3 - Easy-to-use, powerful...
Smultron 10 is an elegant and powerful text editor that is easy to use. You can use Smultron 10 to create or edit any text document. Everything from a web page, a note or a script to any single piece... Read more
Tor Browser Bundle 7.5.2 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
Yummy FTP Pro 2.0.3 - \$29.99
Yummy FTP Pro is an advanced Mac file transfer app which provides a full-featured professional toolkit combined with blazing speeds and impeccable reliability, so whether you want to transfer a few... Read more
BetterTouchTool 2.412 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Monosnap 3.4.11 - Versatile screenshot u...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
BetterTouchTool 2.412 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Tor Browser Bundle 7.5.2 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
Monosnap 3.4.11 - Versatile screenshot u...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Yummy FTP Pro 2.0.3 - \$29.99
Yummy FTP Pro is an advanced Mac file transfer app which provides a full-featured professional toolkit combined with blazing speeds and impeccable reliability, so whether you want to transfer a few... Read more

## Latest Forum Discussions

How PUBG, Fortnite, and the battle royal...
The history of the battle royale genre isn't a long one. While the nascent parts of the experience have existed ever since players first started killing one another online, it's really only in the past six years that the genre has coalesced into... | Read more »
Around the Empire: What have you missed...
Oh hi nice reader, and thanks for popping in to check out our weekly round-up of all the stuff that you might have missed across the Steel Media network. Yeah, that's right, it's a big ol' network. Obviously 148Apps is the best, but there are some... | Read more »
All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming 1.1.1.536 Device: iOS Universal Category: Games Price: \$1.99, Version: 1.1.1.536 (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »
Hints, tips, and tricks for Empires and...
Empires and Puzzles is a slick match-stuff RPG that mixes in a bunch of city-building aspects to keep things fresh. And it's currently the Game of the Day over on the App Store. So, if you're picking it up for the first time today, we thought it'd... | Read more »
What You Need to Know About Sam Barlow’s...
Sam Barlow’s follow up to Her Story is #WarGames, an interactive video series that reimagines the 1983 film WarGames in a more present day context. It’s not exactly a game, but it’s definitely still interesting. Here are the top things you should... | Read more »
Pixel Plex Guide - How to Build Better T...
Pixel Plex is the latest city builder that has come to the App Store, and it takes a pretty different tact than the ones that came before it. Instead of being in charge of your own city by yourself, you have to work together with other players to... | Read more »
Fortnite Will Be Better Than PUBG on Mob...
Before last week, if you asked me which game I prefer between Fortnite Battle Royale and PlayerUnknown’s Battlegrounds (PUBG), I’d choose the latter just about 100% of the time. Now that we know that both games are primed to hit our mobile screens... | Read more »

## Price Scanner via MacPrices.net

8-Core iMac Pro on sale for \$4699, save \$300
Amazon has the 8-core iMac Pro on sale for \$4699 including free shipping. Their price is \$300 off MSRP, and it’s the currently lowest price available for an iMac Pro. For the latest up-to-date prices... Read more
10″ 512GB WiFi iPad Pros on sale for \$849, sa...
B&H Photo has Space Gray and Rose Gold 10.5″ 512GB WiFi iPad Pros on sale for \$849. Their price is \$150 off MSRP, and it’s the lowest price available for these models, new, from any Apple... Read more
MacBook Pro sale! B&H drops prices on new...
B&H Photo has dropped prices on new 2017 13″ MacBook Pros, with models now on sale for up to \$200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only. Their... Read more
13″ MacBook Airs on sale for \$100-\$150 off MS...
B&H Photo has 13″ MacBook Airs on sale for \$100-\$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): \$899, \$... Read more
Huge iMac sale! Apple reseller now offering 2...
B&H Photo has new 2017 21″ & 27″ iMacs on sale today for up to \$300 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): \$... Read more
Sale! 1.4GHz Mac mini for \$399, \$100 off MSRP
B&H Photo has the 1.4GHz Mac mini on sale for \$399 for a limited time. Their price is \$100 off MSRP, and it’s the lowest price available for a mini from any Apple reseller: – 1.4GHz Mac mini (... Read more
Sale of the year continues as Apple resellers...
Adorama has new 2017 15″ MacBook Pros on sale for \$250-\$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): \$... Read more
Walmart has 9.7″ Apple iPads on sale for \$50-\$80 off MSRP for a limited time. Sale prices are for online orders only, in-store prices may vary: – 9″ 32GB iPad: \$249.99 \$80 off – 9″ 128GB iPad: \$379 \$... Read more
Apple resellers offer 27″ 3.4GHz 5K iMac for...
B&H Photo has new 2017 27″ 3.4GHz iMacs on sale for \$200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.4GHz iMac (MNE92LL/A): \$1599.99 \$200 off... Read more
Certified Refurbished 21″ & 27″ iMacs ava...
Apple has a full line of Certified Refurbished iMacs available for up to \$350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: – 27... Read more

## Jobs Board

*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113587340 Hialeah, Florida, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
*Apple* Watch HW Engineering Program Special...
# Apple Watch HW Engineering Program Specialist Job Number: 113466877 Santa Clara Valley, California, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Read more
*Apple* Technical Specialist - Apple, Inc. (...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*Apple* Information Security Project Manager...
# Apple Information Security Project Manager Job Number: 113440724 Santa Clara Valley, California, United States Posted: 15-Mar-2018 Weekly Hours: 40.00 **Job Read more
Senior Linus Systems Engineer, *Apple* Pay...
# Senior Linus Systems Engineer, Apple Pay Job Number: 113584532 Santa Clara Valley, California, United States Posted: 13-Mar-2018 Weekly Hours: 40.00 **Job Read more