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:

## Latest Forum Discussions

Fresh From the Land Down Under – The Tou...
After a two week hiatus, we are back with another episode of The TouchArcade Show. Eli is fresh off his trip to Australia, which according to him is very similar to America but more upside down. Also kangaroos all over. Other topics this week... | Read more »
TouchArcade Game of the Week: ‘Dungeon T...
I’m a little conflicted on this week’s pick. Pretty much everyone knows the legend of Dungeon Raid, the match-3 RPG hybrid that took the world by storm way back in 2011. Everyone at the time was obsessed with it, but for whatever reason the... | Read more »
Hello gentle readers, and welcome to the SwitchArcade Round-Up for July 19th, 2024. In today’s article, we finish up the week with the unusual appearance of a review. I’ve spent my time with Hot Lap Racing, and I’m ready to give my verdict. After... | Read more »
Draknek Interview: Alan Hazelden on Thin...
Ever since I played my first release from Draknek & Friends years ago, I knew I wanted to sit down with Alan Hazelden and chat about the team, puzzle games, and much more. | Read more »
The Latest ‘Marvel Snap’ OTA Update Buff...
I don’t know about all of you, my fellow Marvel Snap (Free) players, but these days when I see a balance update I find myself clenching my… teeth and bracing for the impact to my decks. They’ve been pretty spicy of late, after all. How will the... | Read more »
‘Honkai Star Rail’ Version 2.4 “Finest D...
HoYoverse just announced the Honkai Star Rail (Free) version 2.4 “Finest Duel Under the Pristine Blue" update alongside a surprising collaboration. Honkai Star Rail 2.4 follows the 2.3 “Farewell, Penacony" update. Read about that here. | Read more »
‘Vampire Survivors+’ on Apple Arcade Wil...
Earlier this month, Apple revealed that poncle’s excellent Vampire Survivors+ () would be heading to Apple Arcade as a new App Store Great. I reached out to poncle to check in on the DLC for Vampire Survivors+ because only the first two DLCs were... | Read more »
Homerun Clash 2: Legends Derby opens for...
Since launching in 2018, Homerun Clash has performed admirably for HAEGIN, racking up 12 million players all eager to prove they could be the next baseball champions. Well, the title will soon be up for grabs again, as Homerun Clash 2: Legends... | Read more »
‘Neverness to Everness’ Is a Free To Pla...
Perfect World Games and Hotta Studio (Tower of Fantasy) announced a new free to play open world RPG in the form of Neverness to Everness a few days ago (via Gematsu). Neverness to Everness has an urban setting, and the two reveal trailers for it... | Read more »
Meditative Puzzler ‘Ouros’ Coming to iOS...
Ouros is a mediative puzzle game from developer Michael Kamm that launched on PC just a couple of months back, and today it has been revealed that the title is now heading to iOS and Android devices next month. Which is good news I say because this... | Read more »

## Price Scanner via MacPrices.net

Amazon is still selling 16-inch MacBook Pros...
Prime Day in July is over, but Amazon is still selling 16-inch Apple MacBook Pros for \$500-\$600 off MSRP. Shipping is free. These are the lowest prices available this weekend for new 16″ Apple... Read more
Walmart continues to sell clearance 13-inch M...
Walmart continues to offer clearance, but new, Apple 13″ M1 MacBook Airs (8GB RAM, 256GB SSD) online for \$699, \$300 off original MSRP, in Space Gray, Silver, and Gold colors. These are new MacBooks... Read more
Apple is offering steep discounts, up to \$600...
Apple has standard-configuration 16″ M3 Max MacBook Pros available, Certified Refurbished, starting at \$2969 and ranging up to \$600 off MSRP. Each model features a new outer case, shipping is free,... Read more
Save up to \$480 with these 14-inch M3 Pro/M3...
Apple has 14″ M3 Pro and M3 Max MacBook Pros in stock today and available, Certified Refurbished, starting at \$1699 and ranging up to \$480 off MSRP. Each model features a new outer case, shipping is... Read more
Amazon has clearance 9th-generation WiFi iPad...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for \$80-\$100 off MSRP, starting only \$249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Apple is offering a \$50 discount on 2nd-gener...
Apple has Certified Refurbished White and Midnight HomePods available for \$249, Certified Refurbished. That’s \$50 off MSRP and the lowest price currently available for a full-size Apple HomePod today... Read more
The latest MacBook Pro sale at Amazon: 16-inc...
Amazon is offering instant discounts on 16″ M3 Pro and 16″ M3 Max MacBook Pros ranging up to \$400 off MSRP as part of their early July 4th sale. Shipping is free. These are the lowest prices... Read more
14-inch M3 Pro MacBook Pros with 36GB of RAM...
B&H Photo has 14″ M3 Pro MacBook Pros with 36GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 Pro MacBook Pro (... Read more
14-inch M3 MacBook Pros with 16GB of RAM on s...
B&H Photo has 14″ M3 MacBook Pros with 16GB of RAM and 512GB or 1TB SSDs in stock today and on sale for \$150-\$200 off Apple’s MSRP, each including free 1-2 day shipping: – 14″ M3 MacBook Pro (... Read more
Amazon is offering \$170-\$200 discounts on new...
Amazon is offering a \$170-\$200 discount on every configuration and color of Apple’s M3-powered 15″ MacBook Airs. Prices start at \$1129 for models with 8GB of RAM and 256GB of storage: – 15″ M3... Read more

## Jobs Board

*Apple* Systems Engineer - Chenega Corporati...
…LLC,** a **Chenega Professional Services** ' company, is looking for a ** Apple Systems Engineer** to support the Information Technology Operations and Maintenance Read more
Solutions Engineer - *Apple* - SHI (United...
**Job Summary** An Apple Solution Engineer's primary role is tosupport SHI customers in their efforts to select, deploy, and manage Apple operating systems and Read more
*Apple* / Mac Administrator - JAMF Pro - Ame...
Amentum is seeking an ** Apple / Mac Administrator - JAMF Pro** to provide support with the Apple Ecosystem to include hardware and software to join our team and Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple 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