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

Path Finder 7.5 - Powerful, award-winnin...
Path Finder makes you a master of file management. Take full control over your file system. Save your time: compare and synchronize folders, view hidden files, use Dual Pane and full keyboard... Read more
Merlin Project 4.2.3 - $349.00
Merlin Project is the leading professional project management software for OS X. If you plan complex projects on your Mac, you won’t get far with a simple list of tasks. Good planning raises... Read more
TextSoap 8.4 - Automate tedious text doc...
TextSoap can automatically remove unwanted characters, fix up messed up carriage returns, and do pretty much anything else that we can think of to text. Save time and effort. Be more productive. Stop... Read more
Smultron 9.4 - Easy-to-use, powerful tex...
Smultron 9 is an elegant and powerful text editor that is easy to use. Use it to create or edit any text document. Everything from a web page, a note or a script to any single piece of text or code.... Read more
QuarkXPress 13.0.0.0 - Desktop publishin...
QuarkXPress 2017 is the new version that raises the bar for design and productivity. With non-destructive graphics and image editing directly within your layout, you no longer have to choose between... Read more
Brackets 1.9.0 - Open Source Web design...
Brackets is an Open-Source editor for Web design and development built on top of Web technologies such as HTML, CSS, and JavaScript. The project was created and is maintained by Adobe, and is... Read more
Audio Hijack 3.3.4 - Record and enhance...
Audio Hijack (was Audio Hijack Pro) drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio... Read more
Tunnelblick 3.7.1a - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Amazon Chime 4.3.5721 - Amazon-based com...
Amazon Chime is a communications service that transforms online meetings with a secure, easy-to-use application that you can trust. Amazon Chime works seamlessly across your devices so that you can... Read more
BBEdit 11.6.6 - Powerful text and HTML e...
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

Latest Forum Discussions

See All

Jaipur: A Card Game of Duels (Games)
Jaipur: A Card Game of Duels 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: ** WARNING: iPad 2, iPad Mini 1 & iPhone 4S are NOT compatible. ** *** Special Launch Price for a limited... | Read more »
Subdivision Infinity (Games)
Subdivision Infinity 1.03 Device: iOS Universal Category: Games Price: $2.99, Version: 1.03 (iTunes) Description: Launch sale! 40% Off! Subdivision Infinity is an immersive and pulse pounding sci-fi 3D space shooter. https://www.... | Read more »
Clash of Clans' gets a huge new upd...
Clash of Clans just got a massive new update, and that's not hyperbole. The update easily tacks on a whole new game's worth of content to the hit base building game. In the update, that mysterious boat on the edge of the map has been repaired and... | Read more »
Thimbleweed Park officially headed to iO...
Welp, it's official. Thimbleweed Park will be getting a mobile version. After lots of wondering and speculation, the developers confirmed it today. Thimbleweed Park will be available on both iOS and Android sometime in the near future. There's no... | Read more »
Pokémon GO might be getting legendaries...
The long-awaited legendary Pokémon may soon be coming to Pokémon GO at long last. Data miners have already discovered that the legendary birds, Articuno, Moltres, and Zapdos are already in the game, it’s just a matter of time. [Read more] | Read more »
The best deals on the App Store this wee...
If you’ve got the Monday blues we have just the thing to cheer you up. The week is shaping up to be a spectacular one for sales. We’ve got a bunch of well-loved indie games at discounted prices this week along with a few that are a little more... | Read more »
Honor 8 Pro, a great choice for gamers
Honor is making strides to bring its brand to the forefront of mobile gaming with its latest phone, the Honor 8 Pro. The Pro sets itself apart from its predecessor, the Honor 8, with a host of premium updates that boost the device’s graphical and... | Read more »
The 4 best outdoor adventure apps
Now that we're well into the pleasant, warmer months, it's time to start making the most of the great outdoors. Spring and summer are ideal times for a bit of trekking or exploration. You don't have to go it alone, though. There are plenty of... | Read more »
Things 3 (Productivity)
Things 3 3.0.1 Device: iOS iPhone Category: Productivity Price: $7.99, Version: 3.0.1 (iTunes) Description: Meet the all-new Things! A complete rethinking of the original, award-winning task manager – with a perfect balance between... | Read more »
Oddball mash-up Arkanoid vs Space Invade...
In a move no one was really expecting, Square Enix has put forth an Arkanoid/Space Invaders mash-up aptly titled Arkanoid vs Space Invaders. The game launched today on both iOS and Android and the reviews are actually quite good. [Read more] | Read more »

Price Scanner via MacPrices.net

A Kaby Lake Processor Upgrade For The MacBook...
Now they tell me! Well, actually Apple hasn’t said anything official on the subject, but last week Bloomberg News’s Mark Gurman and Alex Webb cited unnamed “people familiar with the matter”... Read more
Kodak’s Camera-First Smartphone EKTRA Launche...
The Eastman Kodak Company and Bullitt Group have announced the availability of a U.S. GSM version of the KODAK EKTRA Smartphone. The U.S. launch coincides with a software update addressing requests... Read more
Apple Launches App Development Curriculum for...
Apple today launched a new app development curriculum designed for students who want to pursue careers in the fast-growing app economy. The curriculum is available as a free download today from Apple... Read more
Check Apple prices on any device with the iTr...
MacPrices is proud to offer readers a free iOS app (iPhones, iPads, & iPod touch) and Android app (Google Play and Amazon App Store) called iTracx, which allows you to glance at today’s lowest... Read more
9.7-inch 2017 iPad available for $298, save $...
Sams Club has 32GB 9.7″ Apple iPads available for $298 for Sams Club members. That’s $21 off MSRP. Order online and choose free local store pickup (if available) or free shipping. Read more
touchbyte Releases PhotoSync 3.2 for iOS With...
Hamburg, Germany based touchbyte has announced the release of PhotoSync 3.2 for iOS, a major upgrade to the versatile and powerful app to transfer, backup and share photos and videos over the air.... Read more
Emerson Adds Touchscreen Display and Apple Ho...
Emerson has announced the next evolution of its nationally recognized smart thermostat. The new Sensi Touch Wi-Fi Thermostat combines proven smarthome technology with a color touchscreen display and... Read more
SurfPro VPN for Mac Protects Data While Offer...
XwaveSoft has announced announce the release and immediate availability of SurfPro VPN 1.0, their secure VPN client for macOS. SurfPro VPN allows Mac users to protect their internet traffic from... Read more
13-inch Touch Bar MacBook Pros on sale for $1...
B&H Photo has 13″ MacBook Pros in stock today for up to $150 off MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 13″ 2.9GHz/512GB Touch Bar MacBook Pro Space Gray (... Read more
Tuesday deal: $200 off 27-inch Apple iMacs
Amazon has select 27″ iMacs on sale for $200 off MSRP, each including free shipping: - 27″ 3.3GHz iMac 5K: $2099 $200 off MSRP - 27″ 3.2GHz/1TB Fusion iMac 5K: $1799 $200 off MSRP Keep an eye on our... Read more

Jobs Board

*Apple* Mobile Master - Best Buy (United Sta...
**508456BR** **Job Title:** Apple Mobile Master **Location Number:** 000040-Eau Claire-Store **Job Description:** **What does a Best Buy Apple Mobile Master Read more
Director *Apple* ERP Integration Lead - Ast...
…make a real difference. Come, shine with us! Astellas is announcing a Director Apple ERP Integration Lead opportunity in Northbrook, IL. Purpose & Scope: This role Read more
Director *Apple* Platform, IS Data Manageme...
…a real difference. Come, shine with us! Astellas is announcing a Director Apple Platform, IS Data Management Lead opportunity in Northbrook, IL. Purpose & Scope: Read more
Associate Director *Apple* Platform -- SAP...
…real difference. Come, shine with us! Astellas is announcing a Associate Director Apple Platform -- SAP Security, Risks and Controls Lead opportunity in Northbrook, Read more
*Apple* Media Products - Commerce Engineerin...
Apple Media Products - Commerce Engineering Manager Job Number: 57037480 Santa Clara Valley, California, United States Posted: Apr. 18, 2017 Weekly Hours: 40.00 Job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.