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

Latest Forum Discussions

See All

Brawl Stars veteran-backed Octopo Studio...
The 2024 PlayX4 B2B is kicking off tomorrow in Ilsan, lasting until the 26th in KINTEX Hall 1, and Octopo Studio has announced that they will be making an appearance. Shooting RPG Bounty Pang will be on show as the developers seek publishing... | Read more »
The Astral Express sets off to bring Hon...
After vanquishing yet another threat and adding a fine hat to their wardrobe, you’d think the crew of the Astral Express would be able to kick back after their adventures in Penacony. Clearly not though, as HoYo has announced the next leg of the... | Read more »
Dragons rein supreme in Pokemon Unite as...
If you were looking for the strongest type in Pokemon and asked the fanbase, I would wager most people's thoughts would turn to Dragon. They hit hard, are often powerful, and get used by some of the toughest trainers. Pokemon Unite is honouring... | Read more »
Players can take a peek into the design...
It doesn’t matter how much effort developers put into their classes, or how many special little mechanics there are; if there is one that wields two blades, I’m ignoring everything else. Diablo Immortal recently announced such a class in the shape... | Read more »
Android users have a new option in the c...
When you are in the thick of a firefight or trying to pull off a mid-combat parkour flip through a squad of foes, sometimes touchscreen control just won’t do it for you. For those intense sessions, you could benefit from a good mobile controller,... | Read more »
Jagex releases the first of three origin...
At this point, I am sure everyone has heard of Runescape, and or Runescape Classic. It has been going strong for 23 years, with constant content and story coming out. Luckily for fans of the game, or fantasy in general, Jagex has announced an... | Read more »
Watcher of Realms unveils new story and...
Watcher of Realms players are in for quite the feast this month, as Moonton release two powerful new heroes, including one that will burst down even the most mighty of foes. Recruit your new friends, and then burn through the Main Quest expansion... | Read more »
Reverse: 1999 continues its trip down un...
The field trip to Australia continues in Reverse: 1999 as Phase 2 of Revival! The Uluru Games kicks off. You will be able to collect new characters, engage with new events, get hordes of free gifts, and follow the story of a mushroom-based... | Read more »
Ride into the zombie apocalypse in style...
Back in the good old days of Flash games, there were a few staples; Happy Wheels, Stick RPG, and of course the apocalyptic driver Earn to Die. Fans of the running over zombies simulator can rejoice, as the sequel to the legendary game, Earn to Die... | Read more »
Top Mobile Game Discounts
Every day, we pick out a curated list of the best mobile discounts on the App Store and post them here. This list won't be comprehensive, but it every game on it is recommended. Feel free to check out the coverage we did on them in the links below... | Read more »

Price Scanner via MacPrices.net

Amazon is blowing out clearance 13-inch M1 Ma...
Amazon has clearance Apple 13″ M1 MacBook Airs on Memorial Day sale for $300 off original MSRP, only $699. Their prices are the lowest available for new MacBooks this Holiday shopping season. Stock... Read more
MacBook Sale! 13-inch M2 MacBook Airs are onl...
Best Buy has Apple 13″ MacBook Airs with M2 CPUs in stock and back on sale this week on their online store for $150 off MSRP in Space Gray, Silver, Starlight, and Midnight colors. Prices start at... Read more
Apple increases iPhone trade-in values ahead...
Get up to $650 on the purchase of new or refurbished iPhone at Apple using their official Trade In program, now with increased values ahead of WWDC 2024. Trade in your old iPhone, and Apple will... Read more
Amazon has Apple’s iPad discounted to a new l...
Amazon has Apple’s 10th-generation WiFi iPads on sale discounted up to $40 off MSRP, starting at only $334. With the discounts, Amazon’s prices are the lowest we’ve seen for these iPads: – 10″ 10th-... Read more
13-inch M3 MacBook Airs on sale for $100 off...
Best Buy has Apple 13″ MacBook Airs with M3 CPUs in stock and on sale this week for $100 off MSRP. Prices start at $999. Their prices, along with Amazon’s, are the lowest currently available for new... Read more
Weekend Deal! Best Buy has Apple Watch Series...
Best Buy has Apple Watch Series 9 models on sale for $100 off MSRP on their online store this weekend. Sale prices available for online orders only, in-store prices may vary. Order online, and choose... Read more
Apple Watch SE on sale starting at $199 this...
Best Buy has all Apple Watch SE models on sale this weekend for $50 off MSRP on their online store. Sale prices available for online orders only, in-store prices may vary. Order online, and choose... Read more
Mac Pro with M2 Ultra CPU on sale for $6699,...
In the market for one of Apple’s Mac Pro towers? B&H Photo has the base Mac Pro with an Apple M2 Ultra CPU, 64GB RAM, and 1TB SSD on sale for $6699 including free 1-2 day shipping to most... Read more
New May Verizon promotion: Switch and get a f...
Red Hot Deal Days at Verizon: Switch to Verizon this month, and get the 256GB iPhone 15 Pro for free, with trade-in, when you add a new line of service. Verizon is also offering a free cellular iPad... Read more
Updated Apple MacBook Price Trackers
Our Apple award-winning MacBook Price Trackers are continually updated with the latest information on prices, bundles, and availability for 16″ and 14″ MacBook Pros along with 13″ and 15″ MacBook... Read more

Jobs Board

Salon Manager BTC - *Apple* Blossom Mall -...
Salon Manager BTC - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/144535/winchester-va-united-states) - Job Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Beauty Consultant - *Apple* Blossom Mall -...
Beauty Consultant - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Hair Stylist - *Apple* Blossom Mall - JCPen...
Hair Stylist - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.