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

Rodeo Stampede guide to running a better...
In Rodeo Stampede, honing your skills so you can jump from animal to animal and outrun the herd as long as possible is only half the fun. Once you've tamed a few animals, you can bring them home with you. [Read more] | Read more »
VoxSyn (Music)
VoxSyn 1.0 Device: iOS Universal Category: Music Price: $6.99, Version: 1.0 (iTunes) Description: VoxSyn turns your voice into the most flexible vocal sound generator ever. Instantly following even subtle modulations of pitch and... | Read more »
Catch Battleplans on Google Play from Ju...
Real-time strategy title Battleplans is due for release on Google Play on June 30th, following its release for iOS systems last month. With its simple interface and pretty graphics, the crowd-pleaser brings a formerly overlooked genre out for the... | Read more »
iDoyle: The interactive Adventures of Sh...
iDoyle: The interactive Adventures of Sherlock Holmes - A Scandal in Bohemia 1.0 Device: iOS Universal Category: Books Price: $1.99, Version: 1.0 (iTunes) Description: Special Release Price $1.99 (Normally $3.99) | Read more »
Five popular free apps to help you slim...
Thanks to retail and advertising, we're used to thinking one season ahead. Here we are just a week into the summer and we're conditioned to start thinking about the fall. [Read more] | Read more »
How to ride longer and tame more animals...
It's hard to accurately describe Rodeo Stampede to people who haven't seen it yet. It's like if someone took Crossy Roadand Disco Zoo and put them in a blender, yet with a unique game mechanic that's still simple and fun for anyone. [Read more] | Read more »
Teeny Titans - A Teen Titans Go! Figure...
Teeny Titans - A Teen Titans Go! Figure Battling Game 1.0.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.0 (iTunes) Description: Teeny Titans, GO! Join Robin for a figure battling RPG of epic proportions! TEENY... | Read more »
NinjAwesome: Tips and tricks to be a mor...
Sorry about that headline, but I'm going to go ahead and assume that GameResort would not have named its game NinjAwesome without expecting some of that. It is, in fact, pretty awesome the way it combines an endless runner and old school arcade... | Read more »
Into Mirror (Games)
Into Mirror 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: "Is all that we see or seem, but a dream within a dream?"- Edgar Allan Poe New game by Lemon Jam Studio, the team behind Pursuit... | Read more »
Perchang (Games)
Perchang 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Welcome to Perchang! A test of skill and puzzle solving across 60 stunning levels. | Read more »

Price Scanner via MacPrices.net

15-inch Retina MacBook Pros on sale for $200-...
B&H Photo has 15″ Retina MacBook Pros on sale for up to $210 off MSRP. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799.99 $200 off MSRP - 15″ 2.5GHz... Read more
Mac minis on sale for up to $100 off MSRP
B&H Photo has Mac minis on sale for up to $100 off MSRP including free shipping plus NY sales tax only: - 1.4GHz Mac mini: $449 $50 off MSRP - 2.6GHz Mac mini: $649 $50 off MSRP - 2.8GHz Mac mini... Read more
Clearance 2015 13-inch MacBook Airs available...
B&H Photo has clearance 2015 13″ MacBook Airs available for $300 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $799.... Read more
Apple refurbished Mac minis available for up...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off MSRP - 2.6GHz Mac... Read more
ABBYY TextGrabber: 1,000,000 Installs in 5 Da...
ABBYY, an international OCR technologies provider, has announced that their image-to-text application TextGrabber, got installed 1,000,000 times in just five days while being featured by the App... Read more
New SkinIt Waterproof Case For iPhone 6
With its impact and waterproof design, the Skinit Waterproof case provides security and protection to guarantee your phone will get you through even the most demanding outdoor conditions. The impact-... Read more
iMacs on sale for up to $150 off MSRP
B&H Photo has 21″ and 27″ iMacs on sale for up to $150 off MSRP including free shipping plus NY sales tax only: - 27″ 3.3GHz iMac 5K: $2181.11 $118 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $1949... Read more
12-inch 1.1GHz Retina MacBooks on sale for $5...
B&H Photo has 2016 12″ 1.1GHz/256GB Retina MacBooks on sale for up to $50 off MSRP. Shipping is free, and B&H charges NY tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1249 $50 off MSRP... Read more
WWDC Announcements Revisited Still Underwhelm...
I was disappointed that no new MacBook hardware was announced at this year’s all-software World Wide Developer’s Conference. Not even a hint about what’s in the development pipeline. Of course, we... Read more
Twelve South Compass 2 iPad Stand Now Availab...
Twelve South has updated its most popular iPad stand, Compass 2, with the introduction of two new colors — Gold and Rose Gold. These new color options n perfectly complement the new Rose Gold iPad... Read more

Jobs Board

*Apple* New Products Testers Needed - Apple...
…we therefore look forward to put out products to quality test for durability. Apple leads the digital music revolution with its iPods and iTunes online store, Read more
*Apple* Solutions Consultant - APPLE (United...
Job Summary As an Apple Solutions Consultant, you'll be the link between our future customers and our products. You'll showcase your entrepreneurial spirit as you 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, Towson...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Professional Learning Specialist - A...
Job Summary The Apple Professional Learning Specialist is a full-time position for one year with Apple in the Phoenix, AZ area. This position requires a high Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.