Jan 93 Challenge
 Volume Number: 9 Issue Number: 1 Column Tag: Challenge

# Programmers' Challenge

By Mike Scanlin, MacTech Magazine Regular Contributing Author

Note: Source code files accompanying this article are located on MacTech CD-ROM or source code disks.

## Challenge of the Month: Travelling Salesman

Recent discussions with friends about fuel efficiency reminded me of a problem I once had in a linear algebra class: A travelling salesman needs to visit a set of cities. He can go from any city to any other city and must visit each city exactly once. The question is, what is the optimal order of visitation that minimizes total distance travelled?

The prototype of the function you write is:

```void OptimalPath(numCities,
startCityIndex, citiesPtr,
optimalPathPtr)
unsigned short numCities;
unsigned short  startCityIndex;
Point *citiesPtr;
Point *optimalPathPtr;
Example:

```

## Input:

``` numCities = 6
startCityIndex = 2
*citiesPtr = {1,4}, {2,2}, {2,1}, {5,7}, {4,6}, {2,6}

```

## Output:

``` *optimalPathPtr = {2,1}, {2,2}, {1,4}, {2,6}, {4,6}, {5,7}

```

numCities is a 1-based count of the number of cities to be visited (between 3 and 20, inclusive); startCityIndex is a zero-based index of the city in which the salesman starts ((2,1) in this example); citiesPtr is a pointer to an array of city locations (x and y locations are positive integers from 0 to 32767; each entry in the array is unique - no duplicate cities); optimalPathPtr points to an array (allocated by the caller) that OptimalPath fills in with the coordinates of the cities that the salesman should visit, in the order he should visit them (the first entry will always be citiesPtr[startCityIndex]).

## October Challenge winner!

The winner of the October “Name no one man” palindrome challenge is Stepan Riha (location unknown). His superb solution is overflowing with neat optimization tricks, starting from a good understanding of the problem at hand (right algorithm) and continuing on to efficient implementation details like precomputed multiplication tables (right code). This is a perfect example of what we’re looking for here in the Programmer’s Challenge column. Nice job, Stepan!

Credit is also given to three people who submitted solutions that were relatively close to Stepan’s winning time and code size: Leonid Braginsky (22% slower; Brighton, MA), Allen Stenger (37% slower; Gardena, CA) and Eric Slosser (40% slower; Berkeley, CA).

To those people who submitted solutions that use a precomputed lookup table containing every palindrome from 0 to 999,999,999 I have three words: Get a life. I can hear the moaning from here, “That’s not fair! He said the primary criteria was speed!” Well, that’s true, it is. However, there comes a point in programming when you have to sacrifice speed for reasonable code size and/or memory usage. It is my personal opinion that taking 30K+ to do what Stepan does in 426 bytes is not the right approach.

I have received several requests for statistics regarding the Programmer’s Challenge. Readers want to know how many entries I get, what test data I use, what the winning time and code size is, etc. I can and will satisfy some of those requests. Unfortunately, I can’t publish my test bench program or test data because of space constraints. But I can tell you that I generally test with several hand calculated values to verify that functions are returning correct results. Then I call each function several thousand times with random (same random seed for everyone; it’s fair) as well as average case inputs. I test edge cases but I don’t dwell on these. I’m not trying to trick people (a couple of people asked me about negative palindromes since I used long instead of unsigned long in my baseNumber parameter-it was an oversight on my part, not a trick); I’m just looking for good, fast code that handles a wide range of inputs.

Having said that, here are some numbers that I can share with you: The “pegs” challenge received 9 entries, “spell CAT” received 21 entries and “palindromes” received 22 entries. Of the 22 entries for palindromes, one gave bogus results, one gave a divide-by-zero error and three others took way too long (or were caught in some kind of infinite loop) so I stopped timing them. Of the remaining entries, the slowest one was 4.3 times slower than the winner and the largest one that didn’t use a huge lookup table was 2.8 times larger than the winner.

## Name No one man

```/* 1 */
/* FindNthPalindrome by Stepan Riha
*
* This algorithm works with the following
* fact in mind: An N-digit string can form
* 9 * 10^((N-1)/2) palindromes:
*
* Odd N: Even N:
* 1st  100..000..001100..0000..001
* 2nd  100..010..001100..0110..001
* 3rd  100..020..001100..0220..001
* 100.......001 100........001
* 10th 100..090..001100..0990..001
* 11th 100..101..001100..1001..001
* 12th 100..111..001100..1111..001
* ............. ..............
* last-1 999..989..999   999..9889..999
* last 999..999..999999..9999..999
*
* Speedups are achieved bye replacing x*10
* with (x<<1 + x<<3) and by doing conversions
* requireing x/10 and x%10 on my own
* approximating 1/10 with 3/32. Also, I use
* a lookup table for powers of 10, etc.
*/

/* Precomputed values:
palins10 is an array of 9*10^((n-1)/2)
multpow10is a multiplication table of
10^n (last row is all 10^9
because of integer overflow)
*/

static long palins10[] = {
9L, 9L, 90L, 90L, 900L, 900L, 9000L,
9000L, 90000L, 90000L, 900000L
};

static long multpow10[100] = {
0L, 1L, 2L, 3L, 4L,
5L, 6L, 7L, 8L, 9L,
0L, 10L, 20L, 30L, 40L,
50L, 60L, 70L, 80L, 90L,
0L, 100L, 200L, 300L, 400L,
500L, 600L, 700L, 800L, 900L,
0L, 1000L, 2000L, 3000L, 4000L,
5000L, 6000L, 7000L, 8000L, 9000L,
0L, 10000L, 20000L, 30000L, 40000L,
50000L, 60000L, 70000L, 80000L, 90000L,
0L, 100000L, 200000L, 300000L, 400000L,
500000L, 600000L, 700000L, 800000L,
900000L,
0L, 1000000L, 2000000L, 3000000L, 4000000L,
5000000L, 6000000L, 7000000L, 8000000L,
9000000L,
0L, 10000000L, 20000000L, 30000000L,
40000000L, 50000000L, 60000000L, 70000000L,
80000000L, 90000000L,
0L, 100000000L, 200000000L, 300000000L,
400000000L, 500000000L, 600000000L,
700000000L, 800000000L, 900000000L,
0L, 1000000000L, 1000000000L, 1000000000L,
1000000000L, 1000000000L, 1000000000L,
1000000000L, 1000000000L, 1000000000L
};

/* (x * 10) */
#define Times10(x) ((x<<1) + (x<<3))
/* x *= 10 */
#define MultBy10(x) x += x + (x<<3)
/* (x * 3 / 32) */
#define ApproxDiv10(x) ((x>>4)+(x>>5))
/* (x/2) */
#define Half(x) ((x)>>1)

long FindNthPalindrome(long baseNumber, short n);

long FindNthPalindrome(register long base, short n)
{
register long num, dig, mult10, remain,
*lop, *hip, *multpow;
long   buffer[16];

if (base >= 1000000000L)
return -1L;

if (!(num = n))
/* 0th palindrome doesn't exist */
return base;

/* palindrome =
*     n-th palindrome > baseNumber */

/* Find dig = (number of digits in
* baseNumber) - 1
* Find how many dig-digit palindromes
* are smaller than the baseNumber
*/

if (base < 10) { /* baseNumber <= 9 */
dig = 0;
/* all 1-digit strings are
* palindromes (duh!)
*/
num += base - 1;
}
else { /* baseNumber is >= 10 */
/* Convert baseNumber to string.
* This is faster than using /1
* and %10
*/
lop = buffer; dig = -1;
while (base) {
remain = base; base = 0;
goto division1;
while (mult10) {
base += mult10;
remain -= Times10(mult10);
division1:
mult10 = ApproxDiv10(remain);
}
if (remain >= 10) {
base++; remain -= 10;
}
*lop++ = remain; dig++;
}
/* Find how many dig-digit palindromes
* are smaller than this string
* Start searching from the middle
*/
hip = (lop = buffer) + Half(dig+1);
lop += (base = Half(dig));
multpow = multpow10;
for(; base >= 0 && *lop==*hip;
hip++, lop--, multpow += 10, base--)
num += multpow[*hip];
if (base >= 0) {
if (*hip > *lop)
num--;
for(; base >= 0;
hip++, multpow += 10, base--)
num += multpow[*hip];
}
num -= multpow[-9];
} /* if (baseNumber < 10) */

/* palindrome =
*num-th palindrome > 10^dig */

/* Find how many digits the palindrome
* will have
*/
hip = (lop = palins10) + dig;
while (num >= 0)
num -= *hip++;
num += *(--hip);
dig = hip - lop;
if (dig >= 9)
/* i.e. baseNumber > 999999999
* (dig is always <= 10) */
return -1L;

/* palindrome =
*num-th dig-digit palindrome */

/* Find the num-th dig-digit paindrome.
* Calculate final palindrome string. This
* is faster than using /10 and %10
* Use lop and hip to point in the correct
* row in the multiplication table
* Start filling digits from the middle of
* the string
*/
base = Half(dig+1);
hip = (lop = multpow10) + Times10(base);
base = Half(dig);
lop += Times10(base);
base = 0L;
while (num) {
remain = num; num = 0;
goto division2;
while (mult10) {
num += mult10;
remain -= Times10(mult10);
division2:
mult10 = ApproxDiv10(remain);
}
if (remain >= 10) {
num++; remain -= 10;
}
base += lop[remain];
if (lop < hip)
/* don't count middle digit twice */
base += hip[remain];
lop -= 10; hip += 10;
}
lop = multpow10 + 1;
base += *lop;
if (dig) {
MultBy10(dig);
base += lop[dig];
}

return base;
}
```

## The Rules

Here’s how it works: Each month there will be a different programming challenge presented here. First, you must write some code that solves the challenge. Second, you must optimize your code (a lot). Then, submit your solution to MacTech Magazine (formerly MacTutor). A winner will be chosen based on code correctness, speed, size and elegance (in that order of importance) as well as the postmark of the answer. In the event of multiple equally desirable solutions, one winner will be chosen at random (with honorable mention, but no prize, given to the runners up). The prize for the best solution each month is \$50 and a limited edition “I won the MacTech Magazine Programming Challenge” T-shirt (not to be found in stores).{1}

In order to make fair comparisons between solutions, all solutions must be in ANSI compatible C. All entries will be tested with the FPU and 68020 flags turned off in THINK C. When timing routines, the latest version of THINK C will be used (with ANSI Settings plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you optimize for a different C compiler.

The solution and winners for this month’s Programmers’ Challenge will be published in the issue two months later. All submissions must be received by the 15th day of the month printed on the front of this issue.

All solutions should be marked “Attn: Programmers’ Challenge Solution” and sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or e-mail. If you send via snail mail, please include a disk with the solution and all related files (including contact information). See page 2 for information on “How to Contact Xplain Corporation.”

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month and all entries are the property of MacTech Magazine upon submission. The submission falls under all the same conventions of an article submission.

{1} The prize is subject to change in the event of production problems.

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