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

Spotify 1.0.44.100. - Stream music, crea...
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 puts... Read more
Microsoft OneNote 15.29 - Free digital n...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
WALTR 2 2.0.8 - $39.95
WALTR 2 helps you wirelessly drag-and-drop any music, ringtones, videos, PDF, and ePub files onto your iPhone, iPad, or iPod without iTunes. It is the second major version of Softorino's critically-... Read more
Dropbox 16.3.27 - Cloud backup and synch...
Dropbox is an application that creates a special Finder folder that automatically syncs online and between your computers. It allows you to both backup files and keep them up-to-date between systems... Read more
EtreCheck 3.1.5 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
Carbon Copy Cloner 4.1.12 - Easy-to-use...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
VueScan 9.5.62 - 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
SpamSieve 2.9.27 - Robust spam filter fo...
SpamSieve is a robust spam filter for major email clients that uses powerful Bayesian spam filtering. SpamSieve understands what your spam looks like in order to block it all, but also learns what... Read more
Fantastical 2.3.2 - Create calendar even...
Fantastical 2 is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
PCalc 4.4.4 - Full-featured scientific c...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more

Latest Forum Discussions

See All

Track Santa with these three festive app...
Christmas is fast approaching and that means it's time to prepare for Santa's yearly pilgrimage around the globe. Christmas Eve is an exciting time as parents help their kids get ready to welcome Santa. You've got the cookies and milk all planned... | Read more »
Galaxy on Fire 3 and four other fantasti...
Galaxy on Fire 3 - Manticore brings the series back for another round of daring space battles. It's familiar territory for folks who are familiar with the franchise. If you've beaten the game and are looking to broaden your horizons, might we... | Read more »
The best apps for your holiday gift exch...
What's that, you say? You still haven't started your holiday shopping? Don't beat yourself up over it -- a lot of people have been putting it off, too. It's become easier and easier to procrastinate gift shopping thanks to a number of apps that... | Read more »
Toca Hair Salon 3 (Education)
Toca Hair Salon 3 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Winter comes to Darkwood as Seekers Note...
MyTona, based in the chilly Siberian city of Yakutsk, has brought a little festive fun to its hidden object game Seekers Notes: Hidden Mystery. The Christmas update introduces some new inhabitants to players, and with them a chance to win plenty of... | Read more »
Bully: Anniversary Edition (Games)
Bully: Anniversary Edition 1.03.1 Device: iOS Universal Category: Games Price: $6.99, Version: 1.03.1 (iTunes) Description: *** PLEASE NOTE: This game is officially supported on the following devices: iPhone 5 and newer, iPod Touch... | Read more »
PINE GROVE (Games)
PINE GROVE 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: A pine grove where there are no footsteps of people due to continuous missing cases. The case is still unsolved and nothing has... | Read more »
Niantic teases new Pokémon announcement...
After rumors started swirling yesterday, it turns out there is an official Pokémon GO update on its way. We’ll find out what’s in store for us and our growing Pokémon collections tomorrow during the Starbucks event, but Niantic will be revealing... | Read more »
3 reasons why Nicki Minaj: The Empire is...
Nicki Minaj is as business-savvy as she is musically talented and she’s proved that by launching her own game. Designed by Glu, purveyors of other fine celebrity games like cult favorite Kim Kardashian: Hollywood, Nicki Minaj: The Empire launched... | Read more »
Clash of Clans is getting its own animat...
Riding on its unending wave of fame and success, Clash of Clans is getting an animated web series based on its Clash-A-Rama animated shorts.As opposed to the current shorts' 60 second run time, the new and improved Clash-A-Rama will be comprised of... | Read more »

Price Scanner via MacPrices.net

Never Settle for Low Performing Wifi With iOS...
AppYogi Software has announced the release of WiFi Signal Strength Status App 1.0, the company’s new utility developed exclusively for macOS. WiFi Signal Strength Status App features a unique, single... Read more
New 2016 13-inch Touch Bar MacBook Pros in st...
B&H Photo has stock of new 2016 Apple 13″ Touch Bar MacBook Pro models, each including free shipping plus NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro Space Gray: $1999 - 13″ 2.... Read more
New 2016 15″ Touch Bar MacBook Pros in stock...
B&H Photo has new 2016 Apple 15″ Touch Bar MacBook Pro models in stock today including free shipping plus NY sales tax only: - 15″ 2.7GHz Touch Bar MacBook Pro Space Gray: $2799 - 15″ 2.7GHz... Read more
DietSensor App Targeting Diabetes and Obesity...
DietSensor, Inc., a developer of smart food and nutrition applications designed to fight diabetes and obesity and help improve overall fitness, has announced the launch of its DietSensor app for... Read more
Holiday 2016 13-inch 2.0GHz MacBook Pro sales...
B&H has the non-Touch Bar 13″ MacBook Pros in stock today for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.0GHz MacBook Pro Space Gray (MLL42LL/A): $1449 $... Read more
Holiday sale: Apple TVs for $51-$40 off MSRP,...
Best Buy has dropped their price on the 64GB Apple TV to $159.99 including free shipping. That’s $40 off MSRP. 32GB Apple TVs are on sale right now for $98 on Sams Club’s online store. That’s $51 off... Read more
12-inch Retina MacBooks, Apple refurbished, n...
Apple has restocked a full line of Certified Refurbished 2016 12″ Retina MacBooks, now available for $200-$260 off MSRP. Refurbished 2015 models are available starting at $929. Apple will include a... Read more
Holiday sale: 12-inch Retina MacBook for $100...
B&H has 12″ Retina MacBooks on sale for $100 off MSRP as part of their Holiday sale. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1199 $100... Read more
Apple refurbished 13-inch MacBook Airs availa...
Apple has Certified Refurbished 13″ MacBook Airs available starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: - 13″ 1.6GHz/8GB/128GB MacBook Air: $849 $... Read more
Apple refurbished iMacs available for up to $...
Apple has 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 available: - 21″ 3.... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
US- *Apple* Store Leader Program - Apple (Un...
…Summary Learn and grow as you explore the art of leadership at the Apple Store. You'll master our retail business inside and out through training, hands-on Read more
Automotive Detailer - *Apple* Used Autos -...
We are currently conductinginterviews and will be accepting applications for a part-time detailer. Apple Used Autos is a great place to work andstart a career. We Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions- Trumbul...
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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.