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.
Referenced by (2):