TweetFollow Us on Twitter

Jan 94 Challenge
Volume Number:10
Issue Number:1
Column Tag:Programmers’ Challenge

Programmers’ Challenge

Connect The Dots

By Mike Scanlin, MacTech Magazine Regular Contributing Author

Note: Source code files accompanying article are located on MacTech CD-ROM or source code disks.

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 MacTech Magazine (formerly 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 “The Winner! MacTech Magazine Programming Challenge” T-shirt (not to be found in stores).

In order to make fair comparisons between solutions, all solutions must be in ANSI compatible C (i.e., don’t use Think’s Object extensions). Only pure C code can be used. Any entries with any assembly in them will be disqualified (except for those challenges specifically stated to be in assembly). However, you may call any routine in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK 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. All code should be limited to 60 characters wide. This will aid us in dealing with e-mail gateways and page layout.

The solution and winners for this month’s Programmers’ Challenge will be published in the issue two months later. All submissions must be received by the 10th day of the month printed on the front of this issue.

All solutions should be marked “Attn: Programmers’ Challenge Solution” and sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or preferably, e-mail - AppleLink: MT.PROGCHAL, Internet:, CompuServe: 71552,174 and America Online: MT PRGCHAL. 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.”

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month and all entries are the property of MacTech Magazine upon submission. The submission falls under all the same conventions of an article submission.


Thanks to James Goebel (location unknown) for suggesting this month’s challenge. You are given a set of Points and a PixMapHandle. The goal is to quickly draw a line from each point in the set to the next point in the set (if you have n points then draw n-1 line segments). A really fast version of this routine would help improve the speed of a program that makes line charts, for instance.

The prototype of the function you write is:

/* 1 */
void ConnectTheDots(numDots, theDots, 
 thePixMapHndl, lineColor)
unsigned short numDots;
Point   theDots[];

NumDots is the 1-based number of Points in the array theDots (range is 2..500). ThePixMapHandle is a handle to the PixMap where the line drawing takes place (maximum dimensions are 4000 pixels square). In order to avoid sub-byte addressing problems, you can assume that the only combinations of pixelSize, cmpSize and cmpCount of the PixMap you’ll have to deal with are (8, 8, 1), (16, 5, 3) and (32, 8, 3) (basically, 256 indexed colors, 16-bit direct (Thousands) and 32-bit direct (Millions)).

LineColor is the RGBColor that you should use to draw each line segment. If the PixMap is indexed then you’ll have to convert the RGBColor to the appropriate index value (using the inverse table of the PixMap’s pmTable field). You may assume that each point in theDots array lies within the bounds of the PixMap. And it’s okay to write or clear the unused bits of each pixel (the alpha bit(s) in the 16-bit or 32-bit direct cases).

Here’s an example: Say numDots is 4, theDots[0] = (1,2), theDots[1] = (1,4), theDots[2] = (2,4) and theDots[3] = (3,6). You would draw 3 lines of the appropriate color from (1,2) to (1,4), from (1,4) to (2,4) and from (2,4) to (3,6).

That’s it. Pretty simple concept, huh? The key is, though, that you can probably do better than the ROM’s Line or LineTo routines given the special circumstances that this drawing takes place in. Your pen size is (1,1), the mode is patCopy, there is no clipping or bounds checking, etc. It boils down to how fast your line algorithm is and how fast you can do byte-aligned pixel addressing. It is not necessary to exactly match QuickDraw’s Line routine; that is, you don’t have to plot the exact same set of pixels when making a line from a given point to some other given point. But your line routine should produce reasonable unbroken lines nonetheless.


Of the 21 entries I received for the Who Plays Who challenge I only had to disqualify 3 entries: one that used tables of precomputed answers, one that was written in Pascal and one that was incorrect. Of those remaining there were two who were equally fast: Bill Karsh (Chicago, IL) and two-time Challenge winner Bob Boonstra (Westford, MA). Bill wins, though, because his code and data size is about a quarter of Bob’s.

Here are the times, code+data sizes and outpTop 10ut sizes of each entry (the output size represents the concatenated output for many sample runs of the routine). Numbers in parens after a person’s name indicate how many times that person has finished in the top 5 places of all previous Programmer Challenges, not including this one.

Name time code+data output size

Bill Karsh (1) 4 660 27935

Bob Boonstra (3) 4 2430 29157

James Goebel (1) 7 348 29157

Doug Currie 8 298 29066

P Kidwell & G Klesczewski 8 468 29113

Dan Farmer 8 526 29157

Jerry Panagrossi 12 508 29183

Thomas Studer 12 906 29158

Martin Caron 16 676 29158

Jorj Bauer 28 11040 28936

John Chen 34 1828 29027

Michael Panchenko 73 270 35944

Dave Darah 73 780 33682

Allen Stenger (2) 74 728 35158

Stefan Pantke 76 764 33075

Steve Gehrman 81 1294 28813

Jan de Ruiter 145 354 76431

Jeremy Vineyard (1) 4561 592 29069

One thing that the two fastest entries have in common is that they don’t call fprintf (which takes up the bulk of the time for most solutions). Instead, they format the output themselves (since the format requirements are simple), buffer the output to one of their own buffers (allocated on the stack) and then call fwrite (see Bill’s solution below for an example of this).

Although I disqualified the entry from Ernst Munter (Kanata, ON, Canada) for using entirely too many precomputed lookup tables, his output format was interesting (and very compact). Here’s a sample for 12 teams:

Matches are played every 15 minutes,

starting at noon. Teams meet each other

in the designated playing areas.

Playing Areas:

A = Field 1

B = Field 2

C = Field 3

D = Field 4

E = Field 5

F = Field 6

Time: 12 . . . 1 . . . 2 . .


CycleStealers A A A A A A A A A A A

Beanies A B B B B B B B B B B

RiscTakers B A B C C C C C C C C

GiraffeButts B B A D D D D D D D D

BlueBombers C C C A B E E E E C D

Wackos C D D B A F F F F D C

Peashooters D C D E E A B C D E E

SourGrapes D D C F F B A D C F F

SnowBirds E E E C D E F A B E F

Monarchs E F F D C F E B A F E

Accountants F E F E F C D E F A B

Friends F F E F E D C F E B A

Here’s Bill’s winning solution:

/* 2 */
/* ScheduleMatches ----------------------------------------
 * In response to Nov 93 MacTech programmer's challenge.
 * Object is to:
 * 1)   form all combinations of 'numTeams' 'teamNames',
 * taken two at a time (numTeams even);
 * 2) match these pairs to 'numTeams'/2
 * 'playingAreaNames';
 * 3) schedule 'numTeams'/2 "matches" at a time, starting
 * at 12 noon, with a new set of such matches
 * scheduled every 15 minutes, until all combinations
 * are used;
 * 4) write the whole schedule out to a given ANSI file
 * stream.
 * Some observations:
 * number of combinations = C(numTeams,2) =
 * numTeams*(numTeams-1)/2.
 * There are then (numTeams-1) sets of matches, or,
 * times, which must be scheduled.
 * The pairs can be generated geometrically using
 * central cyclical pattern as demonstrated for
 * numTeams = 6:
 *          1           Connecting rods have fixed
 *          |           orientation.  0 stays in center.
 *          |           Other digits cycle clockwise, 
 *    2---\ 0 /---5     or, cc, around circumference.
 *         ---
 *       3-----4
 * Suggested formatting is as follows:
 * 12:xx
 * areaU: nameJ vs nameK
 * areaV: nameL vs nameM
 * .
 * .
 * {blank line}
 * 12:xx
 * .
 * .
 * billKarsh - solution author.

#pragma options( honor_register, !assign_registers )
#pragma options( !check_ptrs )


void ScheduleMatches(
 unsigned short  numTeams,
 Str255 teamNames[],
 Str255 playingAreaNames[],
 FILE   *outputfile );

#define BufSize  1024

// BufIt modifier codes
#define kTime    -1// write time
#define kStrn    1 // write string + '\n'
#define kStrSep  2 // write string + ': '
#define kStrVs   4 // write string + ' vs '

// useful shorthand inside BufIt
// make sure n bytes available in buffer,
// else empty it out

#define BufReady( n )\
 if( n > b->avail ) {\
 b->p = p;\
 p = b->buf;\

typedef struct {
 FILE   *file; // ANSI stream
 Byte   *buf;  // start of private buffer
 Byte   *p; // current position in buffer
 short  avail; // available bytes in buffer
 short  padding;// global data 4-byte aligned
} BufRec;

static  BufRec gBuf;

/* BufFlush -----------------------------------------------
 * Write current buffer to file.
static void BufFlush( void )
 register BufRec *b = &gBuf;
 size_t  n = b->p - b->buf;
 if( n ) {
 fwrite( b->buf, 1, n, b->file );
 // reset buffer
 b->p   = b->buf;
 b->avail = BufSize;

/* BufIt --------------------------------------------------
 * 1) Write string to local buffer if room,
 * otherwise,
 * 2) Dump buffer to file,
 * 3) resume with step 1.
 * If behavior code, mod, as defined above is >= 0:
 * data is data starting address,
 * nBytes of data to write.
 * If mod is special code kTime:
 * data indexes internal minute string,
 * nBytes = hour.
static void BufIt(
 register Byte *data,
 register short  nBytes,
 short  mod )
 register BufRec *b= &gBuf;
 register Byte *p= b->p;
 static  Byte  mins[8]  = "00153045";

 if( mod < 0 ) { // write a time
 BufReady( 7 );
 *p++ = '\n';
 // hour
 if( !nBytes ) {
 *p++ = '1';
 *p++ = '2';
 *p++ = nBytes + '0';
 *p++  =':';
 // mins
 data += (long)mins;
 *p++ = *data++;
 *p++ = *data;
 *p++ = '\n';
 b->avail -= 6;
 else { // write a string
 BufReady( nBytes + mod );
 memcpy( p, data, nBytes );
 p += nBytes;
 b->avail -= nBytes + mod;
 switch( mod ) { // write string suffix
 case kStrn:
 *p++ = '\n';
 case kStrSep:
 *p++ = ':';
 *p++ = ' ';
 case kStrVs:
 *p++ = ' ';
 *p++ = 'v';
 *p++ = 's';
 *p++ = ' ';
 b->p = p;

/* ScheduleMatches ----------------------------------------
 * Driver routine.
void ScheduleMatches(
 unsigned short  numTeams,
 Str255 teamNames[],
 Str255 playingAreaNames[],
 FILE   *outputfile )
 register Byte *area, *tmJ, *tmK;
 register short  N = numTeams,
 set  = 0, nAreas;
 register long t1= (long)*teamNames + 256,
 tN= t1 + ((N-2)<<8);
 Byte   localBuf[BufSize];
 if( !N || N & 1 ) return;
// init local buffer

 gBuf.file= outputfile;
 gBuf.buf = gBuf.p = localBuf;
 gBuf.avail = BufSize;
 // loop over sets of matches (times)
 do {
 // do first pair separately, because team[0]
 // is at center, so this pair disjoint from
 // others.
 nAreas = N>>1;
 area = *playingAreaNames;
 BufIt( (Byte*)((set&3)<<1), set>>2, kTime );
 BufIt( area+1, *area, kStrSep );
 tmJ = (Byte*)t1 - 256;
 tmK = (Byte*)t1 + (set<<8);
 BufIt( tmJ+1, *tmJ, kStrVs );
 BufIt( tmK+1, *tmK, kStrn  );
 tmJ = tmK;
 // loop over remaining areas (pairs)
 while( --nAreas ) {
 area += 256;
 BufIt( area+1, *area, kStrSep );
 // next pair
 tmJ = (long)tmJ < tN ? tmJ+256 : (Byte*)t1;
 tmK = (long)tmK > t1 ? tmK-256 : (Byte*)tN;
 BufIt( tmJ+1, *tmJ, kStrVs );
 BufIt( tmK+1, *tmK, kStrn  );
 } while( ++set < N - 1 );

Community Search:
MacTech Search:

Software Updates via MacUpdate

Bookends 12.6.0 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Access the power of Bookends directly from Mellel, Nisus Writer Pro, or MS Word (... Read more
Apple iBooks Author 2.4 - Create and pub...
Apple iBooks Author helps you create and publish amazing Multi-Touch books for iPad. Now anyone can create stunning iBooks textbooks, cookbooks, history books, picture books, and more for iPad. All... Read more
Web Snapper 3.3.9 - Capture entire Web p...
Web Snapper lets you capture Web pages exactly as they appear in your browser. You can send them to a file as images or vector-based, multi-page PDFs. It captures the whole Web page - eliminating the... Read more
Tunnelblick 3.6beta10 - GUI for OpenVPN...
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
EtreCheck 2.5.1 - For troubleshooting yo...
EtreCheck is a simple little app to display 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... Read more
Paragraphs 1.0.4 - Writing tool just for...
Paragraphs is an app just for writers. It was built for one thing and one thing only: writing. It gives you everything you need to create brilliant prose and does away with the rest. Everything in... Read more
Things 2.8 - Elegant personal task manag...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
Coda 2.5.12 - One-window Web development...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few surprises... Read more
PCalc 4.3 - Full-featured scientific cal...
PCalc is a full-featured, scriptable scientific calculator with support for hexadecimal, octal, and binary calculations, as well as an RPN mode, programmable functions, and an extensive set of unit... Read more
DiskMaker X 5.0 - Make a bootable OS X i...
DiskMaker X (was Lion DiskMaker) helps you to build a bootable drive from the official OS X installer app (the one you download from the Mac App Store). It detects the OS X Install program with... Read more

Camel Up (Games)
Camel Up 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Martian: Bring Him Home (Games)
The Martian: Bring Him Home 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Based on the best selling novel and critically acclaimed film, THE MARTIAN tells the story of Astronaut Mark... | Read more »
This Week at 148Apps: September 21-30, 2...
Leap Into Fall With 148Apps How do you know what apps are worth your time and money? Just look to the review team at 148Apps. We sort through the chaos and find the apps you're looking for. The ones we love become Editor’s Choice, standing out above... | Read more »
Tweetbot 4 for Twitter (Social Networki...
Tweetbot 4 for Twitter 4.0 Device: iOS Universal Category: Social Networking Price: $4.99, Version: 4.0 (iTunes) Description: *** 50% off for a limited time. *** | Read more »
Mori (Games)
Mori 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Stop, rewind and unwind with Mori. Time is always running, take a moment to take control. Mori is an action puzzle game about infinitely... | Read more »
100 Years' War (Games)
100 Years' War 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Tower in the Sky (Games)
Tower in the Sky 0.0.60 Device: iOS Universal Category: Games Price: $1.99, Version: 0.0.60 (iTunes) Description: | Read more »
hocus. (Games)
hocus. 1.0.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0.0 (iTunes) Description: New, polished, mind-bending, minimal puzzle game with dozens of levels and extra-ordinary design Features:- Beautifully crafted... | Read more »
Mos Speedrun 2 (Games)
Mos Speedrun 2 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Mos is back, in her biggest and most exciting adventure ever! Wall-jump to victory through 30 mysterious, action packed levels... | Read more »
3D Touch could be a game-changer, but it...
Were you one of the lucky/financially secure enough ones to buy a new iPhone 6s or iPhone 6s Plus over the weekend? Yup, me too (I’m not convinced I was either of those two things, but let’s go with lucky for now), so I thought I’d delve into just... | Read more »

Price Scanner via

12-inch MacBooks in stock for up to $120 off,...
Adorama has 12″ Retina MacBooks in stock for up to $120 off MSRP including free shipping plus NY & NJ sales tax only. For a limited time, Adorama will include a free Apple USB-C to USB Adapter,... Read more
15-inch 2.2GHz Retina MacBook Pro on sale for... has the 15″ 2.2GHz Retina MacBook Pro on sale for $1799 including free shipping. Their price is $200 off MSRP, and it’s the lowest price available for this model (except for Apple’s $1699... Read more
iPhone 6s and 6s Plus Feature Improved Durabi...
Upgraded components in the new iPhone 6s Plus cost $16 more than the components in the earlier iPhone 6 Plus according to a preliminary estimate from IHS Inc. The bill of materials (BOM) for an... Read more
13-inch Retina MacBook Pros on sale for up to...
Adorama has 13″ Retina MacBook Pros on sale for up to $130 off MSRP. Shipping is free, and Adorama charges sales tax for NY & NJ residents only: - 13″ 2.7GHz/128GB Retina MacBook Pro: $1199.99 $... Read more
Apple refurbished 2014 13-inch Retina MacBook...
Apple has Certified Refurbished 2014 13″ 2.6GHz/128GB SSD Retina MacBook Pros available $979, $320 off original MSRP. An Apple one-year warranty is included, and shipping is free: - 13″ 2.6GHz/128GB... Read more
iOS 9 Reflections Ten Days In – The ‘Book Mys...
I’ve never been much of an early adopter by philosophy or temperament, although I did buy the iPad Air 2 I’m typing this column on last fall only about a month after Apple unveiled it. However, my... Read more
Apple refurbished Time Capsules available for...
Apple has certified refurbished Time Capsules available for $120 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $179, $120 off - 3TB... Read more
OS X El Capitan Available as a Free Update To...
OS X El Capitan, the latest major release of Apple’s desktop operating system, is available today, September 30 as a free update for Mac users. “People love using their Macs, and one of the biggest... Read more
15-inch Retina MacBook Pros on sale for $150-...
B&H Photo has 2015 15″ Retina MacBook Pros on sale for up to $200 off MSRP including free shipping plus NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1815 $184 off - 15″ 2.5GHz Retina... Read more
Updated For iOS 9, InterConneX Lets You Store...
InterConneX version 1.2 is now a 64-bit app that’s completely compatible with iOS 9. InterConneX is a file storage, file management, and file sharing app for the iPhone or iPad that now takes... Read more

Jobs Board

*Apple* Systems Engineer (Mclean, VA and NYC...
Title: Apple Systems Engineer (Mclean, VA and NYC)Location: United States-New York-New York-NYC 200 Park Avenue (22005)Other Locations: United Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, you're Read more
*Apple* Retail - Multiple Customer Support P...
Job Description:Customer SupportSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the Read more
*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
SW QA Engineer - *Apple* TV - Apple (United...
**Job Summary** The Apple TV team is looking for experienced Quality Assurance Engineers with a passion for delivering first in class home entertainment solutions. **Key Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.