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: 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[];
PixMapHandlethePixMapHndl;
RGBColorlineColor;

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

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 . .

Team:

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 )

#include<string.h>
#include<stdio.h>

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;\
 BufFlush();\
 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';
 b->avail--;
 }
 else
 *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';
 break;
 case kStrSep:
 *p++ = ':';
 *p++ = ' ';
 break;
 case kStrVs:
 *p++ = ' ';
 *p++ = 'v';
 *p++ = 's';
 *p++ = ' ';
 break;
 }
 }
 
 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 );
 
 BufFlush();
}
 
AAPL
$97.57
Apple Inc.
+0.54
MSFT
$44.55
Microsoft Corpora
+0.15
GOOG
$590.40
Google Inc.
-2.95

MacTech Search:
Community Search:

Software Updates via MacUpdate

Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more
Airfoil 4.8.7 - Send audio from any app...
Airfoil allows you to send any audio to AirPort Express units, Apple TVs, and even other Macs and PCs, all in sync! It's your audio - everywhere. With Airfoil you can take audio from any... Read more
Microsoft Remote Desktop 8.0.8 - Connect...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more
xACT 2.30 - Audio compression toolkit. (...
xACT stands for X Aaudio Compression Toolkit, an application that encodes and decodes FLAC, SHN, Monkey’s Audio, TTA, Wavpack, and Apple Lossless files. It also can encode these formats to MP3, AAC... Read more
Firefox 31.0 - Fast, safe Web browser. (...
Firefox for Mac offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals... Read more
Little Snitch 3.3.3 - Alerts you to outg...
Little Snitch gives you control over your private outgoing data. Track background activityAs soon as your computer connects to the Internet, applications often have permission to send any... Read more
Thunderbird 31.0 - Email client from Moz...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Together 3.2 - 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. Smart storage. With simple drag-and-drop functionality,... Read more
Cyberduck 4.5 - FTP and SFTP browser. (F...
Cyberduck is a robust FTP/FTP-TLS/SFTP browser for the Mac whose lack of visual clutter and cleverly intuitive features make it easy to use. Support for external editors and system technologies such... Read more

Latest Forum Discussions

See All

Watch and Share Mobile Gameplay Videos W...
Watch and Share Mobile Gameplay Videos With Kamcord Posted by Jennifer Allen on July 25th, 2014 [ permalink ] iPhone App - Designed for the iPhone, compatible with the iPad | Read more »
THE KING OF FIGHTERS '98 (Games)
THE KING OF FIGHTERS '98 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: Series’ masterpiece “KOF ’98” finally joins the battle on iPhone! FEATURES:■ The best game balance in the “KOF”... | Read more »
LEX Goes Free For One Day In Honor of Ne...
LEX Goes Free For One Day In Honor of New Update Posted by Jennifer Allen on July 24th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Thomas Was Alone Goes Universal, Slashes...
Thomas Was Alone Goes Universal, Slashes Price to $3.99 Posted by Ellis Spice on July 24th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Meerkatz Challenge Review
Meerkatz Challenge Review By Jennifer Allen on July 24th, 2014 Our Rating: :: FONDLY PUZZLINGUniversal App - Designed for iPhone and iPad Cute and challenging, Meerkatz Challenge is a fun puzzle game, particularly for fans of... | Read more »
Book Your Appointment with F.E.A.R. this...
Book Your Appointment with F.E.A.R. | Read more »
It Came From Canada: Epic Skater
For all the hate that it gets for being a pastime for slackers, skateboarding really does require a lot of skill. All those flips and spins take real athleticism, and there’s all the jargon to memorize. Fortunately for us less extreme individuals,... | Read more »
Cultures Review
Cultures Review By Jennifer Allen on July 24th, 2014 Our Rating: :: SLOW-PACED EMPIRE BUILDINGiPad Only App - Designed for the iPad Cute it might seem, but Cultures is a bit too slow paced when it comes to those pesky timers to... | Read more »
More Paintings Have Been Added to Paint...
More Paintings Have Been Added to Paint it Back! Posted by Jessica Fisher on July 24th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Heroes Rise: HeroFall Review
Heroes Rise: HeroFall Review By Lee Hamlet on July 24th, 2014 Our Rating: :: A FITTING ENDUniversal App - Designed for iPhone and iPad The last instalment in the Heroes Rise trilogy put players back into the cape and brightly... | Read more »

Price Scanner via MacPrices.net

Mac minis on sale for $100 off MSRP, starting...
Best Buy has Mac minis on sale for $100 off MSRP. Choose free shipping or free instant local store pickup. Prices are for online orders only, in-store prices may vary: 2.5GHz Mac mini: $499.99 2.3GHz... Read more
Global Tablet Market Grows 11% in Q2/14 Notwi...
Worldwide tablet sales grew 11.0 percent year over year in the second quarter of 2014, with shipments reaching 49.3 million units according to preliminary data from the International Data Corporation... Read more
New iPhone 6 Models to Have Staggered Release...
Digitimes’ Cage Chao and Steve Shen report that according to unnamed sources in Apple’s upstream iPhone supply chain, the new 5.5-inch iPhone will be released several months later than the new 4.7-... Read more
New iOS App Helps People Feel Good About thei...
Mobile shoppers looking for big savings at their favorite stores can turn to the Goodshop app, a new iOS app with the latest coupons and deals at more than 5,000 online stores. In addition to being a... Read more
Save on 5th generation refurbished iPod touch...
The Apple Store has Apple Certified Refurbished 5th generation iPod touches available starting at $149. Apple’s one-year warranty is included with each model, and shipping is free. Many, but not all... Read more
What Should Apple’s Next MacBook Priority Be;...
Stabley Times’ Phil Moore says that after expanding its iMac lineup with a new low end model, Apple’s next Mac hardware decision will be how it wants to approach expanding its MacBook lineup as well... Read more
ArtRage For iPhone Painting App Free During C...
ArtRage for iPhone is currently being offered for free (regularly $1.99) during Comic-Con San Diego #SDCC, July 24-27, in celebration of the upcoming ArtRage 4.5 and other 64-bit versions of the... Read more
With The Apple/IBM Alliance, Is The iPad Now...
Almost since the iPad was rolled out in 2010, and especially after Apple made a 128 GB storage configuration available in 2012, there’s been debate over whether the iPad is a serious tool for... Read more
MacBook Airs on sale starting at $799, free s...
B&H Photo has the new 2014 MacBook Airs on sale for up to $100 off MSRP for a limited time. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels... Read more
Apple 27″ Thunderbolt Display (refurbished) a...
The Apple Store has Apple Certified Refurbished 27″ Thunderbolt Displays available for $799 including free shipping. That’s $200 off the cost of new models. Read more

Jobs Board

*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Sr. Project Manager for *Apple* Campus 2 -...
…the design and construction of one building or building components of the New Apple Campus located in Cupertino, CA. They will provide project management oversight for Read more
WW Sales Program Manager, *Apple* Online St...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.