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

Capto 1.2.9 - $29.99
Capto (was Voila) is an easy-to-use app that takes capturing, recording, video and image editing to the next level. With an intelligent file manager and quick sharing options, Capto is perfect for... Read more
Opera 51.0.2830.40 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
GarageSale 7.0.13 - Create outstanding e...
GarageSale is a slick, full-featured client application for the eBay online auction system. Create and manage your auctions with ease. With GarageSale, you can create, edit, track, and manage... Read more
1Password 6.8.7 - Powerful password mana...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
Evernote 7.0.1 - Create searchable notes...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
MacUpdate Desktop 6.2.0 - $20.00
MacUpdate Desktop brings seamless 1-click app 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... Read more
HoudahSpot 4.3.5 - Advanced file-search...
HoudahSpot is a versatile desktop search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the... Read more
EtreCheck 4.0.4 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
WhatsApp 0.2.8361 - Desktop client for W...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
iClock 4.2 - Customize your menubar cloc...
iClock is a menu-bar replacement for Apple's default clock but with 100x features. Have your Apple or Google calendar in the menubar. Have the day, date, and time in different fonts and colors in the... Read more

Latest Forum Discussions

See All

The best games like Florence
Florence is a great little game about relationships that we absolutely adored. The only problem with it is it's over a little too soon. If you want some other games with some emotional range like Florence, check out these suggestions: [Read more] | Read more »
Angry Birds Champions adds cash prizes t...
Collaborating with developer Rovio Entertainment, GSN Games has released a twist on the Angry Birds formula. Angry Birds Champions features the same bird-flinging gameplay, but now you can catapult Red and co for cash. | Read more »
Around the Empire: What have you missed...
148Apps is part of a family. A big family of sites that make sure you're always up to date with all the portable gaming news. Just like a real family, I guess. I don't know, my mum never told me anything about Candy Crush to be fair. [Read more] | Read more »
The Battle of Polytopia Guide - Tips for...
The addition of multiplayer to The Battle of Polytopia has catapulted the game from a fun enough time waster to a fully-fledged 4X experience on your phone. We've been playing quite a few matches over the past week or so, and we've put together a... | Read more »
All the best games on sale for iPhone an...
Hi there, and welcome to our round up of all the best games that are on sale for iOS at the moment. It's not a vintage week in terms of numbers, but I'm pretty sure that every single one of these is worth picking up if you haven't already played... | Read more »
Disc Drivin' 2 Guide - Tips for the...
We're all still playing quite a bit of Disc Drivin' 2 over here at 148Apps, and we've gotten pretty good at it. Now that we've spent some more time with the game and unlocked more powerups, check out some of these more advanced tips: | Read more »
Alto's Odyssey Guide - How to Tackl...
Alto’s Odyssey is a completely stunning and serene runner, but it can also be a bit tricky. Check out these to try and keep your cool while playing this endless runner: Don’t focus too much on tasks [Read more] | Read more »
Here's everything you need to know...
Alto's Odyssey is a really, really good game. If you don't believe me, you should definitely check out our review by clicking this link right here. It takes the ideas from the original Alto's Adventure, then subtly builds on them, creating... | Read more »
Alto's Odyssey (Games)
Alto's Odyssey 1.0.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.1 (iTunes) Description: Just beyond the horizon sits a majestic desert, vast and unexplored. Join Alto and his friends and set off on an endless... | Read more »
Vainglory 5v5: Everything you need to kn...
Vainglory just got bigger. [Read more] | Read more »

Price Scanner via MacPrices.net

Apple AirPods in stock today for $159, free s...
Adorama reports stock of Apple AirPods today for $159 including free shipping, plus pay no sales tax outside of NY & NJ. See our Apple AirPod Price Tracker for the latest prices and stock status... Read more
Saturday Sale: Amazon offers 12″ 1.3GHz MacBo...
Amazon has Silver and Gold 2017 12″ 1.3GHz Retina MacBooks on sale for $250 off MSRP. Shipping is free: – 12″ 1.3GHz Silver MacBook: $1349.99 $250 off MSRP – 12″ 1.3GHz Gold MacBook: $1349.99 $250... Read more
Use your Apple Education discount and save up...
Purchase a new Mac using Apple’s Education discount, and take up to $400 off MSRP. All teachers, students, and staff of any educational institution with a .edu email address qualify for the discount... Read more
Apple Canada offers 2017 21″ and 27″ iMacs fo...
 Canadian shoppers can save up to $470 on the purchase of a 2017 current-generation 21″ or 27″ iMac with Certified Refurbished models at Apple Canada. Apple’s refurbished prices are the lowest... Read more
9″ iPads available online at Walmart for $50...
Walmart has 9.7″ Apple iPads on sale for $50 off MSRP for a limited time. Sale prices are for online orders only, in-store prices may vary: – 9″ 32GB iPad: $279.99 $50 off – 9″ 128GB iPad: $379.99 $... Read more
15″ Apple MacBook Pros, Certified Refurbished...
Save $360-$420 on the purchase of a 2017 15″ MacBook Pro with Certified Refurbished models at Apple. Apple’s refurbished prices are the lowest available for each model from any reseller. An standard... Read more
Amazon restocks MacBook Pros with models avai...
Amazon has restocked 15″ and 13″ Apple MacBook Pros with models on sale for up to $251 off MSRP. Shipping is free. Note that stock of some Macs may come and go (and some sell out quickly), so check... Read more
Lowest price of the year: 15″ 2.8GHz Apple Ma...
Amazon has the 2017 Space Gray 15″ 2.8GHz MacBook Pro on sale today for $251 off MSRP. Shipping is free: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): $2148, $251 off MSRP Their price is... Read more
Apple restocks full line of Certified Refurbi...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
Lowest sale price available for 13″ 1.8GHz Ma...
Focus Camera has the 2017 13″ 1.8GHz/128GB Apple MacBook Air on sale today for $829 including free shipping. Their price is $170 off MSRP, and it’s the lowest price available for a current 13″... Read more

Jobs Board

*Apple* Media Products Commerce Engineering...
# Apple Media Products Commerce Engineering Manager Job Number: 56207285 Santa Clara Valley, California, United States Posted: 26-Jan-2018 Weekly Hours: 40.00 **Job Read more
Digital Platforms Lead, Today at *Apple* -...
# Digital Platforms Lead, Today at Apple Job Number: 56178747 Santa Clara Valley, California, United States Posted: 23-Feb-2018 Weekly Hours: 40.00 **Job Summary** 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* 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.