TweetFollow Us on Twitter

Sep 92 Challenge
Volume Number:8
Issue Number:5
Column Tag:Programmers' Challenge

Programmers' Challenge

By Mike Scanlin, MacTutor Regular Contributing Author

Some things you cannot rush. The aging of a fine wine, the bearing of a child and copying files with Finder 7.0 are all things that take a prescribed amount of time. As much as you'd like to, you just can't accelerate certain processes. Putting together an issue of MacTutor is another such process. Article lead times being what they are, Programming Challenge questions will be separated from their winning solutions by two months. That is, the October issue will have the winning solution for the August Challenge, the November issue will have the winning solution for this September Challenge, and so on. So, for those of you waiting to find out the most efficient way to detect rubber banded pegs, you'll have to wait until next month. In the mean time, here's another Challenge for you to work on.

Programming Challenge of the Month - How many ways can you spell "cat"?

Given an order N (from 2 to 10) of a graph matrix and a character value for each node in the graph, calculate the number of unique paths that correctly spell out a given word (starting from any node). For instance, if N is 3 and the nodes are C, T, C, A, R, A, T, A and C, your input graph looks like figure 1.

Given an input word, say "CAT", you start at each of the 9 nodes and see how many unique paths there are that spell out "CAT". In this example, there are two solutions: (1,1), (2,1), (3,1) and (3,3), (3,2), (3,1). If the input word is "CAR", then there are four solutions: (1,1), (2,1), (2,2) and (1,3), (2,3), (2,2) and (3,3), (2,3), (2,2) and (3,3), (3,2), (2,2). For the input word "CATARACT" there are eight solutions.

Each path may cross any node any number of times but you cannot go diagonally from node to node, nor can you use the same node twice in a row (in the event of two letters next to each other in the input word that are the same). Don't worry about case sensitivity (assume everything is upper or lower case). The input word length is from 1 to 255 (a PString).

The goal is to find the number of unique paths (returned as a long). Here's the prototype:

long CountPaths(order, nodeValuesPtr, inputWordPtr)
short order;
char  *nodeValuesPtr;
StringPtr inputWordPtr;



order = 3

*nodeValuesPtr = "CTCARATAC"

*inputWordPtr = "\pCAT"


function result = 2

The winning solution will be the one that is (1) most correct, (2) fastest, (3) smallest (code size), and (4) elegant (in approximately that order of importance).

All solutions should be marked "Attn: Challenge Solution" and sent either via AppleLink or mail to Xplain Corporation (see page 2 for contact information).

And if you have any great ideas for future programming challenges send them in, too.

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 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 MacTutor 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. 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 a month’s Programmers’ Challenge will be published in the issue two months later (i.e., the solutions for August will appear in the October issue). The deadline for submitting a solution is a postmark of the 5th day of the month after the month printed on the front of this issue (i.e., the challenge in the August issue’s due date is October 5th).

All solutions should be marked “Attn: Programmers’ Challenge Solution” and sent to Xplain Corporation 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.”

MacTutor reserves the right to publish any solution entered in the Programming Challenge of the Month and all entries are the property of MacTutor 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

The best GIF making apps
Animated GIFs have exploded in popularity recently which is likely thanks to a combination of Tumblr, our shorter attention spans, and the simple fact they’re a lot of fun. [Read more] | Read more »
The best remote desktop apps for iOS
We've been sifting through the App Store to find the best ways to do computer tasks on a tablet. That gave us a thought - what if we could just do computer tasks from our tablets? Here's a list of the best remote desktop apps to help you use your... | Read more »
Warhammer 40,000: Freeblade guide - How...
Warhammer 40,000: Freebladejust launched in the App Store and it lets you live your childhood dream of blowing up and slashing a bunch of enemies as a massive, hulking Space Marine. It's not easy being a Space Marine though - and particularly if... | Read more »
Gopogo guide - How to bounce like the be...
Nitrome just launched a new game and, as to be expected, it's a lot of addictive fun. It's called Gopogo, and it challenges you to hoparound a bunch of platforms, avoiding enemies and picking up shiny stuff. It's not easy though - just like the... | Read more »
Sago Mini Superhero (Education)
Sago Mini Superhero 1.0 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0 (iTunes) Description: KAPOW! Jack the rabbit bursts into the sky as the Sago Mini Superhero! Fly with Jack as he lifts impossible weights,... | Read more »
Star Wars: Galaxy of Heroes guide - How...
Star Wars: Galaxy of Heroes is all about collecting heroes, powering them up, and using them together to defeat your foes. It's pretty straightforward stuff for the most part, but increasing your characters' stats can be a bit confusing because it... | Read more »
The best cooking apps (just in time for...
It’s that time of year again, where you’ll be gathering around the dinner table with your family and a huge feast in front of you. [Read more] | Read more »
Square Rave guide - How to grab those te...
Square Rave is an awesome little music-oriented puzzle game that smacks of games like Lumines, but with its own unique sense of gameplay. To help wrap your head around the game, keep the following tips and tricks in mind. [Read more] | Read more »
Snowboard Party 2 (Games)
Snowboard Party 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Crowned the best snowboarding game available on the market, Snowboard Party is back to fulfill all your adrenaline needs in... | Read more »
One Button Travel (Games)
One Button Travel 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: “To cut a long story short, If you like interactive fiction, just go buy this one.” - “Oozes the polish that... | Read more »

Price Scanner via

Holiday weekend Mac sales roundup: B&H Ph...
B&H Photo continues to have all new Macs on sale for up to $500 off MSRP as part of their Black Friday/Holiday weekend sale. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina... Read more
iMobie Releases its Ace iOS Cleaner PhoneClea...
iMobie Inc. has announced the new update of PhoneClean 4, its iOS cleaner designed to reclaim wasted space on iPhone/iPad for use and keep the device fast. Alongside, iMobie hosts a 3-day giveaway of... Read more
U.S. Cellular Offering iPad Pro
U.S. Cellular today announced that it is offering the new iPad Pro with Wi-Fi + Cellular, featuring a 12.9-inch Retina display with 5.6 million pixels — the most ever in an iOS device. U.S. Cellular... Read more
Newegg Canada Unveils Black Friday Deals for...
Newegg Canada is offering more than 1,000 deep discounts to Canadian customers this Black Friday, available now through Cyber Monday, with new deals posted throughout the week. “Black Friday is... Read more
Black Friday: Macs on sale for up to $500 off...
BLACK FRIDAY B&H Photo has all new Macs on sale for up to $500 off MSRP as part of their early Black Friday sale including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $... Read more
Black Friday: Up to $125 off iPad Air 2s at B...
BLACK FRIDAY Walmart has the 16GB iPad Air 2 WiFi on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available): - 16GB iPad Air 2 WiFi: $399, save $... Read more
Black Friday: iPad mini 4s on sale for $100 o...
BLACK FRIDAY Best Buy has iPad mini 4s on sale for $100 off MSRP on their online store for Black Friday. Choose free shipping or free local store pickup (if available): - 16GB iPad mini 4 WiFi: $299.... Read more
Black Friday: Apple Watch for up to $100 off...
BLACK FRIDAY Apple resellers are offering discounts and bundles with the purchase of an Apple Watch this Black Friday. Below is a roundup of the deals being offered by authorized Watch resellers:... Read more
Black Friday: Target offers 6th Generation iP...
BLACK FRIDAY Save $40 to $60 on a 6th generation iPod touch at Target with free shipping or free local store pickup (if available). Sale prices for online orders only, in-store prices may vary: -... Read more
Black Friday: Walmart and Target offer iPod n...
BLACK FRIDAY Walmart has the 16GB iPod nano (various colors) on sale for $119.20 on their online store for a limited time. That’s $30 off MSRP. Choose free shipping or free local store pickup (if... Read more

Jobs Board

*Apple* Site Security Manager - Apple (Unite...
# Apple Site Security Manager Job Number: 42975010 Culver City, Califo ia, United States Posted: Oct. 2, 2015 Weekly Hours: 40.00 **Job Summary** The Apple Site Read more
WiSE *Apple* Pay Quality Engineer - Apple (...
# WiSE Apple Pay Quality Engineer Job Number: 44313381 Santa Clara Valley, Califo ia, United States Posted: Nov. 13, 2015 Weekly Hours: 40.00 **Job Summary** Join our Read more
Holiday Retail Associate with *Apple* Knowl...
…and assertive.Someone who can troubleshoot iOS devices (iPhone and iPad) and Apple Mail issues.Someone who can offer solutions.Someone who can work weekends.Someone with Read more
*Apple* Systems Engineer (Mclean, VA and NYC...
Summary:Assist in providing strategic direction and technical leadership within the Apple portfolio, including desktops, laptops, and printing environment. This person 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.