TweetFollow Us on Twitter

Dec 94 Challenge
Volume Number:10
Issue Number:12
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. 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, we’ll choose one winner at random (with honorable mention, but no prize, given to the runners up). The prize for each month’s best solution is $50 and a limited-edition “The Winner! MacTech Magazine Programming Challenge” T-shirt (not available in stores).

To help us make fair comparisons, all solutions must be in ANSI compatible C (e.g. don’t use Think’s Object extensions). Use only pure C code. We disqualify any entries with any assembly in them (except for challenges specifically stated to be in assembly). You may call any routine in the Macintosh toolbox (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 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 with e-mail gateways and page layout.

We publish the solution and winners for this month’s Programmers’ Challenge 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 info. If you send via snail mail, send a disk with those items on it; see “How to Contact Us” on p. 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.

Rubik’s Cube

There are several things I’m good at. Solving Rubik’s Cube isn’t one of them. One of my sadist friends gave me one last Christmas. I scramble it all the time and leave it on my desk at work. Then I watch in amazement as any one of several co-workers walks up to it and solves it within the amount of time it takes to ask “Mike, what’s the fastest way to do buffered file I/O?” It’s very frustrating.

This month’s challenge idea comes not only from my own inadequacy but also from Jim Lloyd (Mountain View, CA). The goal is to solve Rubik’s Cube.

The prototype of the function you write is:


/* 1 */
int
SolveRubiksCube(cubePtr)
RubiksCube*cubePtr;

Since I am so pathetic at solving the cube, I do not have enough insight to design an effective data structure to represent it. You get to define the RubiksCube typedef anyway you like.

Each call to SolveRubiksCube should make exactly one move. A move means turning any side any direction by 90 degrees. The function returns one of 3 values on each call to it:


/* 2 */
 -1   illegal cube condition, can’t be solved
  0   made a move, but not done yet
  1   made the last move, it’s solved

Your routine will be called in a loop from my test bench something like this:


/* 3 */
ScrambleCube(cubePtr);
do {
 x = SolveRubiksCube(cubePtr);
} while (x == 0);

Minimizing the number of moves to solve the cube is not important. Minimizing the total time required to solve the cube is important. If your SolveRubiksCube routine needs to keep track of some kind of state info or cached solution info between calls to it then it may use static variables to do so (or, you could incorporate that info into the RubiksCube data structure).

It is not required to detect an illegal cube condition on the first call to SolveRubiksCube, just so long as it is detected eventually (i.e. don’t go into an infinite loop if someone removes a couple of squares from your cube and puts them back in such a way that it makes the cube unsolvable).

Because I will need to be able to watch your routine’s progress, you will need to write two conversion routines:


/* 4 */
void
MikeCubeToRubiksCube(mikePtr, rubikPtr)
MikeCube*mikePtr;
RubiksCube*rubikPtr;

void
RubiksCubeToMikeCube(rubikPtr, mikePtr)
RubiksCube*rubikPtr;
MikeCube*mikePtr;

The purpose is to convert your cube from whatever data structure you come up with into something my test bench can understand. It only knows about MikeCubes:


/* 5 */
typedef struct CubeSide {
 char   littleSquare[3][3];
} CubeSide;

typedef struct MikeCube {
 CubeSide face[6];
} MikeCube;

A cube has 6 CubeSides. If you look at a cube straight on then the indexes are: 0 = top, 1 = left side, 2 = front, 3 = right side, 4 = bottom, 5 = back. Within each CubeSide there is a 3x3 array of littleSquares (first index is row, second index is column). Each littleSquare is a number from 0 to 5, where each number represents one of the 6 colors that make up a cube.

So, a solved cube would have all 9 of the littleSquares for each side set to the same value. A solved cube that had the rightmost vertical column rotated counterclockwise 90 degrees would look like this:

   005
   005
   005
111220333
111220333
111220333
   442
   442
   442
   554
   554
   554

The top part (the 005 lines) represent the top of the cube after the rotation. The 220 pieces are what you see on the front, the 442 lines are what you see on the bottom and the 554 pieces are what’s on the back. The value of mikePtr-> face[0]. littleSquare[1][2] is 5. The value of mikePtr->face[0].littleSquare[1][1] is 0 (the center square of the top).

Write to me if you have questions on this. Your conversion routines are not going to be part of your times so it doesn’t matter if they’re slow. Have fun.

Two Months Ago Winner

Based on the number of entries I received for the How Long Will It Take Challenge I would have to say that software time estimates are even more difficult than their well-deserved reputation implies. Either that or the typical Programmer Challenge entrant isn’t concerned with schedules (or, at least, this Challenge). In any case, congrats (and thanks) to Jeremy Vineyard (Lawrence, KS) for winning. I suppose the fact that he was the only person to enter helped his entry somewhat but there are signs of some careful thinking in his entry as well. (Although I must confess that I find the inclusion of a Jolt Cola parameter completely useless. Mountain Dew on the other hand...) This is Jeremy’s second 1st place showing (he also won the Insane Anglo Warlord challenge in February, 1993). Nice job!

Jeremy’s entry refers to a book by E. Barne called “Estimation of Time-Space Development Theorems” which I wasn’t, unfortunately, able to track down before my column deadline. Sounds like something to check out, though, if you’re involved with scheduling.

Here’s Jeremy’s winning solution:

Top 5 Excuses Why This Project Was Late:

1. “I though you said it was due NEXT month!”

2. The Product Manager quit after we missed the beta acceptance deadline.

3. Somebody activated the fire alarm while we were holding a brainstorming session, and all our ideas were lost.

4. QA didn’t keep us up to date on active bugs.

5. I just couldn’t wait to try out the new game of solitaire that came with System 7.5!

The skill of the product manager is the key to a successful product.

 
/* 6 */
enum {
 // Manager ratings. 
 noManager = 0,
 lazyManager = 1,
 poorManager = 2,
 okManager = 3,
 motivatedManager = 4,
 excellentManager = 5
};

enum {
 // System versions. 
 system7 = 7,
 system6 = 6,
 system5 = 5,
 system4 = 4,
 system3 = 3,
 system2 = 2,
 system1 = 1
};


// It assumed that the better the manager is, the more lines
// the engineers will be motivated to write.
#define juniorLines(100 + (20 * manager))
#define seniorLines(200 + (25 * manager))

// Every large project will have an overhead for planning,
// designing, and preparing for development.
#define overhead (linesC / 5000)

// These ratios are based on Barne’s matrix equations
// related to the study of time-space software development
// theorems. (trust me!)
#define PPCNativeRatio    (float) (1.75 - (.02 * powerMacs))
#define joltRatio(float) (.7)
#define systemSupportRatio(float) (7.0 / systemSupport)

// Here again,the manager can motivate both QA and UI
// people to be more productive.
#define qaRatio  1 - (.1 + (.01 * manager) * qaPeople)
#define uiRatio  (float) ((1.2 - \
 (.01 * manager)) * (seniorEng - uiPeople))

// Localization- a nightmare. Enough said.
#define localizedRatio    (float) (1.35 * localized)

SoftwareTimeEstimate

A simplified algorithm that accurately calculates the time in calendar days for any Macintosh software product to be completed.

The complete algorithm and collection of equations can be found in E. Barne’s Estimation of Time-Space Development Theorems, published by Academic Press.

Implementation by Jeremy Vineyard, Lawrence, KS


/* 7 */
SoftwareTimeEstimate

unsigned short SoftwareTimeEstimate(linesC, seniorEng,
 juniorEng, systemSupport, PPCNative, powerMacs, manager,
 jolt, qaPeople, uiPeople, localized)
 
 // Estimated # lines of source code in C.
 unsigned long linesC;

 // # of competent engineers with more than 5
 // years experience.
 unsigned short seniorEng;
 
 // # of junior engineers with less than 2
 // years experience.
 unsigned short juniorEng;

 // Earliest version of system software supported by
 // product (1-7)
 unsigned short systemSupport;

 // TRUE if product will be PowerPC native.
 Boolean PPCNative;
 
 // # of PowerMacs available to developers (1-30).
 unsigned short powerMacs;

 // Rating of manager 1-5 (1 is poor, 5 is excellent)
 // or 0 if none.
 unsigned short manager;

 // TRUE if company has steady supply of Jolt cola.
 Boolean jolt;   
 
 // # of trained, in-house testers (most important).
 unsigned short qaPeople;
 
 // # of people responsible for making decisions about UI.     
 unsigned short uiPeople;
 
 // # of Languages product must be localized to before
 // shipping or 0 if none.
 unsigned short localized;
{
 float  time, ratio;
 short  linesADay;
 

 // Calculate the lines of source code that can be 
 // produced per day based upon the number of engineers 
 // working on the product.
 // (Must have at least one engineer)
 linesADay = (seniorEng * seniorLines) 
  + (juniorEng * juniorLines);
 
 // Estimate the # of days it will take to produce the   
 // specified amount of code. 
 time = (linesC / linesADay) + overhead;
 
 // The farther backwards this product is compatible with      
 
 // system versions, the more time it will take to develop.    
 
 // systemSupport should be from 1 (System 1.0) to 7.
 time *= systemSupportRatio;
 
 // More development & QA time will need to be spent on  
 // a product that is PowerPC native. The more Power Macs
 // that are available to developers, the faster the 
 // development & testing process will proceed.                
 
 if (PPCNative)
 time *= PPCNativeRatio;
 
 // o JOLT COLA!  o
 // o GIve the PRogramMeRS that EXtra ZING! to geT thEm o
 // o MOTIVATED!! o
 if (jolt)
 time *= joltRatio;

 // Quality assurance is one of the most important             
 // aspects of a product’s construction.  Without it, the      
 
 // product will fail to reach the user base because of 
 // too many bugs. QA can never be overstaffed!                
 
 time *= qaRatio;

 // User interface has a limited potential because people      
 // are likely to have very set opinions, and if there 
 // are too many UI people, it can kill a product. There       
 // should never be more UI personnel than engineers.    
 if (uiPeople > seniorEng)
 time *= uiRatio;

 // The more languages the product must be localized to
 // before it can be shipped has a drastic effect on the
 // development time.
 if (localized)
 time *= localizedRatio;
 
 return (short) time;
}







  
 
AAPL
$102.99
Apple Inc.
+0.52
MSFT
$44.38
Microsoft Corpora
-0.50
GOOG
$532.71
Google Inc.
+6.17

MacTech Search:
Community Search:

Software Updates via MacUpdate

OmniOutliner 4.1.3 - Organize your ideas...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
BBEdit 11.0 - Powerful text and HTML edi...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
Apple Security Update 2014-005 - For OS...
Apple Security Update is recommended for all users and improves the security of Mac OS X. For information on the security content of this update, please visit this website: http://support.apple.com/... Read more
EyeTV 3.6.6 - Watch and record TV on you...
EyeTV brings a rich TV experience to your Mac. Watch live TV on your Mac. Pause, rewind, and record whenever you want. EyeTV gives you powerful control over what you watch and how you watch it. Put... Read more
RapidWeaver 6.0 - Create template-based...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
NTFS 12.0.39 - Provides full read and wr...
Paragon NTFS breaks down the barriers between Windows and OS X. Paragon NTFS effectively solves the communication problems between the Mac system and NTFS, providing full read and write access to... Read more
RestoreMeNot 2.0.3 - Disable window rest...
RestoreMeNot provides a simple way to disable the window restoration for individual applications so that you can fine-tune this behavior to suit your needs. Please note that RestoreMeNot is designed... Read more
Macgo Blu-ray Player 2.10.9.1750 - Blu-r...
Macgo Mac Blu-ray Player can bring you the most unforgettable Blu-ray experience on your Mac. Overview Macgo Mac Blu-ray Player can satisfy just about every need you could possibly have in a Blu-ray... Read more
Apple iOS 8.1 - The latest version of Ap...
The latest version of iOS can be downloaded through iTunes. Apple iOS 8 comes with big updates to apps you use every day, like Messages and Photos. A whole new way to share content with your family.... Read more
TechTool Pro 7.0.5 - Hard drive and syst...
TechTool Pro is now 7, and this is the most advanced version of the acclaimed Macintosh troubleshooting utility created in its 20-year history. Micromat has redeveloped TechTool Pro 7 to be fully 64... Read more

Latest Forum Discussions

See All

TinType by Hipstamatic (Photography)
TinType by Hipstamatic 1.0 Device: iOS iPhone Category: Photography Price: $.99, Version: 1.0 (iTunes) Description: Create hauntingly beautiful, soul capturing portraits with TinType by Hipstamatic. Inspired by daguerreotypes,... | Read more »
The Latest Update for Heroes of Dragon A...
The Latest Update for Heroes of Dragon Age Introduces Daily PvE Challenges Posted by Ellis Spice on October 22nd, 2014 [ permalink ] | Read more »
A New Trailer has Been Revealed for Epic...
A New Trailer has Been Revealed for Epic of Kings Posted by Jessica Fisher on October 22nd, 2014 [ permalink ] Dead Mage Inc. has released a new, action-packed trailer for the upcoming Epic of Kings. | Read more »
Find the Line Review
Find the Line Review By Campbell Bird on October 22nd, 2014 Our Rating: :: INSLIDE THE LINESUniversal App - Designed for iPhone and iPad Tease out beautiful line drawings in this unique, free-to-play puzzle game.   | Read more »
The Silent Age Episode 2 Review
The Silent Age Episode 2 Review By Jennifer Allen on October 22nd, 2014 Our Rating: :: ROUNDING THINGS OFF NICELYUniversal App - Designed for iPhone and iPad Rounding off a great point and click adventure comes The Silent Age... | Read more »
Craft Your Own Mini-Games with Papercade
Craft Your Own Mini-Games with Papercade Posted by Jessica Fisher on October 22nd, 2014 [ permalink ] iPad Only App - Designed for the iPad Scrapbookers move over, Scrapgaming is the new thing. | Read more »
Reshape Review
Reshape Review By Jennifer Allen on October 22nd, 2014 Our Rating: :: SIMPLE SHAPESUniversal App - Designed for iPhone and iPad Match triangles together to form cubes in this fast-paced and twitchy game.   | Read more »
Miika (Games)
Miika 1.0.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.0 (iTunes) Description: Miika is a beautiful 3D puzzle game based on camera perspectives combined with the use of optical illusions. Miika challenges... | Read more »
Infuse Pro (Photography)
Infuse Pro 3.0 Device: iOS Universal Category: Photography Price: $9.99, Version: 3.0 (iTunes) Description: ** All-new version 3 includes fully licensed and certified DTS® and DTS-HD® audio! ** | Read more »
Swap Heroes (Games)
Swap Heroes 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: **Half price for a limited time only** Swap Heroes is a casual turn-based strategy adventure. Form a group of heroes and guide them... | Read more »

Price Scanner via MacPrices.net

Save with Best Buy’s College Student Deals
Take an additional $50 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through November 1st. Anyone with a valid .EDU email address can take advantage... Read more
iPad Air 2 & iPad mini 3 Best Tablets Yet...
The new iPads turned out to be pretty much everything I’d been hoping for and more than I’d expected.”More” particularly in terms of a drinking-from-a-firehose choice of models and configurations,... Read more
Drafts 4 Reinvents iOS Productivity App
N Richland Hills, Texas based Agile Tortoise has announced the release of Drafts 4 for iPhone and iPad. Drafts is a quick capture note taking app with flexible output actions. Drafts 4 scales from... Read more
AT&T accepting preorders for new iPads fo...
AT&T Wireless is accepting preorders for the new iPad Air 2 and iPad mini 3, cellular models, for $100 off MSRP with a 2-year service agreement: - 16GB iPad Air 2 WiFi + Cellular: $529.99 - 64GB... Read more
Apple offering refurbished Mac Pros for up to...
The Apple Store is offering Apple Certified Refurbished 2013 Mac Pros for up to $600 off the cost of new models. An Apple one-year warranty is included with each Mac Pro, and shipping is free. The... Read more
Select MacBook Airs $100 off MSRP, free shipp...
B&H Photo has 2014 a couple of MacBook Airs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only. They also include free copies of Parallels Desktop and LoJack for... Read more
13-inch 2.5GHz MacBook Pro on sale for $100 o...
B&H Photo has the 13″ 2.5GHz MacBook Pro on sale for $999.99 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Read more
Strong iPhone, Mac And App Store Sales Drive...
Apple on Monday announced financial results for its fiscal 2014 fourth quarter ended September 27, 2014. The Company posted quarterly revenue of $42.1 billion and quarterly net profit of $8.5 billion... Read more
Apple Posts How-To For OS X Recovery
OS X 10.7 Lion and later include OS X Recovery. This feature includes all of the tools you need to reinstall OS X, repair your disk, and even restore from a Time Machine backup. OS X Recovery... Read more
Mac OS X Versions (Builds) Supported By Vario...
Apple Support has posted a handy resource explaining which Mac OS X versions (builds) originally shipped with or are available for your computer via retail discs, downloads, or Software Update. Apple... Read more

Jobs Board

Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Position Opening at *Apple* - Apple (United...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.