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

Call of Duty Warzone is a Waiting Simula...
It's always fun when a splashy multiplayer game comes to mobile because they are few and far between, so I was excited to see the notification about Call of Duty: Warzone Mobile (finally) launching last week and wanted to try it out. As someone who... | Read more »
Albion Online introduces some massive ne...
Sandbox Interactive has announced an upcoming update to its flagship MMORPG Albion Online, containing massive updates to its existing guild Vs guild systems. Someone clearly rewatched the Helms Deep battle in Lord of the Rings and spent the next... | Read more »
Chucklefish announces launch date of the...
Chucklefish, the indie London-based team we probably all know from developing Terraria or their stint publishing Stardew Valley, has revealed the mobile release date for roguelike deck-builder Wildfrost. Developed by Gaziter and Deadpan Games, the... | Read more »
Netmarble opens pre-registration for act...
It has been close to three years since Netmarble announced they would be adapting the smash series Solo Leveling into a video game, and at last, they have announced the opening of pre-orders for Solo Leveling: Arise. [Read more] | Read more »
PUBG Mobile celebrates sixth anniversary...
For the past six years, PUBG Mobile has been one of the most popular shooters you can play in the palm of your hand, and Krafton is celebrating this milestone and many years of ups by teaming up with hit music man JVKE to create a special song for... | Read more »
ASTRA: Knights of Veda refuse to pump th...
In perhaps the most recent example of being incredibly eager, ASTRA: Knights of Veda has dropped its second collaboration with South Korean boyband Seventeen, named so as it consists of exactly thirteen members and a video collaboration with Lee... | Read more »
Collect all your cats and caterpillars a...
If you are growing tired of trying to build a town with your phone by using it as a tiny, ineffectual shover then fear no longer, as Independent Arts Software has announced the upcoming release of Construction Simulator 4, from the critically... | Read more »
Backbone complete its lineup of 2nd Gene...
With all the ports of big AAA games that have been coming to mobile, it is becoming more convenient than ever to own a good controller, and to help with this Backbone has announced the completion of their 2nd generation product lineup with their... | Read more »
Zenless Zone Zero opens entries for its...
miHoYo, aka HoYoverse, has become such a big name in mobile gaming that it's hard to believe that arguably their flagship title, Genshin Impact, is only three and a half years old. Now, they continue the road to the next title in their world, with... | Read more »
Live, Playdate, Live! – The TouchArcade...
In this week’s episode of The TouchArcade Show we kick things off by talking about all the games I splurged on during the recent Playdate Catalog one-year anniversary sale, including the new Lucas Pope jam Mars After Midnight. We haven’t played any... | Read more »

Price Scanner via MacPrices.net

Deal Alert! B&H Photo has Apple’s 14-inch...
B&H Photo has new Gray and Black 14″ M3, M3 Pro, and M3 Max MacBook Pros on sale for $200-$300 off MSRP, starting at only $1399. B&H offers free 1-2 day delivery to most US addresses: – 14″ 8... Read more
Department Of Justice Sets Sights On Apple In...
NEWS – The ball has finally dropped on the big Apple. The ball (metaphorically speaking) — an antitrust lawsuit filed in the U.S. on March 21 by the Department of Justice (DOJ) — came down following... Read more
New 13-inch M3 MacBook Air on sale for $999,...
Amazon has Apple’s new 13″ M3 MacBook Air on sale for $100 off MSRP for the first time, now just $999 shipped. Shipping is free: – 13″ MacBook Air (8GB RAM/256GB SSD/Space Gray): $999 $100 off MSRP... Read more
Amazon has Apple’s 9th-generation WiFi iPads...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for $80-$100 off MSRP, starting only $249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Discounted 14-inch M3 MacBook Pros with 16GB...
Apple retailer Expercom has 14″ MacBook Pros with M3 CPUs and 16GB of standard memory discounted by up to $120 off Apple’s MSRP: – 14″ M3 MacBook Pro (16GB RAM/256GB SSD): $1691.06 $108 off MSRP – 14... Read more
Clearance 15-inch M2 MacBook Airs on sale for...
B&H Photo has Apple’s 15″ MacBook Airs with M2 CPUs (8GB RAM/256GB SSD) in stock today and on clearance sale for $999 in all four colors. Free 1-2 delivery is available to most US addresses.... Read more
Clearance 13-inch M1 MacBook Airs drop to onl...
B&H has Apple’s base 13″ M1 MacBook Air (Space Gray, Silver, & Gold) in stock and on clearance sale today for $300 off MSRP, only $699. Free 1-2 day shipping is available to most addresses in... Read more
New promo at Visible: Buy a new iPhone, get $...
Switch to Visible, and buy a new iPhone, and Visible will take $10 off their monthly Visible+ service for 24 months. Visible+ is normally $45 per month. With this promotion, the cost of Visible+ is... Read more
B&H has Apple’s 13-inch M2 MacBook Airs o...
B&H Photo has 13″ MacBook Airs with M2 CPUs and 256GB of storage in stock and on sale for $100 off Apple’s new MSRP, only $899. Free 1-2 day delivery is available to most US addresses. Their... Read more
Take advantage of Apple’s steep discounts on...
Apple has a full line of 16″ M3 Pro and M3 Max MacBook Pros available, Certified Refurbished, starting at $2119 and ranging up to $600 off MSRP. Each model features a new outer case, shipping is free... Read more

Jobs Board

Medical Assistant - Surgical Oncology- *Apple...
Medical Assistant - Surgical Oncology- Apple Hill Location: WellSpan Medical Group, York, PA Schedule: Full Time Sign-On Bonus Eligible Remote/Hybrid Regular Apply 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
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall 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
Business Analyst | *Apple* Pay - Banco Popu...
Business Analyst | Apple PayApply now " Apply now + Apply Now + Start applying with LinkedIn Start + Please wait Date:Mar 19, 2024 Location: San Juan-Cupey, PR Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.