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.

 
AAPL
$517.96
Apple Inc.
-3.72
MSFT
$39.75
Microsoft Corpora
+0.57
GOOG
$536.44
Google Inc.
+3.92

MacTech Search:
Community Search:

Software Updates via MacUpdate

Starcraft II: Wings of Liberty 1.1.1.180...
Download the patch by launching the Starcraft II game and downloading it through the Battle.net connection within the app. Starcraft II: Wings of Liberty is a strategy game played in real-time. You... Read more
Sibelius 7.5.0 - Music notation solution...
Sibelius is the world's best-selling music notation software for Mac. It is as intuitive to use as a pen, yet so powerful that it does most things in less than the blink of an eye. The demo includes... Read more
Typinator 5.9 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
MYStuff Pro 2.0.16 - Create inventories...
MYStuff Pro is the most flexible way to create detail-rich inventories for your home or small business. Add items to MYStuff by dragging and dropping existing information, uploading new images, or... Read more
TurboTax 2013.r17.002 - Manage your 2013...
TurboTax guides you through your tax return step by step, does all the calculations, and checks your return for errors and overlooked deductions. It lets you file your return electronically to get... Read more
TrailRunner 3.8.769 - Route planning for...
Note: While the software is classified as freeware, it is actually donationware. Please consider making a donation to help support development. TrailRunner is the perfect companion for runners,... Read more
Flavours 1.1.10 - Create and apply theme...
Flavours is a Mac application that allow users to create, apply and share beautifully designed themes. Classy Give your Mac a gorgeous new look by applying delicious themes! Easy Unleash your... Read more
Spotify 0.9.8.296. - Stream music, creat...
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... Read more
SlingPlayer Plugin 3.3.20.475 - Browser...
SlingPlayer is the screen interface software that works hand-in-hand with the hardware inside the Slingbox to make your TV viewing experience just like that at home. It features an array of... Read more
S.M.A.R.T. for USB and FireWire Drives 0...
S.M.A.R.T. for USB and FireWire Drives is a kernel driver for OS X external usb or firewire drives. It extends the standard driver behaviour by providing access to drive smart data. The interface to... Read more

Latest Forum Discussions

See All

148Apps Live on Twitch: Pivvot’s Looper...
On our latest Twitch stream, we’ll be playing a pair of minimalist arcade games, one that just got a big content update in Pivvot, and another that was inspired by it in 15 Coins. Whitaker Trebella, creator of Pivvot, will discuss the new modes... | Read more »
Word Cubes Review
Word Cubes Review By Jordan Minor on April 15th, 2014 Our Rating: :: SQUARESVILLEUniversal App - Designed for iPhone and iPad Word Cubes is fine, but it is barely any different from any other word game.   | Read more »
PAX East 2014 – Desert Fox: The Battle o...
PAX East 2014 – Desert Fox: The Battle of El Alamein is Coming to iOS Soon Posted by Rob Rich on April 15th, 2014 [ permalink ] Shenandoah Studio has become one of the go-to developers for war games on iOS, with | Read more »
Tank of Tanks Review
Tank of Tanks Review By Carter Dotson on April 15th, 2014 Our Rating: :: TANKS A LOT!iPad Only App - Designed for the iPad This multiplayer game played on a single iPad is simple, chaotic fun.   | Read more »
PAX East 2014 – Dungeon of the Endless J...
PAX East 2014 – Dungeon of the Endless Just Might Have a Shot at an iPad Release Posted by Rob Rich on April 15th, 2014 [ permalink ] I think it’s fair to say that | Read more »
SideSwype Review
SideSwype Review By Carter Dotson on April 15th, 2014 Our Rating: :: ON YOUR SIDEUniversal App - Designed for iPhone and iPad SideSwype is a puzzler that takes inspiration from Threes, but becomes its own incredibly fun game.   | Read more »
PAX East 2014 – Bigfoot Hunter Invites P...
PAX East 2014 – Bigfoot Hunter Invites Players on a Wild and Wooly Photo Safari Posted by Rob Rich on April 15th, 2014 [ permalink ] Yeti. Sasquatch. Wendigo. | Read more »
Dungeon Quest Review
Dungeon Quest Review By Cata Modorcea on April 15th, 2014 Our Rating: :: NO STORY, BUT GOOD FUNUniversal App - Designed for iPhone and iPad Dungeon Quest does a lot of things right, but ultimately forgets about one of the core... | Read more »
Tempo AI and Speek Join Forces to “Kill...
Tempo AI and Speek Join Forces to “Kill the Conference Call PIN” Posted by Rob Rich on April 15th, 2014 [ permalink ] Today Tempo AI, makers of Tempo Smart Calendar, and | Read more »
Fighting Fantasy: Starship Traveller Rev...
Fighting Fantasy: Starship Traveller Review By Jennifer Allen on April 15th, 2014 Our Rating: :: A SIGNIFICANT VOYAGEUniversal App - Designed for iPhone and iPad Continuing the release of Fighting Fantasy titles, Starship Traveller... | Read more »

Price Scanner via MacPrices.net

Save $50 on Mac mini Server
B&H Photo has the 2012 Mac mini Server on sale for $949 including free shipping plus NY sales tax only. Their price is $50 off MSRP. Read more
PhatWare’s “Ultimate Writing App For iOS” Ren...
PhatWare Corp. has announced it has renamed its new WritePro word processing app for iPhone and iPad: WritePad Pro. The decision to change the app’s name to leverages the strong brand awareness and... Read more
Full Resolution Photo Editor Tint Mint 1.0 Re...
California based independent developer, Jeffrey Sun, creator of the iOS app Modern Editor, has released Tint Mint, a new photography app for editing enthusiasts. The app costs a dollar, and it packs... Read more
16GB iPad mini (Apple refurbished) available...
The Apple Store has refurbished 1st generation 16GB iPad minis available for $249 including free shipping. Both black and white models are available. Read more
Save $120 on the 27-inch 3.2GHz Haswell iMac
B&H Photo has the 27″ 3.2GHz iMac on sale for $1679.99 including free shipping plus NY sales tax only. Their price is about $120 off MSRP. Read more
Using a Mac Doesn’t Eliminate The Heartbleed...
Low End Mac’s Dan Knight notes that any time you visit a website with an https: prefix or see that secure lock icon on your browser, some type of security software is busy trying to protect your data... Read more
AirPrint Basics Tutorial Posted
A new Apple Knowledge Base article helps get you started using AirPrint, the Apple protocol that enables instant printing from iPad, iPhone, iPod touch, and Mac without the need to install drivers or... Read more
Speed Tips For Running LibreOffice On The Mac
LibreOffice is my favorite of several free, open-source application suites, and the one I have configured on my Mac as my default app for Word documents that one frequently has to deal with. It also... Read more
Snag a 15-inch Retina MacBook Pro for $115 of...
B&H Photo has 2013 15″ Retina MacBook Pros on sale for up to $115 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.3GHz Retina MacBook Pro: $2489.99... Read more
MacBook Airs on sale for $50 to $100 off MSRP
Several resellers are offering $50-$100 discounts on 11″ and 13″ MacBook Airs today, including Amazon, Best Buy, B&H, and others. See the breakdown of deals on our MacBook Air Price Tracker,... Read more

Jobs Board

Position Opening at *Apple* - Apple (United...
**Job Summary** Every day, business customers come to the Apple Store to discover what powerful, easy-to-use Apple products can do for them. As a Business Leader, Read more
Position Opening at *Apple* - Apple (United...
…challenges of developing individuals, building teams, and affecting growth across Apple Stores. You demonstrate successful leadership ability - focusing on excellence Read more
Position Opening at *Apple* - Apple (United...
…Summary** As a Specialist, you help create the energy and excitement around Apple products, providing the right solutions and getting products into customers' hands. You Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** The Apple Store is a retail environment like no other - uniquely focused on delivering amazing customer experiences. As an Expert, you introduce people Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** Being a Business Manager at an Apple Store means you're the catalyst for businesses to discover and leverage the power, ease, and flexibility of Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.