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();
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Fantastical 2.5.13 - Create calendar eve...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
A Better Finder Rename 11.05 - File, pho...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
SpamSieve 2.9.38 - Robust spam filter fo...
SpamSieve is a robust spam filter for major email clients that uses powerful Bayesian spam filtering. SpamSieve understands what your spam looks like in order to block it all, but also learns what... Read more
TeamViewer 15.0.8397 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for non... Read more
SteerMouse 5.4.3 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Toast Titanium 18.2.1 - The ultimate med...
Roxio Toast Titanium, the leading DVD burner for Mac, makes burning even better, adding Roxio Secure Burn to protect your files on disc and USB in Mac- or Windows-compatible formats. Get more style... Read more
HoudahSpot 5.0.11 - Advanced file-search...
HoudahSpot is a versatile desktop search tool. Use HoudahSpot to locate hard-to-find files and keep frequently used files within reach. HoudahSpot will immediately feel familiar. It works just the... Read more
ClipGrab 3.8.6 - Download videos from Yo...
ClipGrab is a free downloader and converter for YouTube, Vimeo, Facebook and many other online video sites. It converts downloaded videos to MPEG4, MP3 or other formats in just one easy step Version... Read more
ExpanDrive 7.4.0 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Adobe Dreamweaver CC 2020 20.0 - Build w...
Dreamweaver CC 2020 is available as part of Adobe Creative Cloud for as little as $20.99/month (or $9.99/month if you're a previous Dreamweaver customer). Adobe Dreamweaver CC 2020 allows you to... Read more

Latest Forum Discussions

See All

New heroes and balance updates set to ar...
It feels like Hearthstone: Battlegrounds only launched yesterday, and already the auto batter addition to Blizzard's megahit card game is set to receive new heroes and balance updates. [Read more] | Read more »
Pre-register for Hello Kitty AR: Kawaii...
Hello Kitty — the cute cat that launched a multi-billion-pound franchise — has been brought to life… sort of. Sanrio has teamed up with the Bublar Group to create a new mobile game that uses AR tech to turn the real world into Hello Kitty’s... | Read more »
Gorgeous and tranquil puzzler Spring Fal...
One-man indie studio SPARSE//GameDev has now launched its tranquil puzzler, Spring Falls. It's described as "a peaceful puzzle game about water, erosion, and watching things grow". [Read more] | Read more »
Black Desert Mobile gets an official rel...
Pearl Abyss has just announced that its highly-anticipated MMO, Black Desert Mobile, will launch globally for iOS and Android on December 11th. [Read more] | Read more »
Another Eden receives new a episode, cha...
Another Eden, WFS' popular RPG, has received another update that brings new story content to the game alongside a few new heroes to discover. [Read more] | Read more »
Overdox guide - Tips and tricks for begi...
Overdox is a clever battle royale that changes things up by adding MOBA mechanics and melee combat to the mix. This new hybrid game can be quite a bit to take in at first, so we’ve put together a list of tips to help you get a leg up on the... | Read more »
Roterra Extreme - Great Escape is a pers...
Roterra Extreme – Great Escape has been described by developers Dig-It Games as a mini-sequel to their acclaimed title Roterra: Flip the Fairytale. It continues that game's tradition of messing with which way is up, tasking you with solving... | Read more »
Hearthstone: Battlegrounds open beta lau...
Remember earlier this year when auto battlers were the latest hotness? We had Auto Chess, DOTA Underlords, Chess Rush, and more all gunning for our attention. They all had their own reasons to play, but, at least from where I'm standing, most... | Read more »
The House of Da Vinci 2 gets a new gamep...
The House of Da Vinci launched all the way back in 2017. Now, developer Blue Brain Games is gearing up to deliver a second dose of The Room-inspired puzzling. Some fresh details have now emerged, alongside the game's first official trailer. [Read... | Read more »
Shoot 'em up action awaits in Battl...
BattleBrew Productions has just introduced another entry into its award winning, barrelpunk inspired, BattleSky Brigade series. Whilst its previous title BattleSky Brigade TapTap provided fans with idle town building gameplay, this time the... | Read more »

Price Scanner via MacPrices.net

Apple continues to offer 2017 13″ Dual-Core n...
Apple has Certified Refurbished 2017 13″ 2.3GHz Dual-Core non-Touch Bar MacBook Pros still available starting at $1019. An standard Apple one-year warranty is included with each model, outer cases... Read more
Save up to $120 on the new 16″ MacBook Pro at...
Apple’s resellers are starting to receive stock of new 16″ MacBook Pros, and the first set of sales & deals are now available: (1) Amazon 16″ MacBook Pros start on sale for $100-$116 off Apple’s... Read more
Apple Watch Series 3 models on sale at Amazon...
Amazon has Apple Watch Series 3 GPS models on sale for $30 off MSRP, starting at only $169. There prices are the lowest we’ve ever seen for these models from any Apple reseller. Choose Amazon as the... Read more
The ‘Mac Potpourri’ Mailbag: Edition #1- Info...
COMMENTARY: 11.20.19- Welcome to the inaugural edition of the “Mac Potpourri” Mailbag where we take a look at correspondence received from readers of this column from all over the world who write in... Read more
13″ 2.4GHz MacBook Pros available for up to $...
Apple has a full line of Certified Refurbished 2019 13″ 2.4GHz 4-Core Touch Bar MacBook Pros available starting at $1529 and up to $300 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
New at T-Mobile: Switch to T-Mobile, and get...
T-Mobile is offering a free 64GB iPhone 8 for new customers who switch to T-Mobile and open a new line of service. Eligible trade-in required, and discount applied over a 24 month period. The fine... Read more
Xfinity Mobile’s Black Friday Apple savings:...
Take $250 off the purchase of any iPhone at Xfinity Mobile with a new line activation, and transfer of phone number to Xfinity Mobile, through December 8, 2019. This includes Apple’s new iPhone 11... Read more
2019 13″ 1.4GHz MacBook Pros available starti...
Apple has a full line of Certified Refurbished 2019 13″ 1.4GHz 4-Core Touch Bar MacBook Pros available starting at $1099 and up to $230 off MSRP. Apple’s one-year warranty is included, shipping is... Read more
Save up to $350 on a 21″ or 27″ iMac with the...
Apple has Certified Refurbished 2019 21″ & 27″ iMacs available starting at $929 and up to $350 off the cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Early Holiday 2019 Sale: B&H again offers...
B&H Photo has 10.2″ iPads on sale again for $30 off Apple’s MSRP, starting at $299, as part of their early Holiday 2019 sale. Overnight shipping is free to many addresses in the US: – 10.2″ 32GB... Read more

Jobs Board

Best Buy *Apple* Computing Master - Best Bu...
**745516BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Store Associates **Store NUmber or Department:** 001101-Manhattan-Store **Job Read more
Best Buy *Apple* Computing Master - Best Bu...
**746655BR** **Job Title:** Best Buy Apple Computing Master **Job Category:** Sales **Store NUmber or Department:** 002518-Atlantic Center-Store **Job Description:** Read more
*Apple* Mobility Pro - Best Buy (United Stat...
**747089BR** **Job Title:** Apple Mobility Pro **Job Category:** Store Associates **Store NUmber or Department:** 000377-Prescott AZ-Store **Job Description:** At Read more
*Apple* Health Benefit Specialist - Call Cen...
Description ** Apple Health Benefit Specialist - Call Center (MAS 3/MACSC)** **Olympia, WA Multiple Positions** *The ideal candidate for this position will have Read more
Hair Stylist - *Apple* Blossom Mall - JCPen...
Hair Stylist - Apple Blossom Mall Location:Winchester, VA, United States- Apple Blossom Mall 1850 Apple Blossom Dr Job ID:1065040Salon Professionals Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.