TweetFollow Us on Twitter

Aug 92 Challenge
Volume Number:8
Issue Number:4
Column Tag:Programmers' Challenge

Programmers' Challenge

By Mike Scanlin, MacTutor Regular Contributing Author

Welcome to Programmers’ Challenge of the Month wherein each month you will find an interesting programming problem and get the chance to win an insanely great prize, not to mention get your name in print in this prestigious magazine to show all your wannabe friends.

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 this month will appear in the October issue). The deadline for submitting a solution is a postmark of September 10, 1992.

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 the staff page at the front of the magazine 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.

Also, if you have any great ideas for future programming challenges send them in, too.

1 The prize is subject to change in the event of production problems.

The Scene

Contestant #1

“I can write that routine in 200 bytes and 700 cycles.”

Contestant #2:

“I can do it in 180 bytes.”

Contestant #1

“150 bytes and 500 cycles.”

Contestant #2:

<silence>

Announcer:

“Contestant #1, write that routine!”

This month’s Challenge

You have a piece of wood with a 13 x 13 array of holes drilled into it, 1 inch apart (169 holes total, covering one square foot). Into these holes you place 3 to 100 pegs. You then take a rubber band and surround all the pegs and let go. What pegs does the rubber band touch and what is the area inside the rubber band?

The input to your function is a short, numPegs, a pointer to an array of Points, pegsPtr. The output is a short, numEdgePegs, an array of Points, edgePegs (which can be in any order) and a Fixed, area. Here is the prototype:

void BandedPegs(numPegs, pegsPtr, numEdgePegsPtr, edgePegsPtr, areaPtr)
short numPegs;
Point *pegsPtr;
short *numEdgePegsPtr;
Point *edgePegsPtr;
Fixed *areaPtr;
Example:

Input:

 numPegs = 7
 *pegsPtr = {6,6}, {8,5}, {6,7}, {5,6}, {7,7}, {6,5}, {6,9}

Output:

 *numEdgePegsPtr = 5
 *edgePegsPtr = {8,5}, {5,6}, {7,7}, {6,5}, {6,9}
 *areaPtr = 6.0

Good luck! Ready, set, go!

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

NTFS 14.3.318 - $19.95
This latest version supports the new macOS 10.12 Sierra! NTFS breaks down the barriers between Windows and OS X. Paragon NTFS effectively solves the communication problems between the Mac system and... Read more
iFFmpeg 6.2.2 - 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
ForeverSave 2.1.6 - Universal auto-save...
ForeverSave auto-saves all documents you're working on while simultaneously doing backup versioning in the background. Lost data can be quickly restored at any time. Define your preferred time... Read more
BetterTouchTool 1.961 - Customize Multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
EtreCheck 3.1.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
Together 3.7 - Store and organize all of...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Features Smart storage. With simple drag-and-drop... Read more
Together 3.7 - Store and organize all of...
Together helps you organize your Mac, giving you the ability to store, edit and preview your files in a single clean, uncluttered interface. Features Smart storage. With simple drag-and-drop... Read more
EtreCheck 3.1.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
Postbox 5.0.9 - Powerful and flexible em...
Postbox is a new email application that helps you organize your work life and get stuff done. It has all the elegance and simplicity of Apple Mail, but with more power and flexibility to manage even... Read more
DiskCatalogMaker 6.5.16 - Catalog your d...
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... Read more

Latest Forum Discussions

See All

Enneas Saga lets you lead your own demon...
Defend the land of Enneas Continent from the forces of evil in the new fantasy MMORPG from Lyto Mobi: Enneas Saga. Can’t wait? No problem. It’s available to download now on Android devices. | Read more »
Great zombie games in the spirit of Dead...
Dead Rising 4 arrives tomorrow, giving enthusiasts a fresh chance to take selfies with zombies and get up to other ridiculous end-of-the-world shenanigans. To really get into the spirit of things, we've gone and gathered the best zombie games that... | Read more »
Amateur Surgeon 4 Guide: Advanced tips a...
Amateur Surgeon 4 is still tackling the competition at the top of the App Store charts, so if you haven't tried it out yet, you should probably do that right away. If you've been at it for a while, though, perhaps you're ready to start expanding... | Read more »
Amateur Surgeon 4 Guide: Become the worl...
It's time to wield your trusty pizza cutter again, as Amateur Surgeon has returned with a whole fresh set of challenges (and some old, familiar ones, too). Starting anew isn't easy, especially when all you have at your disposal is a lighter, the... | Read more »
Le Parker: Sous Chef Extraordinaire (Ga...
Le Parker: Sous Chef Extraordinaire 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »
Telltale Games really is working on a Gu...
Telltale Games' next episodic adventure is indeed Guardians of the Galaxy. A document tied to the voice actors strike suggested that the project was in the work, but now we have direct confirmation following an announcement at the Game Awards that... | Read more »
Amateur Surgeon returns to iOS and Andro...
Amateur Surgeon and its two sequels disappeared from the App Store some time and it was sad days for all. But now, just in time for the holidays, the Adult Swim favorite makes its joyous return in the shape of Amateur Surgeon 4, a remake with... | Read more »
The best board games on mobile
Sometimes you need to ditch all of the high speed, high action games in favor of something a little more traditional. If you don't feel like parting ways from your mobile device, though, there are still plenty of ways to get that old-school fix.... | Read more »
The best Facebook Messenger Instant Game...
Facebook's new Instant Games is now here, meaning you can play games with your friends directly via Facebook. It's a fun new way to connect with friends, of course, but it's also proving to be a solid gaming experience in its own right, with a... | Read more »
You can now play game's on Facebook...
Facebook launched its new Instant Games platform in an exciting new attempt to engage its user base. As a result, you can now play a number of different games directly through Facebook Messenger. All of these games run with HTML5, meaning you play... | Read more »

Price Scanner via MacPrices.net

Slate Tablet Market Share to Fall Below 75% i...
After two years of decline, the tablet market is showing signs of new life as productivity trumps entertainment, and tablets become cost-effective computing devices for both entertainment and... Read more
Yostand Launches Indigogo campaign for iStand...
China-based startup Yostand (meaning ‘your stand’), has announced the launch of its Indigogo campaign for their newly awaited iStand7. This product is a one of a kind iPhone battery case that offers... Read more
Green App – Budget Forecasting Now Available...
Indianapolis, Indiana based CoopToons has announced the release of Green – Budget Forecasting 1.5, an update to their personal budgeting app developed exclusively for iOS devices. Green aims to be a... Read more
New 2016 13-inch 2.0GHz MacBook Pros in stock...
Overstock.com has the non-Touch Bar 13″ MacBook Pros in stock today for $150 off MSRP. Shipping is free: - 13″ 2.0GHz MacBook Pro Space Gray (MLL42LL/A): $1349.99 $150 off MSRP - 13″ 2.0GHz MacBook... Read more
15-inch 2.6GHz Silver Touch Bar MacBook Pro o...
Adorama has the new 2016 15″ 2.6GHz Silver Touch Bar MacBook Pro (MLW72LL/A) in stock and available for $2349 including free shipping. Adorama charges sales tax in NY & NJ only. Their price is $... Read more
13-inch MacBook Airs on sale for up to $180 o...
Overstock.com has 13″ MacBook Airs on sale for up to $180 off MSRP including free shipping: - 13″ 1.6GHz/128GB MacBook Air (MMGF2LL/A): $869.99 $130 off MSRP - 13″ 1.6GHz/256GB MacBook Air (sku... Read more
13-inch 2.5GHz MacBook Pro (Apple refurbished...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros (MD101LL/A) available for $829, or $270 off original MSRP. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook... Read more
Monday roundup of Holiday Mac sales: Up to $3...
Take up to $300 off MSRP on the price of a new Apple Mac at B&H Photo today as part of their Holiday sale. Shipping is free, and B&H charges NY sales tax only. Touch Bar MacBook Pros are in... Read more
12-inch WiFi Apple iPad Pros on sale for up t...
B&H Photo has 12″ WiFi Apple iPad Pros on sale for up to $50 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 12″ Space Gray 32GB WiFi iPad Pro: $749 $50 off MSRP... Read more
9-inch Apple WiFi iPad Pros on sale for $20-$...
B&H Photo has 9.7″ Apple WiFi iPad Pros on sale for $20-$50 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 9″ Space Gray 256GB WiFi iPad Pro: $779.95 $20 off MSRP... Read more

Jobs Board

*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
Lead *Apple* Solutions Consultant - Apple (...
# Lead Apple Solutions Consultant Job Number: 53586123 Pittsburgh, Pennsylvania, United States Posted: Nov. 28, 2016 Weekly Hours: 40.00 **Job Summary** The Lead ASC Read more
*Apple* Retail - Multiple Positions- Plano,...
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- Kansas...
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- Chicago...
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.