Sep 92 Challenge
|Column Tag:||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)
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.
Heres 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 months 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 issues 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.