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;
}







  
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Capture One 11.0.1.40 - RAW workflow sof...
Capture One is a professional RAW converter offering you ultimate image quality with accurate colors and incredible detail from more than 400 high-end cameras -- straight out of the box. It offers... Read more
GraphicConverter 10.5.4 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Dash 4.1.3 - Instant search and offline...
Dash is an API documentation browser and code snippet manager. Dash helps you store snippets of code, as well as instantly search and browse documentation for almost any API you might use (for a full... Read more
Microsoft OneNote 16.9 - Free digital no...
OneNote is your very own digital notebook. With OneNote, you can capture that flash of genius, that moment of inspiration, or that list of errands that's too important to forget. Whether you're at... Read more
DEVONthink Pro 2.9.17 - Knowledge base,...
Save 10% with our exclusive coupon code: MACUPDATE10 DEVONthink Pro is your essential assistant for today's world, where almost everything is digital. From shopping receipts to important research... Read more
OmniGraffle 7.6 - Create diagrams, flow...
OmniGraffle helps you draw beautiful diagrams, family trees, flow charts, org charts, layouts, and (mathematically speaking) any other directed or non-directed graphs. We've had people use Graffle to... Read more
iFinance 4.3.7 - Comprehensively manage...
iFinance allows you to keep track of your income and spending -- from your lunchbreak coffee to your new car -- in the most convenient and fastest way. Clearly arranged transaction lists of all your... Read more
Opera 50.0.2762.58 - High-performance We...
Opera is a fast and secure browser trusted by millions of users. With the intuitive interface, Speed Dial and visual bookmarks for organizing favorite sites, news feature with fresh, relevant content... Read more
Microsoft Office 2016 16.9 - Popular pro...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
SoftRAID 5.6.4 - High-quality RAID manag...
SoftRAID allows you to create and manage disk arrays to increase performance and reliability. SoftRAID allows the user to create and manage RAID 4 and 5 volumes, RAID 1+0, and RAID 1 (Mirror) and... Read more

Latest Forum Discussions

See All

Around the Empire: What have you missed...
Around this time every week we're going to have a look at the comings and goings on the other sites in Steel Media's pocket-gaming empire. We'll round up the very best content you might have missed, so you're always going to be up to date with the... | Read more »
The 7 best games that came out for iPhon...
Well, it's that time of the week. You know what I mean. You know exactly what I mean. It's the time of the week when we take a look at the best games that have landed on the App Store over the past seven days. And there are some real doozies here... | Read more »
Popular MMO Strategy game Lords Mobile i...
Delve into the crowded halls of the Play Store and you’ll find mobile fantasy strategy MMOs-a-plenty. One that’s kicking off the new year in style however is IGG’s Lords Mobile, which has beaten out the fierce competition to receive Google Play’s... | Read more »
Blocky Racing is a funky and fresh new k...
Blocky Racing has zoomed onto the App Store and Google Play this week, bringing with it plenty of classic kart racing shenanigans that will take you straight back to your childhood. If you’ve found yourself hooked on games like Mario Kart or Crash... | Read more »
Cytus II (Games)
Cytus II 1.0.1 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0.1 (iTunes) Description: "Cytus II" is a music rhythm game created by Rayark Games. It's our fourth rhythm game title, following the footsteps of three... | Read more »
JYDGE (Games)
JYDGE 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Build your JYDGE. Enter Edenbyrg. Get out alive. JYDGE is a lawful but awful roguehate top-down shooter where you get to build your... | Read more »
Tako Bubble guide - Tips and Tricks to S...
Tako Bubble is a pretty simple and fun puzzler, but the game can get downright devious with its puzzle design. If you insist on not paying for the game and want to manage your lives appropriately, check out these tips so you can avoid getting... | Read more »
Everything about Hero Academy 2 - The co...
It's fair to say we've spent a good deal of time on Hero Academy 2. So much so, that we think we're probably in a really good place to give you some advice about how to get the most out of the game. And in this guide, that's exactly what you're... | Read more »
Everything about Hero Academy 2: Part 3...
In the third part of our Hero Academy 2 guide we're going to take a look at the different modes you can play in the game. We'll explain what you need to do in each of them, and tell you why it's important that you do. [Read more] | Read more »
Everything about Hero Academy 2: Part 2...
In this second part of our guide to Hero Academy 2, we're going to have a look at the different card types that you're going to be using in the game. We'll split them up into different sections too, to make sure you're getting the most information... | Read more »

Price Scanner via MacPrices.net

Deals on clearance 15″ Apple MacBook Pros wit...
B&H Photo has clearance 2016 15″ MacBook Pros available for up to $800 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: – 15″ 2.7GHz Touch Bar MacBook Pro... Read more
Apple restocked Certified Refurbished 13″ Mac...
Apple has restocked a full line of Certified Refurbished 2017 13″ MacBook Airs starting at $849. An Apple one-year warranty is included with each MacBook, and shipping is free: – 13″ 1.8GHz/8GB/128GB... Read more
How to find the lowest prices on 2017 Apple M...
Apple has Certified Refurbished 13″ and 15″ 2017 MacBook Pros available for $200 to $420 off the cost of new models. Apple’s refurbished prices are the lowest available for each model from any... Read more
The lowest prices anywhere on Apple 12″ MacBo...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Apple now offering a full line of Certified R...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for $100-$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
27″ iMacs on sale for $100-$130 off MSRP, pay...
B&H Photo has 27″ iMacs on sale for $100-$130 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): $2199 $100 off MSRP – 27″ 3.... Read more
2.8GHz Mac mini on sale for $899, $100 off MS...
B&H Photo has the 2.8GHz Mac mini (model number MGEQ2LL/A) on sale for $899 including free shipping plus NY & NJ sales tax only. Their price is $100 off MSRP. Read more
Apple offers Certified Refurbished iPad minis...
Apple has Certified Refurbished 128GB iPad minis available today for $339 including free shipping. Apple’s standard one-year warranty is included. Their price is $60 off MSRP. Read more
Amazon offers 13″ 256GB MacBook Air for $1049...
Amazon has the 13″ 1.8GHz/256B #Apple #MacBook Air on sale today for $150 off MSRP including free shipping: – 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A): $1049.99, $150 off MSRP Read more
9.7-inch 2017 WiFi iPads on sale starting at...
B&H Photo has 9.7″ 2017 WiFi #Apple #iPads on sale for $30 off MSRP for a limited time. Shipping is free, and pay sales tax in NY & NJ only: – 32GB iPad WiFi: $299, $30 off – 128GB iPad WiFi... Read more

Jobs Board

*Apple* Data Center Site Selection and Strat...
# Apple Data Center Site Selection and Strategy Research Analyst Job Number: 83708609 Santa Clara Valley, California, United States Posted: 18-Jan-2018 Weekly Hours: Read more
Security Engineering Coordinator, *Apple* R...
# Security Engineering Coordinator, Apple Retail Job Number: 113237456 Santa Clara Valley, California, United States Posted: 18-Jan-2018 Weekly Hours: 40.00 **Job Read more
Firmware Engineer - *Apple* Accessories - A...
# Firmware Engineer - Apple Accessories Job Number: 113422485 Santa Clara Valley, California, United States Posted: 18-Jan-2018 Weekly Hours: 40.00 **Job Summary** Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Store Leader - Retail District Manag...
Job Description:Job SummaryAs more and more people discover Apple , they visit our retail stores seeking ways to incorporate our products into their lives. It's your Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.