Programmer’s Challenge

By Mike Scanlin, Mountain View, CA

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

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[] = \
“0123456789”\
“0123456789”\
...
“0123456789”;

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

BlockMoveData

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

// 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, 
        outputText,
        numInputBytes, 
        maxOutputBytes,
        width,
        grouping)
   
  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,
          numberOfLines,asciiOffset,lastLineLength;
        
 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[] = "\
000102030405060708090A0B0C0D0E0F\
101112131415161718191A1B1C1D1E1F\
202122232425262728292A2B2C2D2E2F\
303132333435363738393A3B3C3D3E3F\
404142434445464748494A4B4C4D4E4F\
505152535455565758595A5B5C5D5E5F\
606162636465666768696A6B6C6D6E6F\
707172737475767778797A7B7C7D7E7F\
808182838485868788898A8B8C8D8E8F\
909192939495969798999A9B9C9D9E9F\
A0A1A2A3A4A5A6A7A8A9AAABACADAEAF\
B0B1B2B3B4B5B6B7B8B9BABBBCBDBEBF\
C0C1C2C3C4C5C6C7C8C9CACBCCCDCECF\
D0D1D2D3D4D5D6D7D8D9DADBDCDDDEDF\
E0E1E2E3E4E5E6E7E8E9EAEBECEDEEEF\
F0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFF";

  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 
done.
   
 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. 
*/

 numberOfLines++;
 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++ = '.';
 else
 *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.
 memset(outputText,space,lineLength);

 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++ = '.';
 else
 *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.
 *outputText++;
 
 } while (--eCntr);// End of groups per line loop.
 
 }  // end if

   AllDone:

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