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;

Example:

Input:

order = 3

*nodeValuesPtr = "CTCARATAC"

*inputWordPtr = "\pCAT"

Output:

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.

 
AAPL
$100.85
Apple Inc.
+0.32
MSFT
$45.07
Microsoft Corpora
-0.26
GOOG
$584.58
Google Inc.
-2.28

MacTech Search:
Community Search:

Software Updates via MacUpdate

Tidy Up 3.0.15.0 - Find duplicate files...
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
Parallels Desktop 10.0 - Run Windows app...
Parallels Desktop is simply the world's bestselling, top-rated, and most trusted solution for running Windows applications on your Mac. With Parallels Desktop for Mac, you can seamlessly run both... Read more
Apple Final Cut Pro X 10.1.3 - Professio...
Apple Final Cut Pro X is a professional video editing solution.Completely redesigned from the ground up, Final Cut Pro adds extraordinary speed, quality, and flexibility to every part of the post-... Read more
Apple Compressor 4.1.3 - Adds power and...
Compressor adds power and flexibility to Final Cut Pro X export. Customize output settings, work faster with distributed encoding, and tap into a comprehensive set of delivery features. Powerful... Read more
Chromium 36.0.1985.143 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. FreeSMUG-Free OpenSource Mac User Group build is... Read more
Macgo Blu-ray Player 2.10.6.1691 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple Motion 5.1.2 - Create and customiz...
Apple Motion is designed for video editors, Motion 5 lets you customize Final Cut Pro titles, transitions, and effects. Or create your own dazzling animations in 2D or 3D space, with real-time... Read more
A Better Finder Rename 9.39 - File, phot...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
PopChar X 6.6 - Floating window shows av...
PopChar X helps you get the most out of your font collection. With its crystal-clear interface, PopChar X provides a frustration-free way to access any font's special characters. Expanded... Read more
MacUpdate Desktop 6.0.2 - Install Mac ap...
MacUpdate Desktop 6 brings seamless 1-click installs and version updates to your Mac. With a free MacUpdate account and MacUpdate Desktop 6, Mac users can now install almost any Mac app on macupdate.... Read more

Latest Forum Discussions

See All

Frontier Heroes Review
Frontier Heroes Review By Andrew Fisher on August 20th, 2014 Our Rating: :: BLAZES NO TRAILSUniversal App - Designed for iPhone and iPad Despite awesome visuals and great music, Frontier Heroes just doesn’t quite deliver enough fun... | Read more »
Echo Prime is Now on Sale for $0.99
Echo Prime is Now on Sale for $0.99 Posted by Jessica Fisher on August 20th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Star Realms Review
Star Realms Review By Andrew Fisher on August 20th, 2014 Our Rating: :: A STAR IS BORNUniversal App - Designed for iPhone and iPad Star Realms is an excellent adaptation of an outstanding deck-builder. With great visuals and an... | Read more »
This. Is. SPRINGFIELD! War comes to The...
This. Is. SPRINGFIELD! | Read more »
One Tap RPG Review
One Tap RPG Review By Campbell Bird on August 20th, 2014 Our Rating: :: DUNGEON SLIDERUniversal App - Designed for iPhone and iPad This casual arcade game introduces some very light rpg elements into its fantasy-themed pachinko... | Read more »
Goodbye Paywall – Table Tennis Touch Eli...
Goodbye Paywall – Table Tennis Touch Eliminates In-App Purchases Posted by Jessica Fisher on August 20th, 2014 [ permalink ] | Read more »
Go to Bed – An Interview With Touchfight...
Touchfight Games is an exciting new indie studio that was co-formed between game journalist and author Nathan Meunier, artist Leonard Kenyon, and programmer Jon Kenyon. Their debut game Go To Bed will be released this fall, and with all the... | Read more »
Assault Vector Review
Assault Vector Review By Rob Thomas on August 19th, 2014 Our Rating: :: SIMPLE STRATEGYUniversal App - Designed for iPhone and iPad While this hex-based warp ride is fine in theory, Assault Vector is a bit too simple to be... | Read more »
Tom Hanks’ Hanx Writer has Taken the App...
Tom Hanks’ Hanx Writer has Taken the App Store by Storm Posted by Jessica Fisher on August 19th, 2014 [ permalink ] iPad Only App - Designed for the iPad | Read more »
It Came from Canada: Galaxy Dash
With its use of well-established tropes like endless flying and sci-fi space shooting, the upcoming Galaxy Dash: Race to the Outer Run most likely won’t confound expectations. However, with its robust amount of opportunities for fun player... | Read more »

Price Scanner via MacPrices.net

Best Buy’s College Student Deals: $100 off Ma...
Take an additional $100 off all MacBooks and iMacs, $50 off iPad Airs and iPad minis, at Best Buy Online with their College Students Deals Savings, valid through September 6th. Anyone with a valid .... Read more
MacBook Airs on sale for $100 off MSRP, free...
B&H Photo has three 2014 MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for Laptops... Read more
Razer Taipan Mouse For Gamers And Non-Gamers...
If you’re a serious gamer on either Mac or Windows PCs, a serious gaming mouse is a necessity for first-tier performance. However, even if like me you’re not much of a gamer, there’s still a strong... Read more
15-inch 2.2GHz MacBook Pro on sale for $1899,...
Adorama has the new 15″ 2.2GHz Retina MacBook Pro on sale for $1899 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP, and it’s the lowest price available for this... Read more
Mid-Size Tablet Shootout Posted: iPad mini wi...
I ‘m curious about how many iPads Apple is actually selling these days. It’s been widely rumored and anticipated that new models with A8 SoCs, 2 GB of RAM, 8 megapixel cameras, and fingerprint... Read more
The 15 Biggest iPad Air Problems And How To A...
What’s this? Fifteen “biggest” problems with the iPad Air? Does that mean there are a lot of smaller problems as well? Say it isn’t so! My old iPad 2 has manifested no hardware problems in three... Read more
TYLT Syncable-Duo, 2-in-1 USB Cable With Appl...
TYLT has introduced the Syncable-Duo, a universal cable solution for charging and syncing data to smartphones and tablets. The Syncable-Duo eliminates the need for multiple cables by incorporating... Read more
Save up to $140 off MSRP with Apple refurbish...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more
2.5GHz Mac mini on sale for $549, save $50
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
Chromebooks Are Actually Sometimes A Better C...
Mac360′s Kate MacKenzie notes that when Steve Jobs announced the post-PC era, he was assuming that the dominant post-PC device would be the iPad he was unveiling, or another Apple product like the... Read more

Jobs Board

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
*Apple* Solutions Consultant - Apple (United...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** Being a Business Manager at an Apple Store means you're the catalyst for businesses to discover and leverage the power, ease, and flexibility of Apple Read more
Position Opening at *Apple* - Apple (United...
**Job Summary** At the Apple Store, you connect business professionals and entrepreneurs with the tools they need in order to put Apple solutions to work in their Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.