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
$102.50
Apple Inc.
+0.25
MSFT
$45.43
Microsoft Corpora
+0.55
GOOG
$571.60
Google Inc.
+2.40

MacTech Search:
Community Search:

Software Updates via MacUpdate

Path Finder 6.5.5 - Powerful, award-winn...
Path Finder is a file browser that combines the familiar Finder interface with the powerful utilities and innovative features. Just a small selection of the Path Finder 6 feature set: Dual pane... Read more
QuarkXPress 10.2.1 - Desktop publishing...
With QuarkXPress, you can communicate in all the ways you need to -- and always look professional -- in print and digital media, all in a single tool. Features include: Easy to Use -- QuarkXPress is... Read more
Skype 6.19.0.450 - Voice-over-internet p...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
VueScan 9.4.41 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
Cloud 3.0.0 - File sharing from your men...
Cloud is simple file sharing for the Mac. Drag a file from your Mac to the CloudApp icon in the menubar and we take care of the rest. A link to the file will automatically be copied to your clipboard... Read more
LibreOffice 4.3.1.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
SlingPlayer Plugin 3.3.20.505 - 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
Get Lyrical 3.8 - Auto-magically adds ly...
Get Lyrical auto-magically add lyrics to songs in iTunes. You can choose either a selection of tracks, or the current track. Or turn on "Active Tagging" to get lyrics for songs as you play them.... Read more
Viber 4.2.2 - Send messages and make cal...
Viber lets you send free messages and make free calls to other Viber users, on any device and network, in any country! Viber syncs your contacts, messages and call history with your mobile device,... Read more
Cocktail 7.6 - General maintenance and o...
Cocktail is a general purpose utility for OS X that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more

Latest Forum Discussions

See All

Rhonna Designs Magic (Photography)
Rhonna Designs Magic 1.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0 (iTunes) Description: Want to sprinkle *magic* on your photos? With RD Magic, you can add colors, filters, light leaks, bokeh, edges,... | Read more »
This Week at 148Apps: August 25-29, 2014
Shiny Happy App Reviews   | Read more »
Qube Kingdom – Tips, Tricks, Strategies,...
Qube Kingdom is a tower defense game from DeNA. You rally your troops – magicians, archers, knights, barbarians, and others – and fight against an evil menace looking to dominate your kingdom of tiny squares. Planning a war isn’t easy, so here are a... | Read more »
Qube Kingdom Review
Qube Kingdom Review By Nadia Oxford on August 29th, 2014 Our Rating: :: KIND OF A SQUARE KINGDOMUniversal App - Designed for iPhone and iPad Qube Kingdom has cute visuals, but it’s a pretty basic tower defense game at heart.   | Read more »
Fire in the Hole Review
Fire in the Hole Review By Rob Thomas on August 29th, 2014 Our Rating: :: WALK THE PLANKUniversal App - Designed for iPhone and iPad Seafoam’s Fire in the Hole looks like a bright, 8-bit throwback, but there’s not enough booty to... | Read more »
Alien Creeps TD is Now Available Worldwi...
Alien Creeps TD is Now Available Worldwide Posted by Ellis Spice on August 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Dodo Master Review
Dodo Master Review By Jordan Minor on August 29th, 2014 Our Rating: :: NEST EGGiPad Only App - Designed for the iPad Dodo Master is tough but fair, and that’s what makes it a joy to play.   | Read more »
Motorsport Manager Review
Motorsport Manager Review By Lee Hamlet on August 29th, 2014 Our Rating: :: MARVELOUS MANAGEMENTUniversal App - Designed for iPhone and iPad Despite its depth and sense of tactical freedom, Motorsport Manager is one of the most... | Read more »
Motorsport Manager – Beginner Tips, Tric...
The world of Motorsport management can be an unforgiving and merciless one, so to help with some of the stress that comes with running a successful race team, here are a few hints and tips to leave your opponents in the dust. | Read more »
CalPal Update Brings the App to 2.0, Add...
CalPal Update Brings the App to 2.0, Adds Lots of New Stuff Posted by Ellis Spice on August 29th, 2014 [ permalink ] | Read more »

Price Scanner via MacPrices.net

Apple now offering refurbished 21-inch 1.4GHz...
The Apple Store is now offering Apple Certified Refurbished 21″ 1.4GHz iMacs for $929 including free shipping plus Apple’s standard one-year warranty. Their price is $170 off the cost of new models,... Read more
Save $50 on the 2.5GHz Mac mini, on sale for...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $300 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
The Rise of Phablets
Carlisle & Gallagher Consulting Group, a businesses and technology consulting firm focused solely on the financial services industry, has released an infographic depicting the convergence of... Read more
Bad Driver Database App Allows Good Drivers t...
Bad Driver Database 1.4 by Facile Group is a new iOS and Android app that lets users instantly input and see how many times a careless, reckless or just plain stupid driver has been added to the... Read more
Eddy – Cloud Music Player for iPhone/iPad Fre...
Ukraine based CapableBits announces the release of Eddy, its tiny, but smart and powerful cloud music player for iPhone and iPad that allows users to stream or download music directly from cloud... Read more
A&D Medical Launches Its WellnessConnecte...
For consumers and the healthcare providers and loved ones who care for them, A&D Medical, a leader in connected health and biometric measurement devices and services, has launched its... Read more
Anand Lal Shimpi Retires From AnandTech
Anand Lal Shimpi, whose AnandTech Website is famous for its meticulously detailed and thoroughgoing reviews and analysis, is packing it in. Lal Shimpi, who founded the tech site at age 14 in 1997,... Read more
2.5GHz Mac mini, Apple refurbished, in stock...
The Apple Store has Apple Certified Refurbished 2.5GHz Mac minis available for $509, $90 off MSRP. Apple’s one-year warranty is included, and shipping is free. Read more
13-inch 2.5GHz MacBook Pro on sale for $999,...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.