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 orsource 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: progchallenge@xplain.com,
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.
CONNECT THE DOTS
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[];
PixMapHandle thePixMapHndl;
RGBColor lineColor;
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.
TWO MONTHS AGO WINNER
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