TweetFollow Us on Twitter

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)
 /* to big to start with */
 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];
 }
 /* adjust for no leading zero */
 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;
 }
 /* adjust for no leading zero */  
 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:

Software Updates via MacUpdate

Four apps to help improve your Super Bow...
Super Bowl Sunday is upon us, and whether you’re a Panthers or a Broncos fan you’re no doubt gearing up for it. [Read more] | Read more »
LooperSonic (Music)
LooperSonic 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: LooperSonic is a multi-track audio looper and recorder that will take your loops to the next level. Use it like a loop pedal to... | Read more »
Space Grunts guide - How to survive
Space Grunts is a fast-paced roguelike from popular iOS developer, Orange Pixel. While it taps into many of the typical roguelike sensibilities, you might still find yourself caught out by a few things. We delved further to find you some helpful... | Read more »
Dreii guide - How to play well with othe...
Dreii is a rather stylish and wonderful puzzle game that’s reminiscent of cooperative games like Journey. If that sounds immensely appealing, then you should immediately get cracking and give it a whirl. We can offer you some tips and tricks on... | Read more »
Kill the Plumber World guide - How to ou...
You already know how to hop around like Mario, but do you know how to defeat him? Those are your marching orders in Kill the Plumber, and it's not always as easy as it looks. Here are some tips to get you started. This is not a seasoned platform... | Read more »
Planar Conquest (Games)
Planar Conquest 1.0 Device: iOS Universal Category: Games Price: $12.99, Version: 1.0 (iTunes) Description: IMPORTANT: Planar Conquest is compatible only with iPad 3 & newer devices, iPhone 5 & newer. It’s NOT compatible with... | Read more »
We talk to Cheetah Mobile about its plan...
Piano Tiles 2 is a fast-paced rhythm action high score chaser out now on iOS and Android. You have to tap a series of black tiles that appear on the screen in time to the music, being careful not to accidentally hit anywhere else. Do that and it's... | Read more »
Ultimate Briefcase guide - How to dodge...
Ultimate Briefcase is a simple but tricky game that’s highly dependent on how fast you can react. We can still offer you a few tips and tricks on how to survive though. Guess what? That’s exactly what we’re going to do now. Take it easy [Read more... | Read more »
SoundPrism Link Edition (Music)
SoundPrism Link Edition 1.0 Device: iOS Universal Category: Music Price: $4.99, Version: 1.0 (iTunes) Description: ***Introductory price for a the first few days after launch - if you're reading this, get it while it's fresh out of... | Read more »
Pre-register now for hack and slasher An...
Fincon, which won Facebook's Studio to Watch award in 2015, has announced that pre-registration is now open for the massive 3.0 update for its award-winning hack and slasher Angel Stone. Angel Stone is a post-apocalyptic action RPG in which the... | Read more »

Price Scanner via MacPrices.net

iPads on sale at Target: $100 off iPad Air 2,...
Target has WiFi iPad Air 2s and iPad mini 4s on sale for up to $100 off MSRP on their online store for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for... Read more
Target offers Apple Watch for $100 off MSRP
Target has Apple Watches on sale for $100 for a limited time. Choose free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: - Apple... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and shipping is free... Read more
Macs available for up to $300 off MSRP, $20 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, and... Read more
Watch Super Bowl 50 Live On Your iPad For Fre...
Watch Super Bowl 50 LIVE on the CBS Sports app for iPad and Apple TV. Get the app and then tune in Sunday, February 7, 2016 at 6:30 PM ET to catch every moment of the big game. The CBS Sports app is... Read more
Two-thirds Of All Smart Watches Shipped In 20...
Apple dominated the smart watch market in 2015, accounting for over 12 million units and two-thirds of all shipments according to Canalys market research analysts’ estimates. Samsung returned to... Read more
12-inch 1.2GHz Retina MacBooks on sale for up...
B&H Photo has 12″ 1.2GHz Retina MacBooks on sale for $180 off MSRP. Shipping is free, and B&H charges NY tax only: - 12″ 1.2GHz Gray Retina MacBook: $1499 $100 off MSRP - 12″ 1.2GHz Silver... Read more
12-inch 1.1GHz Gray Retina MacBook on sale fo...
B&H Photo has the 12″ 1.1GHz Gray Retina MacBook on sale for $1199 including free shipping plus NY sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this model... Read more
Apple now offering full line of Certified Ref...
Apple now has a full line of 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... Read more
Free GUI Speedometer – The Ultimate Digital D...
Miami, Florida based RMKapps has announced the official release of GUI Speedometer 1.0, their digital dashboard display developed for iOS devices. GUI Speedometer allows users to track their precise... Read more

Jobs Board

*Apple* Subject Matter Expert - Experis (Uni...
This position is for an Apple Subject Matter Expert to assist in developing the architecture, support and services for integration of Apple devices into the domain. Read more
*Apple* Macintosh OSX - Net2Source Inc. (Uni...
…: * Work Authorization : * Contact Number(Best time to reach you) : Skills : Apple Macintosh OSX Location : New York, New York. Duartion : 6+ Months The associate would Read more
Computer Operations Technician ll - *Apple*...
# Web Announcement** Apple Technical Liaison**The George Mason University, Information Technology Services (ITS), Technology Support Services, Desktop Support Read more
Restaurant Manager - Apple Gilroy Inc./Apple...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
Simply Mac *Apple* Specialist- Service Repa...
Simply Mac is the largest premier retailer of Apple products in the nation. In order to support our growing customer base, we are currently looking for a driven Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.