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 progchallenge@xplain.com, 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[] = \
“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);
}







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

How to become the ultimate robot warrior...
Chrono Strike is a delightfully immersive beat ‘em up with a sense of humor (any game with a good Sims reference gets points in my book). [Read more] | Read more »
Tips and tricks to get a higher score in...
Snow Roll is a devilish endless runner very much in the vein of Flappy Bird. It revels in its dastardly level of difficulty, and doesn’t really care how angry you get at it as it knows you’ll keep coming back for more. [Read more] | Read more »
How to win big in Slots Deluxe
Cheating while gambling is illegal and morally wrong, and in some parts of the world it leads to men with names like Vinnie "Six Knuckles" Manchenzo beating you to a pulp in a dark alley. [Read more] | Read more »
How to take over the world in Dictator 2
Running a country isn't easy - especially when you're a dictator who wants to take over the world and crush everyone in your path while you do it. [Read more] | Read more »
Tips and tricks to get a higher score in...
Tank.iois - you guessed it! - another multiplayer arena battler likeAgar.io and Slither.io. It does differentiate itself by putting you in a tiny tank though, so it's not exactly the same. To help you get that all-important high score, we've got a... | Read more »
How to unlock characters in One Tap Tenn...
As the title suggests, One Tap Tennis requires only a single tap to play its particular brand of tennis, and rewards you with a ton of unlockable characters if you perform well. Fortunately for you, we at 148Apps have got a few tips and tricks to... | Read more »
Grab it now: Game Craft’s Legend of War...
The real time strategy game is now available for you to sink your teeth into, through the App Store and Google Play. Combining elements of skill, strategy and empire building, Legend of War is a real gamers’ game. [Read more] | Read more »
Skateboard Party 3 ft. Greg Lutzka (Gam...
Skateboard Party 3 ft. Greg Lutzka 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Skateboard Party is back! This third edition of the popular sports franchise features professional skater... | Read more »
Cubious (Games)
Cubious 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: Cubious – How smart are you? How high is your IQube? Solve the impossible puzzles to find out, and help a lost little cube find his... | Read more »
Goat Simulator Waste of Space (Games)
Goat Simulator Waste of Space 1.1 Device: iOS Universal Category: Games Price: $4.99, Version: 1.1 (iTunes) Description: ** IMPORTANT - SUPPORTED DEVICESiPhone 4S, iPad 2, iPod Touch 5 or better.** | Read more »

Price Scanner via MacPrices.net

Enterprise Workers Pick Technology Over Perks...
New Adobe study shows surprising attitudes about office jobs and where the future of work is heading. Adobe has released survey findings revealing that a surprising 70 percent of U.S. office workers... Read more
Memorial Day Weekend Sale: $50-$100 off 11-in...
B&H Photo has 13″ and 11″ MacBook Airs with 256GB SSDs on sale for $50-$100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 1.6GHz/256GB MacBook Air: $999 $100 off MSRP... Read more
Memorial Day Weekend Sales: Apple MacBook Pro...
B&H Photo has 13″ and 15″ Retina MacBook Pros on sale for up to $210 off MSRP. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799 $200 off MSRP - 15″ 2.5GHz... Read more
Memorial Day Weekend Sales: Apple iMacs and M...
Take up to $150 off the price of a new iMac or Mac mini at the following Apple resellers this Memorial Day weekend: iMacs: B&H Photo has 21″ and 27″ iMacs on sale for up to $150 off MSRP... Read more
Apple refurbished Retina MacBook Pros availab...
Apple has Certified Refurbished 2015 13″ and 15″ Retina MacBook Pros available for up to $380 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free... Read more
Apple refurbished 11-inch MacBook Airs availa...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models), available for up to $170 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is... Read more
Goal Zero and OtterBox Partner to Expand iPh...
Goal Zero, specialists in portable power, have announced a partnership with OtterBox, brand smartphone case protection, to offer the Slide and Slide Plus Batteries as modules compatible with the new... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has 15″ Retina MacBook Pros on sale for up to $210 off MSRP. Shipping is free, and B&H charges NY tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799 $200 off MSRP - 15″ 2.5GHz Retina... Read more
Clearance 2015 13-inch MacBook Airs available...
B&H Photo has clearance 2015 13″ MacBook Airs available for $250 off original MSRP. Shipping is free, and B&H charges NY sales tax only: - 13″ 1.6GHz/4GB/128GB MacBook Air (MJVE2LL/A): $799... Read more
Apple refurbished Apple TVs available for up...
Apple has Certified Refurbished 32GB and 64GB Apple TVs available for up to $30 off the cost of new models. Apple’s standard one-year warranty is included with each model, and shipping is free: -... Read more

Jobs Board

*Apple* Solutions Consultant - APPLE (United...
Job Summary As an Apple Solutions Consultant, you'll be the link between our future customers and our products. You'll showcase your entrepreneurial spirit as you Read more
*Apple* Project Engineer - Smart Source Inc...
SmartSource is in need of an Apple Project Engineer for a 12 month contract opportunity in Pittsburg, PA. Role: Apple Project Engineer Location: Pittsburg, PA Read more
Automotive Sales Consultant - Apple Ford Linc...
…you. The best candidates are smart, technologically savvy and are customer focused. Apple Ford Lincoln Apple Valley is different, because: $30,000 annual salary Read more
Service Assistant - *Apple* Chevrolet *App...
Apple Automotive is one of the fastest growing dealer...and it shows. Consider making the switch to the Apple Automotive Group today! At Apple Automotive, we Read more
Editor, *Apple* News - APPLE (United States...
Job Summary The Apple News team is looking for a passionate and knowledgeable editor with experience covering entertainment/pop culture and experience running social Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.