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.

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more
Iridient Developer 3.2.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
BusyContacts 1.2.7 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
MegaSeg 6.0.5 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
BusyContacts 1.2.7 - Fast, efficient con...
BusyContacts is a contact manager for OS X that makes creating, finding, and managing contacts faster and more efficient. It brings to contact management the same power, flexibility, and sharing... Read more
MegaSeg 6.0.5 - Professional DJ and radi...
MegaSeg is a complete solution for pro audio/video DJ mixing, radio automation, and music scheduling with rock-solid performance and an easy-to-use design. Mix with visual waveforms and Magic... Read more
Iridient Developer 3.2.1 - Powerful imag...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more
iFFmpeg 6.6.1 - Convert multimedia files...
iFFmpeg is a comprehensive media tool to convert movie, audio and media files between formats. The FFmpeg command line instructions can be very hard to master/understand, so iFFmpeg does all the hard... Read more

Latest Forum Discussions

See All

Reigns: Her Majesty guide - how to use e...
Ruling a kingdom isn't easy--doubly so for a queen whose every decision is questioned by the other factions seeking a slice of power. Reigns: Her Majesty builds on the original game's swipey tactics, adding items that you can use to move the story... | Read more »
The best new games we played this week -...
Friday has crept up on us once again, so it's time to honor the best new games we've played over the past few days. This past week was a pretty exciting one, with the debut of lots of beautiful new indies and some familiar faces returning to the... | Read more »
Portal Knights guide- beginner tips and...
Portal Knights is finally making the jump to iOS and Android, and it's already climbing the ranks to become the next big MMO experience on mobile. This sprawling sandbox game will let you pursue any adventure you wish, whether you want to sling... | Read more »
Reigns: Her Majesty guide - how to swipe...
Reigns: Her Majesty is storming the App Store this week, bringing more tinder-esque kingdom building to eager players everywhere. If you've played the original Reigns, you'll know that leading a kingdom is never easy. It's a careful balancing act... | Read more »
Getting Over It (Games)
Getting Over It 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: A game I madeFor a certain kind of person To hurt them. • Climb up an enormous mountain with nothing but a hammer and a pot.•... | Read more »
Reigns: Her Majesty (Games)
Reigns: Her Majesty 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Pocket Legends Adventures guide - how to...
Pocket Legends Adventures is a fun action adventure RPG that takes control when you want it to, but also opens itself for player input, too, if you're looking to tkae a more active role in combat. Regardless of play style, the game can be quite... | Read more »
Portal Knights (Games)
Portal Knights 1.2.4 Device: iOS Universal Category: Games Price: $4.99, Version: 1.2.4 (iTunes) Description: Craft your adventure. Forge your hero. Become the ultimate Portal Knight! | Read more »
Ashworld (Games)
Ashworld 1.3 Device: iOS Universal Category: Games Price: $3.99, Version: 1.3 (iTunes) Description: | Read more »
The best deals on the App Store this wee...
Another week means another roundup of quality bargain games. This week's list features a few games we haven't featured before in our weekly roundups. If you're on the prowl for new games, now's an optimal time to try something completely new for... | Read more »

Price Scanner via MacPrices.net

Beats by Dr. Dre – BeatsX Earphones on sale f...
Best Buy has BeatsX Earphones on sale for $109, $40 off, on their online store. Sale price for online orders only. Choose free store pickup, if available, or choose free shipping. Read more
10″ 64GB WiFi Apple iPad Pros on sale for $59...
MacMall has 10.5″ 64GB Apple iPad Pros on sale for $599 including free shipping. That’s $50 off MSRP and among the lowest prices available for these iPads from any Apple reseller. Read more
15″ 2.2GHz MacBook Pros on sale for $200-$300...
B&H Photo has the 15″ 2.2GHz MacBook Pro available for $200 off MSRP including free shipping plus NY & NJ sales tax only: – 15″ 2.2GHz MacBook Pro (MJLQ2LL/A): $1799 $200 off MSRP Apple has... Read more
Holiday sale: 15″ MacBook Pros for $200-$420...
MacMall has 15″ MacBook Pros on sale for $220-$300 off MSRP, each including free shipping: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2179, $220 off MSRP – 15″ 2.8GHz MacBook Pro Silver (... Read more
Holiday sale: 13″ MacBook Airs for up to $150...
B&H Photo has 13″ MacBook Airs on sale for $100 off MSRP as part of their Holiday sale. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook... Read more
The best Holiday sale prices on 13″ MacBook P...
B&H Photo has 13″ MacBook Pros on sale this weekend, with models available for $100-$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13-inch 2.3GHz... Read more
Holiday sale: 27″ Apple iMacs for $150-$200 o...
MacMall has 27″ iMacs on sale for $150-$200 off MSRP as part of their Holiday sale, each including free shipping: – 27″ 3.8GHz iMac (MNED2LL/A): $2099 $200 off MSRP – 27″ 3.5GHz iMac (MNEA2LL/A): $... Read more
Save on clearance 2016 15″ MacBook Pros, up t...
B&H Photo has clearance 2016 15″ MacBook Pros available for up to $700 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 15″ 2.7GHz Touch Bar MacBook Pro... Read more
Apple offers Certified Refurbished 9.7″ iPads...
Apple has Certified Refurbished 9.7″ WiFi iPads available for $50-$70 off the cost of new models. An Apple one-year warranty is included with each iPad, and shipping is free: – 9″ 32GB WiFi iPad: $... Read more
Save $200-$240 on a 12″ Apple MacBook with Ce...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Information Security - Security Data...
# Apple Information Security - Security Data Analyst Job Number: 113119545 Austin, Texas, United States Posted: 10-Nov-2017 Weekly Hours: 40.00 **Job Summary** This Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.