TweetFollow Us on Twitter

Oct 94 Challenge
Volume Number:10
Issue Number:10
Column Tag:Programmer’s Challenge

Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

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

The rules

Here’s how it works: Each month we present a different programming challenge here. First, you write some code that solves the challenge. Second, optimize your code (a lot). Then, submit your solution to MacTech Magazine (formerly MacTutor). We choose a winner 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 available 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). Use only pure C code. We will disqualify any entries with any assembly in them (except for those challenges specifically stated to be in assembly). You may call any routine in the Macintosh toolbox you want (e.g., it doesn’t matter if you use NewPtr instead of malloc). We test entries with the FPU and 68020 flags turned off in THINK C. We time routines with the latest version of THINK C (with “ANSI Settings”, “Honor ‘register’ first”, and “Use Global Optimizer” turned on), so beware if you optimize for a different C compiler. Limit your code to 60 characters wide. This helps us deal with e-mail gateways and simplifies page layout.

We publish the solution and winners for this month’s Programmers’ Challenge 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.

Mark solutions “Attn: Programmers’ Challenge Solution” and send them via e-mail - Internet, AppleLink MT.PROGCHAL, CompuServe 71552,174 and America Online MT PRGCHAL. Include the solution, all related files, and your contact information. If you send via snail mail, please send a disk with those items on it; see “How to Contact Xplain Corporation” on page 2.

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month. Authors grant MacTech Magazine the non-exclusive right to publish entries without limitation upon submission of each entry. Authors retain copyrights for the code.

How Long Will It Take?

All of the programmer challenges during the last couple of years have focused on optimizing algorithms and implementations. This month we have something a little different. We’re going to tackle one of the hardest problems every software engineer has to deal with. No, I’m not talking about some weird memory model compatibility problem on DOS machines; I’m talking about scheduling. Specifically, estimating how long a particular software project will take. We all know it’s hard for us subjective humans to do this task accurately but maybe one of you clever readers can come up with an algorithmic way to estimate a project. And, you can even decide what your parameters will be.

Here are some example parameters you might want to use to describe the software task at hand:

version = the number of major versions of this product that have already shipped (if you were working on System 8 then this number would be 7, for a new project it would be zero)

features = estimated number of major features that need to be implemented (for a text-based project the following are examples of major features: spell checking, printing, styles, find/replace, footnotes)

engSkilled = the number of very competent engineers working on the project (more than 5 years experience on the relevant platform using the relevant tools)

engNewGuys = the number of unskilled or relatively junior engineers working on the project (less than 2 years experience)

marketing = the number of full-time marketing folks working on the project

uiPeople = the number of people who have at least some decision making authority about the user interface of the project

qaPeople = the number of trained in-house testers assigned to the project

betaTesters = the number of out-of-house user testers using the product at least a month before code freeze

meetings = average number of meetings per engineer per week during the course of the project

love = a number from 1 to 5 describing how well the team members like each other (5 means everyone gets along great, respects and trusts each other; 1 means there are problems affecting work between several members).

linesC = estimated number of lines of code (of C)

objectKB = estimated executable size, in KB

mpw (boolean) = true if using MPW for compiling the base project

thinkC (boolean) = true if using Think C for compiling the base project

appFramework (boolean) = true if using someone else’s application framework or class library (like TCL or MacApp)

systemCost = average number of dollars per engineer spent on engineering development hardware (do the engineers have ample CPU, RAM, disk space, etc.?)

personalMoney (boolean) = true if the engineer’s are financing this project at least partially with their own money

bonusMoney (boolean) = true if there is a meaningful bonus for the team if the project is done on time

food (boolean) = company provides adequate in-house food or, there is at least one restaurant that delivers food 24 hours a day

dew (boolean) = true if free Mountain Dew is available in-house

toys = average number of toys per engineer

netnews (boolean) = true if netnews is available

email (boolean) = true if e-mail is available

The prototype of the function you write starts like this:

/* 1 */
unsigned short SoftwareTimeEstimate(...);

and it’s up to you to fill in the list of parameters (including their types, probable ranges and maybe an example of each). You can choose from the list above or make up your own. The return value is the estimated total time (in calendar days) that the software project will take to make the golden master disk (but it does not include time for printing the manual, disk-duplicating, shipping, etc.).

In order to limit the scope of the project a little bit, let’s assume the project is a typical general-purpose Macintosh application. It could center around graphics, text, spreadsheet, database, communications, etc (nothing too vertical or specialized, though). You can give as much or as little weight to any of the parameters as you like. Your parameters should not be too specific because they need to work for a fairly broad selection of software projects ranging from version 1.0 of a new word processor to version 8.0 of an existing spreadsheet.

Unlike normal challenges, this challenge will not be judged on speed or code size. Instead each entry will be graded by a panel of at least three judges who will give a numerical score to each entry in each of three categories: (1) realistic (i.e. someone might actually be able to use it and get a somewhat usable number out of it), (2) documented assumptions, opinions and coefficients (explain at least a little bit how each variable, ratio and coefficient affects the final answer you produce; use lots of #defines so if someone disagrees with you they can redefine your coefficients and recompile to their taste) and (3) humor (let’s not take this thing too seriously; the winning solution should be fun to read and maybe have a silly parameter or two). The judges’ subjective scores will be totalled and the highest overall point total will win.

If you want to earn extra credit points for your entry then you can also submit your list of Top 5 Excuses Why This Project Is Late that you might give to management (who may or may not be technically impaired) once your deadline has passed. They can be meaningful excuses (“we need more equipment/people”), they can be actual excuses you’ve used in the past (“my disk crashed; we have no backup”) and/or they can be things you’d like to use but probably won’t for fear of reprisals (“If you’d stop asking me every 5 minutes when it will be done then it will be done a hell of a lot sooner!”). For each excuse the judges like we’ll add a few points to your overall score.

One last request: Please don’t go completely wack-o in terms of the length of your entry. The winning solution should fit on 2 to 6 standard MacTech code-listing type pages. This may limit the accuracy of your entry a bit (depending on how detailed you want to be) but you’ll just have to live with that and concentrate on the most important parameters first. As always, e-mail me if you have any questions.

Two Months Ago Winner

Congratulations to Dave Darrah (Lansdale, PA) for his winning entry in the DumpBytes challenge. Despite a bug in Think C (which he was able to identify and work around) Dave was able to dump bytes faster than anyone else and, he was able to do it with relatively little code and lookup table data (4th smallest entry overall). Nice job!

Here are the times and code+data sizes for each entry. The code+data size represents the code size plus the size of the static data (i.e. lookup tables). 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

Dave Darrah 64 1036

Ernst Munter (2) 75 3540

Bob Boonstra (11) 77 1514

N. Liber, I. Phillips (1) 83 6208

Ted DiSilvestre 86 1206

Allen Stenger (7) 87 2152

Kevin Cutts (3) 87 2286

Larry Landry (3) 103 1504

Steve Israelson (1) 128 714

Tom Elwertowski (1) 148 658

Mark Chavira 240 1514

Paul Stankiewicz 3270 422

The bug that Dave uncovered in Think C (and which I was able to reproduce) has to do with a static table of 512 chars. The very last entry (511th, zero-based) was not getting initialized to the value the auto-initializer declared it as. Dave was able to work around this bug by manually setting the last entry to the proper value early on in his code.

While reproducing this bug I noticed that if I increased the size of the table to more than 512 chars then nothing after the 510th entry (zero-based) was initialized. I then thought of breaking the long quoted string into several smaller strings and that did indeed fix the problem. So, it appears there is a limitation in Think C of 511 bytes for the length of a quoted string. If you need more you should split it up into pieces like this:

/* 2 */
static char myTable[] = \

(wouldn’t it be nice if the compiler informed you of its limits if and when you went beyond them...)


I saw something encouraging on AppleLink recently that readers of this column are sure to appreciate. Looks like Apple has finally accepted the idea that making BlockMove clear the instruction cache *every time it’s called* was not efficient (it’s only necessary when moving executable code). They have finally put an official interface on something I’ve been asking them to do for a long time: BlockMoveData. It’s just like BlockMove but it doesn’t do any cache flushing when it’s done. Craig Prouse of Apple says, “It’s only implemented in the $077D ROMs as found in the Quadra 840AV and Centris 660AV.” (I suspect it’s also implemented on any newer ROMs, too...)

To use it all you have to do is set a bit in the trap word. Normally BlockMove is 0xA02E but, if you use 0xA22E instead then you’ll get the new BlockMoveData for those ROMs where it’s implemented (and you’ll get regular old BlockMove on ROMs where it’s not). So, unless you’re moving executable code you should be using BlockMoveData for all your moves. Thanks Apple! And thanks Craig for posting this!

Here’s Dave’s winning solution:

Dump Bytes

Dave Darrah, Lansdale, PA

/* 3 */
#include <string.h>

typedef unsigned short *  usp;

// For unknown reasons, Think generates more efficient code for the critical 

// *(usp)outputText = aTablePtr[byte] instructions when 
// register coloring is off. Go figure.

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

// Address registers are used for:
//    the "inputBytes" pointer, passed parameter.
//    the "outputText" pointer, passed parameter.
//    the "outputTextA" pointer, which points to where the ASCII representation 

// Data registers are used for:
//    "space", a holder of a space.
//    "byte", a temp area that holds a value we want to "burst" to ascii.
//    "eCntr, gCntr", counters used for two loops.
//    Pointer to "aTable": "aTablePtr". Think assigns the last data reg 
to it.

unsigned short   DumpBytes(inputBytes, 
  registerPtr    inputBytes;
  registerPtr    outputText;
   unsigned short  numInputBytes;
   unsigned short  maxOutputBytes;
   unsigned short  width;
   unsigned short  grouping;

  register Byte  space=' ';
  register  Byte     byte;
  register  unsigned short  eCntr,gCntr;

  register  Ptr  outputTextA;
   unsigned short  dispValue=0;   
/* This is the hex value of what’s printed at the beginning of each line. 

 unsigned short    groupsPerLine,lineLength,extras,
 Boolean           truncated=FALSE;
   Ptr               saveOutputText=outputText;

/* 256 entry (512 byte) ascii table. This table will be indexed by the 
byte value, to return the two-char entry that is the character representation 
of that byte. See note later about how Think generates this table. */

  staticcharaTable[] = "\

  register usp aTablePtr=(usp)&aTable; 
 // Think gives aTablePtr a data register, and it actually helps!

Initialize and preflight

/* That's it for local variables, first, let's initialize a few variables 
and preflight the output length.
 Because of some flukie I haven't been able to scope out (a possible 
Think bug?), the last value (the right "F" in "FF") of aTable is hex 
0. Why? Don't know. Oh well, let's just roll with the punch. */
 aTable[511] = 'F';
// Calculate number of groups per line.
 groupsPerLine = width/grouping;
// Calculate output line length.

 lineLength = width*3 + groupsPerLine + 7;      
  // 2 for hex representation, 1 for ascii;
  // 1 for each space that follows a group;
  // 4 for disp, a colon, space and return.

// Calculate offset from outputText where ascii goes.
 asciiOffset = lineLength - width - 1;
// Calculate the number of full lines of output.

 numberOfLines = numInputBytes/width;

// Calculate the number of bytes left over after all complete lines are 
 extras = numInputBytes % width;

// Calculate the number of bytes this line takes.
 lastLineLength = asciiOffset + extras;

// Reduce numberOfLines if output would run past maxOutputBytes. 
// Just dump the number of full lines that fit in maxOutputBytes.
 if ( (lineLength * (unsigned long)numberOfLines) +
 lastLineLength  > maxOutputBytes)  {
 numberOfLines = maxOutputBytes/lineLength;
 extras = 0;
 truncated = TRUE;

/* Initialization and preflighting done.  It's time to process the input. 

 while (--numberOfLines)  { // Do each full line.

 outputTextA = outputText+asciiOffset;
   // Displacement value goes first.   
 byte = dispValue>>8;     // left byte of disp
 *(usp)outputText = aTablePtr[byte];
 outputText += 2;

 byte = dispValue;   // right byte of disp
 *(usp)outputText = aTablePtr[byte];
 outputText += 2;

 *(usp)outputText = ': ';
 outputText += 2;
 dispValue += width;
   // Now do "groupsPerLine" sets of hex expansions.
 eCntr = groupsPerLine;
 do {     // each of the "groupsPerLine" groups.
 gCntr = grouping;
 do {   // each of the "grouping" bytes.
 byte = *inputBytes++;
 *(usp)outputText = aTablePtr[byte];
   outputText += 2;

   // Do the ascii.
 if (byte < space || byte > 0x7E)
 *outputTextA++ = '.';
 *outputTextA++ = byte;
 } while (--gCntr);  // End "grouping bytes" loop

 *outputText++ = space;   // Space after each group
 } while (--eCntr);// End "groups per line" loop
 *outputTextA++ = '\r';
   // Point to beginning of next line.
 outputText = outputTextA;
 } // End of "lines" loop.

//  Now to worry, if necessary, about dribble left over. 
// A lot of code duplication, but what the hey!

 if ( extras )  {
   // Space output line.

 outputTextA = outputText+asciiOffset;
   // Displacement value goes first.   
 byte = dispValue>>8;   // left byte of disp
 *(usp)outputText = aTablePtr[byte];
 outputText += 2;

 byte = dispValue;   // right byte of disp
 *(usp)outputText = aTablePtr[byte];
 outputText += 2;

 *outputText = ':';  // space is already there.
 outputText += 2;
   // Now do "groupsPerLine" sets of hex expansions.
 eCntr = groupsPerLine;
 do {   //  each of the "groupsPerLine" groups.
 gCntr = grouping;
 do {   // each of the "grouping" bytes.
 byte = *inputBytes++;
 *(usp)outputText = aTablePtr[byte];
   outputText += 2;

   // Do the ascii.
 if (byte < space || byte > 0x7E)
 *outputTextA++ = '.';
 *outputTextA++ = byte;
 if (!--extras)
 goto AllDone;   // Nasty termination when we've done 'em all.
 } while (--gCntr);// End "bytes in group" loop

   // skip past space after each group.
 } while (--eCntr);// End of groups per line loop.
 }  // end if


 if (truncated)
 return 0;
 return(outputTextA - saveOutputText);


Community Search:
MacTech Search:

Software Updates via MacUpdate

Fantastical 2.3.6 - Create calendar even...
Fantastical 2 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
Creative Kit 1.1 - $149.99
Creative Kit 2016--made exclusively for Mac users--is your ticket to the most amazing images you've ever created. With a variety of powerful tools at your fingertips, you'll not only repair and fine-... Read more
iMazing 2.2.3 - Complete iOS device mana...
iMazing (was DiskAid) is the ultimate iOS device manager with capabilities far beyond what iTunes offers. With iMazing and your iOS device (iPhone, iPad, or iPod), you can: Copy music to and from... Read more
Apple Configurator 2.4 - Configure and d...
Apple Configurator makes it easy to deploy iPad, iPhone, iPod touch, and Apple TV devices in your school or business. Use Apple Configurator to quickly configure large numbers of devices connected to... Read more
WhatRoute 2.0.18 - Geographically trace...
WhatRoute is designed to find the names of all the routers an IP packet passes through on its way from your Mac to a destination host. It also measures the round-trip time from your Mac to the router... Read more
Posterino 3.3.5 - Create posters, collag...
Posterino offers enhanced customization and flexibility including a variety of new, stylish templates featuring grids of identical or odd-sized image boxes. You can customize the size and shape of... Read more
Skim 1.4.28 - PDF reader and note-taker...
Skim is a PDF reader and note-taker for OS X. It is designed to help you read and annotate scientific papers in PDF, but is also great for viewing any PDF file. Skim includes many features and has a... Read more
Apple macOS Sierra 10.12.4 - The latest...
With Apple macOS Sierra, Siri makes its debut on Mac, with new features designed just for the desktop. Your Mac works with iCloud and your Apple devices in smart new ways, and intelligent... Read more
Apple Numbers 4.1 - Apple's spreads...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
Xcode 8.3 - Integrated development envir...
Xcode includes everything developers need to create great applications for Mac, iPhone, iPad, and Apple Watch. Xcode provides developers a unified workflow for user interface design, coding, testing... Read more

Hearthstone celebrates the upcoming Jour...
Hearthstone gets a new expansion, Journey to Un'Goro, in a little over a week, and they'll be welcoming the Year of the Mammoth, the next season, at the same time. There's a lot to be excited about, so Blizzard is celebrating in kind. Players will... | Read more »
4 smart and stylish puzzle games like Ty...
TypeShift launched a little over a week ago, offering some puzzling new challenges for word nerds equipped with an iOS device. Created by Zach Gage, the mind behind Spelltower, TypeShift boasts, like its predecessor, a sleak design and some very... | Read more »
The best deals on the App Store this wee...
Deals, deals, deals. We're all about a good bargain here on 148Apps, and luckily this was another fine week in App Store discounts. There's a big board game sale happening right now, and a few fine indies are still discounted through the weekend.... | Read more »
The best new games we played this week
It's been quite the week, but now that all of that business is out of the way, it's time to hunker down with some of the excellent games that were released over the past few days. There's a fair few to help you relax in your down time or if you're... | Read more »
Orphan Black: The Game (Games)
Orphan Black: The Game 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dive into a dark and twisted puzzle-adventure that retells the pivotal events of Orphan Black. | Read more »
The Elder Scrolls: Legends is now availa...
| Read more »
Ticket to Earth beginner's guide: H...
Robot Circus launched Ticket to Earth as part of the App Store's indie games event last week. If you're not quite digging the space operatics Mass Effect: Andromeda is serving up, you'll be pleased to know that there's a surprising alternative on... | Read more »
Leap to victory in Nexx Studios new plat...
You’re always a hop, skip, and a jump away from a fiery death in Temple Jump, a new platformer-cum-endless runner from Nexx Studio. It’s out now on both iOS and Android if you’re an adventurer seeking treasure in a crumbling, pixel-laden temple. | Read more »
Failbetter Games details changes coming...
Sunless Sea, Failbetter Games' dark and gloomy sea explorer, sets sail for the iPad tomorrow. Ahead of the game's launch, Failbetter took to Twitter to discuss what will be different in the mobile version of the game. Many of the changes make... | Read more »
Splish, splash! The Pokémon GO Water Fes...
Niantic is back with a new festival for dedicated Pokémon GO collectors. The Water Festival officially kicks off today at 1 P.M. PDT and runs through March 29. Magikarp, Squirtle, Totodile, and their assorted evolved forms will be appearing at... | Read more »

Price Scanner via

Is A New 10.5-inch iPad Still Coming In April...
There was no sign or mention of a long-rumored and much anticipated 10.5-inch iPad Pro in Apple’s product announcements last week. The exciting iPad news was release of an upgraded iPad Air with a... Read more
T-Mobile’s Premium Device Protection Now Incl...
Good news for T-Mobile customers who love their iPhones and iPads. The “Un-carrier” has become the first national wireless company to give customers AppleCare Services at zero additional cost as part... Read more
FileWave Ensures Support for Latest Apple OS...
FileWave multi-platform device management providers announced support for Apple’s release yesterday of iOS 10.3, macOS Sierra 10.12.4, and tvOS 11.2. FileWave has a history of providing zero-day... Read more
Use Apple’s Education discount to save up to...
Purchase a new Mac or iPad using Apple’s Education Store and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free: -... Read more
Apple refurbished Apple Watches available sta...
Apple is now offering Certified Refurbished Series 1 and Series 2 Apple Watches for 14-16% off MSRP, starting at $229. An Apple one-year warranty is included with each watch. Shipping is free: Series... Read more
9-inch 32GB Space Gray iPad Pro on sale for $...
B&H Photo has the 9.7″ 32GB Space Gray Apple iPad Pro on sale for $549 for a limited time. Shipping is free, and B&H charges NY sales tax only. Their price is $50 off MSRP. Read more
13-inch MacBook Airs on sale for $100-$150 of...
B&H Photo has 13″ MacBook Airs on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/128GB MacBook Air (MMGF2LL/A): $899 $100 off MSRP - 13″ 1.... Read more
13-inch MacBook Airs, Apple refurbished, in s...
Apple has Certified Refurbished 2016 13″ MacBook Airs available starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: - 13″ 1.6GHz/8GB/128GB MacBook Air: $... Read more
12-inch Retina MacBooks on sale for $1199, sa...
B&H has 12″ 1.1GHz Retina MacBooks on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 12″ 1.1GHz Space Gray Retina MacBook: $1199 $100 off MSRP - 12″ 1.1GHz... Read more
Save up to $260 with Apple refurbished 12-inc...
Apple has Certified Refurbished 2016 12″ Retina MacBooks available for $200-$260 off MSRP. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The following... Read more

Jobs Board

Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
Desktop Analyst - *Apple* Products - Montef...
…technology to improve patient care. JOB RESPONSIBILITIES: Provide day-to-day support for Apple Hardware and Software in the environment based on the team's support Read more
*Apple* Mobile Master - Best Buy (United Sta...
**493168BR** **Job Title:** Apple Mobile Master **Location Number:** 000827-Denton-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** At Read more
Fulltime aan de slag als shopmanager in een h...
Ben jij helemaal gek van Apple -producten en vind je het helemaal super om fulltime shopmanager te zijn in een jonge en hippe elektronicazaak? Wil jij werken in Read more
*Apple* Mobile Master - Best Buy (United Sta...
**492889BR** **Job Title:** Apple Mobile Master **Location Number:** 000886-Norwalk-Store **Job Description:** **What does a Best Buy Apple Mobile Master do?** Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.