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

Tweetbot 2.1 - Popular Twitter client. (...
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
MacPilot 8.0 - Enable over 1,200 hidden...
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
Typinator 6.7 - 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
Adobe Lightroom 6.2 - Import, develop, a...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
ForeverSave 2.1.4 - Universal auto-save...
ForeverSave auto-saves all documents you're working on while simultaneously doing backup versioning in the background. Lost data can be quickly restored at any time. Losing data, caused by... Read more
VueScan 9.5.27 - 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
AirPort Utility 6.3.6 - Set up and manag...
Note: Most recent release available only within OS X 10.11 El Capitan update. Use AirPort Utility to set up and manage your Wi-Fi network and AirPort base stations, including AirPort Express, AirPort... Read more
Quicksilver 1.3.1 - Application launcher...
Quicksilver is a light, fast and free Mac application that gives you the power to control your Mac with keystrokes alone. Quicksilver allows you to find what you need quickly and easily, then act... Read more
Tidy Up (Five Users) 4.1.5 - Find duplic...
Tidy Up is a complete duplicate finder and disk-tidiness utility. With Tidy Up you can search for duplicate files and packages by the owner application, content, type, creator, extension, time... Read more
Mellel 3.4.3 - The word processor of cho...
Mellel is the leading word processor for OS X and has been widely considered the industry standard since its inception. Mellel focuses on writers and scholars for technical writing and multilingual... Read more

Royal Bounty HD (Games)
Royal Bounty HD 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: New World Computing Approved "Hi Guys! looks good so far! keep up the good work. I worked on HoMM 3 and 4 creating all of the... | Read more »
Swords & Crossbones: An Epic Pirate...
Swords & Crossbones: An Epic Pirate Story 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
Camel Up (Games)
Camel Up 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Martian: Bring Him Home (Games)
The Martian: Bring Him Home 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Based on the best selling novel and critically acclaimed film, THE MARTIAN tells the story of Astronaut Mark... | Read more »
This Week at 148Apps: September 21-30, 2...
Leap Into Fall With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above... | Read more »
Tweetbot 4 for Twitter (Social Networki...
Tweetbot 4 for Twitter 4.0 Device: iOS Universal Category: Social Networking Price: $4.99, Version: 4.0 (iTunes) Description: *** 50% off for a limited time. *** | Read more »
Mori (Games)
Mori 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Stop, rewind and unwind with Mori. Time is always running, take a moment to take control. Mori is an action puzzle game about infinitely... | Read more »
100 Years' War (Games)
100 Years' War 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Tower in the Sky (Games)
Tower in the Sky 0.0.60 Device: iOS Universal Category: Games Price: $1.99, Version: 0.0.60 (iTunes) Description: | Read more »
hocus. (Games)
hocus. 1.0.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0.0 (iTunes) Description: New, polished, mind-bending, minimal puzzle game with dozens of levels and extra-ordinary design Features:- Beautifully crafted... | Read more »

Price Scanner via

Is The iPad Pro Really A Serious Laptop Repla...
Probably not, at least for productive professionals and other power users. Steve Jobs declared that we’d entered the “post-PC Era” with the advent of the original iPad in 2010, a phrase we don’t hear... Read more
Wednesday Deal: 13-inch Retina MacBook Pros f...
Adorama has 13″ Retina MacBook Pros on sale for up to $130 off MSRP. Shipping is free, and Adorama charges sales tax for NY & NJ residents only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1199.99 $... Read more
uBar 3.0 for Mac OS X – Custom Dock Replaceme...
Brawer Software has announced the release of uBar 3.0, an important update to their popular app and window manager for Mac OS X. uBar allows users to position it whichever side of the screen they... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros... Read more
27-inch 3.2GHz iMac on sale for $1689, save $...
Adorama has the 27″ 3.2GHz iMac on sale for $1689 including free shipping plus NY & NJ sales tax only. Their price is $110 off MSRP. Read more
12-inch Retina MacBooks on sale for up to $12...
B&H Photo has 12″ Retina MacBooks in stock today and on sale for up to $120 off MSRP. B&H will include free shipping, and there is NY sales tax only: - 12″ 1.1GHz Gray Retina MacBook: $1224 $... Read more
Tablets Shaping Up for Growth in 2016 – Strat...
Observing that Apple, Samsung, and Microsoft have refocused what tablet computers can do, market analysis firm Strategy Analytics believes there is immense opportunity for new and replacement sales... Read more
Apple Interbrand’s Number One Most Valuable G...
Apple and Google hold aced #1 and #2 spots respectively in Interbrand’s 2015 Best Global Brands Report, leading all tech brands that now comprise more than a third of the entire rankings value.... Read more
Apple offering refurbished 2015 13-inch Retin...
Apple is offering Certified Refurbished 2015 13″ Retina MacBook Pros for up to $270 (15%) off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: -... Read more
Apple refurbished 2015 MacBook Airs available...
Apple has Certified Refurbished 2015 11″ and 13″ MacBook Airs (the latest models), available for up to $180 off the cost of new models. An Apple one-year warranty is included with each MacBook, and... Read more

Jobs Board

Touch Validation Design (EE) - *Apple* Watc...
**Job Summary** Help launch next-generation Touch Technologies in Apple products. The Touch Technology team develops cutting-edge Touch solutions and technologies that Read more
WW Sales Strategy & Program Manager, *Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* TV Product Design Internship (Spring...
…the mechanical design effort associated with creating world-class products with the Apple TV PD Group. Responsibilities will include working closely with manufacturing, Read more
Product Design Engineer - *Apple* Watch - A...
**Job Summary** Product Design Engineer - WATCH ( Apple Watch) Be an integral part of a small and visible team of world-class Mechanical Engineers making Apple 's Read more
Senior Software System App Engineer, *Apple*...
**Job Summary** The Apple Watch system application team is looking for great software engineers who are comfortable working across all levels of the software stack. From Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.