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

Dash 3.4.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Civilization VI 1.0.2 - Next iteration o...
Sid Meier’s Civilization VI is the next entry in the popular Civilization franchise. Originally created by legendary game designer Sid Meier, Civilization is a strategy game in which you attempt to... Read more
TurboTax 2016 - Manage your 2016 U.S. ta...
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
Microsoft Office 2016 15.30 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
FotoMagico 5.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more
Acorn 5.6.1 - Bitmap image editor.
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
iMazing 2.1.8 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
Logic Pro X 10.3 - Music creation and au...
Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get creative... Read more
Microsoft Remote Desktop 8.0.37 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
Logic Pro X 10.3 - Music creation and au...
Logic Pro X is the most advanced version of Logic ever. Sophisticated new tools for professional songwriting, editing, and mixing are built around a modern interface that's designed to get creative... Read more

Red's Kingdom (Games)
Red's Kingdom 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Mad King Mac has kidnapped your father and stolen your golden nut! Solve puzzles and battle goons as you explore and battle your... | Read more »
Turbo League Guide: How to tame the cont...
| Read more »
Fire Emblem: Heroes coming to Google Pla...
Nintendo gave us our first look at Fire Emblem: Heroes, the upcoming mobile Fire Emblem game the company hinted at last year. Revealed at the Fire Emblem Direct event held today, the game will condense the series' tactical RPG combat into bite-... | Read more »
ReSlice (Music)
ReSlice 1.0 Device: iOS Universal Category: Music Price: $9.99, Version: 1.0 (iTunes) Description: Audio Slice Machine Slice your audio samples with ReSlice and create flexible musical atoms which can be triggered by MIDI notes or... | Read more »
Stickman Surfer rides in with the tide t...
Stickson is back and this time he's taken up yet another extreme sport - surfing. Stickman Surfer is out this Thursday on both iOS and Android, so if you've been following the other Stickman adventures, you might be interested in picking this one... | Read more »
Z-Exemplar (Games)
Z-Exemplar 1.4 Device: iOS Universal Category: Games Price: $3.99, Version: 1.4 (iTunes) Description: | Read more »
5 dastardly difficult roguelikes like th...
Edmund McMillen's popular roguelike creation The Binding of Isaac: Rebirth has finally crawled onto mobile devices. It's a grotesque dual-stick shooter that tosses you into an endless, procedurally generated basement as you, the pitiable Isaac,... | Read more »
Last week on PocketGamer
Welcome to a weekly feature looking back on the past seven days of coverage on our sister website, PocketGamer. It’s taken a while for 2017 to really get going, at least when it comes to the world of portable gaming. Thank goodness, then, for... | Read more »
ROME: Total War - Barbarian Invasion set...
To the delight of mobile strategy fans, Feral Interactive released ROME: Total War just a few months ago. Now the game's expansion, Barbarian Invasion is marching onto iPads as a standalone release. [Read more] | Read more »
Yuri (Games)
Yuri 1.0 Device: iOS iPhone Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: It's night. Yuri opens his eyes. He wakes up in a strange forest.The small, courageous explorer rides on his bed on casters in this... | Read more »

Price Scanner via MacPrices.net

Laptop Market – Flight To Quality? – The ‘Boo...
Preliminary quarterly PC shipments data released by Gartner Inc. last week reveal an interesting disparity between sales performance of major name PC vendors as opposed to that of less well-known... Read more
IBM and Bell Transform Canadian Enterprise Mo...
IBM and Bell Canada have announced they are joining forces to offer IBM MobileFirst for iOS market-ready enterprise applications for iPad, iPhone or Apple Watch. Bell, Canada’s largest communications... Read more
Otter Products is Closing… For a Day of Givin...
On Thursday, Feb. 9, Otter Products is closing doors to open hearts. In partnership with the OtterCares Foundation, the company is pausing operations for a day so all employees can volunteer with... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for...
Amazon has 2015 15″ 2.2GHz Retina MacBook Pros (MJLQ2LL/A) available for $1799.99 including free shipping. Apple charges $1999 for this model, so Amazon’s price is represents a $200 savings. Read more
Back in stock: Apple refurbished 13-inch Reti...
Apple has Certified Refurbished 2015 13″ Retina MacBook Pros available for up to $360 off original MSRP, starting at $1099. An Apple one-year warranty is included with each model, and shipping is... Read more
CalcTape for macOS 1.2 Adding Machine App for...
schoettler Software has announced CalcTape 1.2, an update to their desktop calculator for macOS. When it comes to adding long columns of numbers, doing complex calculations or playing around with... Read more
New MacBooks And MacBook Pros WIth Kaby Lake...
Digitimes’ Joseph Tsai cites a Chinese-language Economic Daily News (EDN) report that unnamed market watchers are predicting Apple MacBook shipments to grow 10 percent in 2017, and projecting 15... Read more
New 2016 13-inch MacBook Pros on sale for up...
B&H Photo has the new 2016 13″ MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro... Read more
New 15-inch Touch Bar MacBook Pros in stock a...
B&H Photo has the new 2016 15″ Apple Touch Bar MacBook Pros in stock today and on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.7GHz Touch Bar... Read more
Opera Announces Neon Concept Browser For Mac
Opera is inviting users to get a glimpse of what Opera for computers could become with its Opera Neon browser concept. Each Opera Neon feature is described as “an alternate reality” for the Opera... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (Multi-L...
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 - 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* & PC Desktop Support Technician...
Apple & PC Desktop Support Technician job in Stamford, CT We have immediate job openings for several Desktop Support Technicians with one of our most well-known Read more
*Apple* macOS Systems Integration Administra...
…most exceptional support available in the industry. SCI is seeking an Junior Apple macOS systems integration administrator that will be responsible for providing Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.