TweetFollow Us on Twitter

Jul 93 Challenge
Volume Number:9
Issue Number:7
Column Tag:Programmers' Challenge

Programmers’ Challenge

By Mike Scanlin, MacTech Magazine Regular Contributing Author


This month we have our very first Macintosh-specific Challenge. It was inspired by getting tired of waiting for lame programs that take forever to tile or stack a set of windows. The goal is to write a faster routine to tile a set of windows. ‘Tile’ here means to size and position a given set of windows within a given rectangle such that none of the windows overlap (like MPW’s TileWindows command). We’ll ignore stacking windows for now (besides, once you make tiling fast, stacking is easy).

The prototype of the function you write is:

void TileWindows(enclosingRectPtr,
 windowPtrArray, windowCount,
 pixelsBetween, minHorzSize,
Rect    *enclosingRectPtr;
WindowPtr windowPtrArray[];
unsigned short   windowCount;
unsigned short   pixelsBetween;
unsigned short   minHorzSize;
unsigned short   minVertSize;

enclosingRectPtr points to the rect that contains all of the given windows after they’ve been tiled. windowCount is the 1-based number of windows to tile and windowPtrArray is the address of the first element of an array of WindowPtrs (containing windowCount elements). In case it makes a difference, windowCount won’t be larger than 100.

pixelsBetween is the number of pixels between tiled windows (the number of desktop pixels shining through between windows after they’ve been tiled). minHorzSize and minVertSize are the minimum dimensions of the tiled windows (guaranteed to be smaller than enclosingRect). After you’ve computed the optimal tiling layout you need to verify that no window is smaller than these dimensions. If it is, you need to enlarge the window and overlap it with part of some other window (but in no case should any part of any window exceed the bounds of enclosingRect). So, the only time when overlapping windows are allowed is if there’s no way to layout the windows such that they meet the minimum size requirements and still don’t overlap. Note: this is a tiny detail that I’m not going to stress test. I’m also not going to specify how windows should be laid out. You pick whatever looks good to you (a function of the number of windows, no doubt). Tiled windows do not need to all be the same size nor do you have to use all of the space given to you by enclosingRect (but each side of enclosingRect should have at least one window touching it).

The key to this challenge is to find a way to size and position windows without using the MoveWindow or SizeWindow traps-they are the reason why most tiling routines are slow; they cause too much intermediate-step screen redrawing while the tiling is going on.


Wow! I received 40 entries to the “Magic Additions” challenge-almost twice as many as any previous challenge. There were some extremely clever entries this time and I’d like to thank everyone for sweating the details on the algorithms they used. Unfortunately, we can only have one winner. And that winner is Johnny Lee (location unknown) who had some help from Paul Fieguth (location unknown). Paul’s proof and Johnny’s code are well worth studying. They are an excellent example of how you can improve your performance by really understanding the problem. Only one entry was faster than theirs but the solution from Gerry Davis (St. Charles, MO) uses 580 bytes of static data which violates the spirit of this particular contest which was to not use too much precomputed data (Johnny’s doesn’t use any static data).

Here are the sizes and times for the 35 entries that yielded the correct answer of 168 (the times are for 1000 calls). To protect the guilty, those people whose times were more than 1000 times slower than the winner have only their initials given:

Name bytes ticks

Johnny Lee 464 38

Gerry Davis 944 32

Russ Rufer 648 49

Brian Lowry 450 55

Adam Grossman 956 61

David Sumner 338 87

Robert Coie 378 101

David Rees 706 110

Bruce Smith 402 172

Mason Lancaster 962 226

Dave Darrah 296 242

Nigel D’Souza 678 400

Scott Howlett 462 510

Kevin Cutts 338 610

Alan Stenger 176 800

Scott Manjourides 420 950

Aaron Jaggard 1220 1010

Robert Thurman 390 1610

Henry Carstens 672 2680

Massimo Senna 1100 3010

Yorick Phoenix 424 3640

Gene Arindaeng 588 3770

Donald Knipp 562 6000

Peter Hance 546 16090

Brian Ballard 482 18570

Clay Davis 642 28000

KK 1122 52000

KH 274 59000

DK 1426 65000

PS 540 76000

GD 630 76000

JB 448 204000

BA 784 582000

ST 408 822000

RK 562 849000

Here’s Johnny’s winning solution:

 * MagicAdd.c
 * Purpose:
 * This file contains the function CountMagicAdditions()
 * which solves the May Programmer's Challenge from
 * MacTech Magazine.
 * In the functions, rather than using abc + def = ghj,
 * the variables are repsented by the following notation:
 *        x  x  x
 *         2  1  0
 *     +  y  y  y
 *         2  1  0
 *       -----------  , i.e. x2 = a, x1 = b, y2 = d, etc.
 *        z  z  z
 *         2  1  0
 * CountmMagicAdditions() and its supporting function
 * NFind() calculates the number of equations which satisfy
 * the problem abc + def = ghj, where a...j represent a
 * digit from 1...9 and each digit appears only once in
 * the equation.
 * The main optimization is a property of the problem 
 * which is, g+h+j = 18. My friend, Paul Fieguth,  
 * developed a proof for this which is given later on.
 * Several other properties are used in order to reduce 
 * the run time such as:
 * Only one carry is ever generated - another property
 * from Paul Fieguth's proof.
 * Basic limits:
 * 3 <= a+b <= 17 where 1 <= a,b <= 9 and no digit is
 * used twice
 * If no carry is generated in the addition then
 * 3 <= a+b <= 9 where 1 <= a,b < 9 and no digit is used
 * twice
 * If a carry is generated in the addition then
 * 11 <= a+b <= 17 where 1 < a,b <= 9 and no digit is
 * used twice
 * Never divide by 2 when you can shift left by 1.
 * The function starts by determining valid 'ghj'.
 * Since g+h+j = 18, it can easily reduce the possible # 
 * of valid sums by only generating g,h,j such that their 
 * sum equals 18.
 * It starts by iterating through valid values of g which
 * are from 4 to 9. 3 is excluded since the possible 
 * values of ghj where g=3 are invalid [See proof later
 * on].
 * After selecting a g, h & j are selected. The
 * expression (9-z2) is used to start the selection of
 * the values of h & j since the max value of either h or
 * j is 9. Say h == 9, that means g + j = 18 - (h=9) = 9.
 * So j = 9 - g, which translates into (9-z2) in the z0
 * for-loop.
 * A check is made to ensure that no digit appears more 
 * than once in ghj and that g,h,j are within the range
 * 1...9.
 * The fBitUsed bit-array is updated to reflect
 * those digits that are being used.
 * Next, the function selects valid a & d values.
 * This is simplified once we have a valid ghj since
 * the values of a & d are restricted by the currently-
 * selected g. It iterates from the (g-1)/2 to 1 for
 * values of a. This helps generate a,d,g such that
 * a<d<g. This method is used frequently.
 * A check is made to ensure that a isn't being used
 * in ghj. The function then calculates what d should
 * be in order to satisfy a + d = g.
 * If d isn't being used in ghj, and j < 8
 * (a property of the fact that the tens column didn't 
 * generate a carry, so the ones column must generate
 * a carry. If the ones column does generate a carry. then
 * the valid values for j are limited) a call is made
 * to NFind to determine if the currently selected
 * digits form the basis of an equation which satisfies
 * the problem. If it does, then the # of valid solutions
 * is incremented.
 * d is then decremented to investigate the case where
 * a + d + 1 = g, i.e. a carry is generated from the
 * tens column, (b+e = h, h>10). There are checks
 * made to ensure that the new d isn't being used in ghj
 * and that a<d and j > 2 (once again this is a property
 * of the fact that the tens column did generate a carry
 * so the ones column didn't generate a carry and the
 * values of j are therefore restricted once again).
 * If the checks succeed, a call to NFind is made to
 * see if the current values of a, d, ghj form the
 * basis of an equation which satisfies the problem.
 * For NFind, there are two major cases to handle.
 * One where the tens column generates a carry and one
 * where the tens column doesn't generate a carry (which
 * means that the ones column DOES generate a carry - 
 * the hundreds column can't generate a carry).
 * The first if-statement in NFind handles initializing
 * the for-loop start & end parameters. The start and
 * end parameters are derived from the tables for valid
 * a + b = c shown later on.
 * In the for-loops, valid c & f are selected and
 * checked to see if the digits they correspond to are
 * already being used. If not, then the second for-loop
 * is entered to determine valid b & e. Once again
 * checks to ensure that the digits corresponding to b & e
 * aren't being used are made. If they aren't then we have
 * a solution!
 * Owner:
 * Johnny Lee

 * Proofs & Tables
 * [Paul Fieguth's proof]
 * The problem is:
 * Find all of the correct addition problems of the form:
 * 123 + 456 = 789 using each of 1 through 9 once each in
 * every solution.
 * Now, in performing the addition, if a carry is never
 * generated ...
 *      a+b+c+d+e+f = g+h+j
 * If one carry is generated, then a value of 10 is
 * turned into a 1 in the next higher column, e.g.,
 *      a+b+c+d+e+f = g+h+j + 9    (9 = 10 - 1)
 * In general, we can say
 *      a+b+c+d+e+f = g+h+j + n*9  n = 0,1,2,3,...
 * Now, the sum of digits from one to 9 is
 *  1 + ... + 9 = 45
 *      Let    x = g+h+j     x integer
 *      i.e.,  x + (x + n*9) = 45
 *      Consider each value of  n  separately:
 *        n=0   x = 45 - x      ->  x = 45/2 not integer
 *        n=1   x = 45 - 9 - x  ->  x = 36/2 = 18
 *        n=2   x = 45 -18 - x  ->  x = 27/2 not integer
 *        n=3   x = 45 -27 - x  ->  x = 18/2 = 9
 * But n=3 is not possible, since we are adding 3 sets of
 * digits, and the last (hundreds colunm) cannot generate
 * a carry.  ie, n <= 2
 * But by the previous argument, if n<=2, then n=1, and
 * thus x=18.
 * Therefore  g+h+j = 18 (1) for all satisfying solutions.
 * Also, only one carry is ever generated.
 * [Valid values for g]
 * If we look at the values that g can take:
 * g  18-gh,j
 * 9  9 [1,8],[2,7],[3,6],[4,5],[5,4],[6,3],
 * [7,2],[8,1]
 * 8  10[1,9],[3,7],[4,6],[6,4],[7,3],[9,1]
 * 7  11[2,9],[3,8],[5,6],[6,5],[8,3],[9,2]
 * 6  12[3,9],[4,8],[5,7],[7,5],[8,4],[9,3]
 * 5  13[4,9],[6,7],[7,6],[9,4]
 * 4  14[5,9],[6,8],[8,6],[9,5]
 * g can't take take a value less than 3 because the
 * minimum sum of two single-digit integers is 3, i.e
 * 1+2 - remember we're considering the hundreds column
 * so g can't be greater than 9.
 * Now 3 is also invalid because the set of numbers which
 * satisfy (1) for [h,g] are [6,9], [7,8], [8,7], [9,6].
 * Now the proof above states that there will be one
 * carry generated for the given equation.
 * Now consider each set of [h,j] for g = 3:
 * h=6, j=9:
 * if j=9, it can't generate the carry since the 
 * max result of adding two single digit number is
 * 17 (=8+9) (2).
 * So h=6 must generate the carry. But the only two sums
 * that could generate a 16, (7+9, 8+8) are invalid since
 * the former contains a digit which is being used in j
 * and the latter contains the same two digits.
 * h=7, j=8:
 * if j=8, it can't generate the carry due to (2),
 * Therefore, h=7 must generate the carry. But the only
 * addition which can generate 17 is 8+9 and 8 is being
 * used already in j.
 * h=8, j=7:
 * if j=7, it can't generate the carry since the two
 * numbers needed to generate 17 are 8,9, but 8 is being
 * used in h. Therefore h=8 must generate the carry, but
 * it can't according to (2).
 * h=9, j=6:
 * if j=6, it can't generate the carry since the only
 * valid addition for this problem which can generate
 * 16 uses 7 & 9, but h has the value 9. Therefore h=9 must    *
 generate the carry, but it can't according to (2).
 * [How to ensure a<d<g for a + d = g]
 * Now since abc + def = def + abc = ghj, where a<d<g, the
 * problem specifies that only one of abc+def & def+abc
 * can be counted as a solution. Therefore, when determining   *
 a & d, a only needs to iterate from 1 to (g-1)/2 because      *
 if a >= g/2 then d <= a otherwise we'd have an overflow       
 * of the hundreds column and the problem doesn't allow  *      
 * that.We check for solutions with a = 1 ... (g-1)/2, and
 * all solutions for a<g/2 will have been counted already,
 * so if d is less than a, the solution will be counted twice.
 * [Valid a,b,c for a + b = c]
 * If a carry is generated by a + b = c, then for 
 * valid c (10<c<18):
 * c  [a,b] pairs
 * 11 [2,9], [3,8], [4,7], [5,6]
 * 12 [3,9], [4,8], [5,7]
 * 13 [4,9], [5,8], [6,7]
 * 14 [5,9], [6,8]
 * 15 [6,9], [7,8]
 * 16 [7,9]
 * 17 [8,9]
 * Therefore:
 * a = (c mod 10)+1...((c mod 10)+9)/2
 * b = c - a
 * If no carry is generated by a + b = c, then for
 * valid c (2<c<10):
 * c  [a,b] pairs
 * 3  [1,2]
 * 4  [1,3]
 * 5  [1,4], [2,3]
 * 6  [1,5], [2,4]
 * 7  [1,6], [2,5], [3,4]
 * 8  [1,7], [2,6], [3,5]
 * 9  [1,8], [2,7], [3,6], [4,5]
 * a = 1...(c-1)/2
 * b = c - a

/* Raise 2 to the power of x */
#define PowerTwo(x) (1<<(x))

/* Determine if digit/bit Y in the word X is set */
#define FIsDigitUsed(x,y) ((x) & PowerTwo(y))

/* NFind
 * Purpose:
 * Finds out if there are any equations which fit the
 * equation, abc + def = ghj given the parameters
 * passed in.
 * Arguments:
 * fDigitsUsed   buffer where every bit that's set 
 * represents a digit that's been used.
 * z0   the one digit of the sum
 * z1   the tens digit of the sum
 * fCarryFromTensColumn if the tens column
 * generates a carry.
 * Returns:
 * Number of equations which satisfy the problem.
 * Can be either 4 or 0.
NFind(short fDigitsUsed, short z0, short z1,
 short fCarryFromTensColumn)
 register short x0;
 register short x1;
 register short y0;
 register short fDigitsUsedT;
 short y1;
 short nStop;
 short nStartX1;
 short nStopX1 = 10;
 if ( fCarryFromTensColumn ) {
 x0 = (z0-1)>>1;
 nStartX1 = z1+1;
 z1 += 10;
 nStop = 0;
 else {
 x0 = (z0+9)>>1;
 nStop = z0;
 z0 += 10;
 nStartX1 = 1;

 for (; x0>nStop; --x0) {
 if (FIsDigitUsed(fDigitsUsed,x0))
 y0 = z0 - x0;
 if (FIsDigitUsed(fDigitsUsed, y0))
 fDigitsUsedT = fDigitsUsed | PowerTwo(x0) | PowerTwo(y0);
 for (x1 = nStartX1; x1<nStopX1; ++x1) {
 if (FIsDigitUsed(fDigitsUsedT,x1))
 y1 = z1 - x1;

if (FIsDigitUsed(fDigitsUsedT,y1))
 if (y1 == x1)
 return 4;
 return 0;

/* CountMagicAdditions
 * Purpose:
 * Calculates the number of equations which satisfy
 * the problem abc + def = ghj where a-j represent
 * a digit 1...9 and each digit appears only once
 * in the equation.
 * Returns:
 * Unsigned shortnumber of Magic Additions
unsigned short
 short z0;
 short z1;
 short z2;
 short y2;
 short x2;
 short fDigitsUsed;
 short w;
 short cSolutions = 0;

 for (z2 = 9, w = 18 - z2; z2 > 3; --z2, ++w) {
 for (z0 = (z2<9) ? 9 - z2 : 1; z0<10; ++z0) {
 z1 = w - z0;
 if ((z2 == z0) || (z2 == z1) ||
   (z0 == z1) || (z1<1))
 fDigitsUsed = PowerTwo(z2) | PowerTwo(z1) |
 for (x2 = (z2-1)>>1; x2 > 0; --x2) {
 if (FIsDigitUsed(fDigitsUsed,x2))
 y2 = z2 - x2;
 if (!FIsDigitUsed(fDigitsUsed,y2) &&
   (z0<8)) {
 cSolutions += NFind(fDigitsUsed |
   PowerTwo(x2) | PowerTwo(y2), z0,
   z1, 0);
 if (!FIsDigitUsed(fDigitsUsed,y2) &&
   (y2 > x2) && (z0 > 2)) {
 cSolutions += NFind(fDigitsUsed |
   PowerTwo(x2) | PowerTwo(y2), z0,
   z1, 1);
 return cSolutions;

The Rules

Here’s how it works: Each month there will be a different programming challenge presented here. First, you must write some code that solves the challenge. Second, you must optimize your code (a lot). Then, submit your solution to MacTech Magazine (formerly MacTutor). A winner will be chosen 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 to be found 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). Only pure C code can be used. Any entries with any assembly in them will be disqualified. However, you may call any routine in the Macintosh toolbox you want (i.e., it doesn’t matter if you use NewPtr instead of malloc). All entries will be tested with the FPU and 68020 flags turned off in THINK C. When timing routines, the latest version of THINK C will be used (with ANSI Settings plus “Honor ‘register’ first” and “Use Global Optimizer” turned on) so beware if you optimize for a different C compiler. All code should be limited to 60 characters wide. This will aid us in dealing with e-mail gateways and page layout.

The solution and winners for this month’s Programmers’ Challenge will be published 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.

All solutions should be marked “Attn: Programmers’ Challenge Solution” and sent to Xplain Corporation (the publishers of MacTech Magazine) via “snail mail” or preferably, e-mail - AppleLink: MT.PROGCHAL, Internet:, CompuServe: 71552,174 and America Online: MT PRGCHAL. If you send via snail mail, please include a disk with the solution and all related files (including contact information). See page 2 for information on “How to Contact Xplain Corporation.”

MacTech Magazine reserves the right to publish any solution entered in the Programming Challenge of the Month and all entries are the property of MacTech Magazine upon submission. The submission falls under all the same conventions of an article submission.


Community Search:
MacTech Search:

Software Updates via MacUpdate

How to get all the crabs in Mr Crab 2
Mr. Crab 2 may look like a cutesy platformer for kids, but if you're the kind of person who likes to complete a game 100%, you'll soon realise that it's a tougher than a crustacean's shell. [Read more] | Read more »
How to be a star in Britney Spears: Amer...
If you've ever wanted to be a star, baby, then you've probably already checked out Britney Spears: American Dream and are happily making your way up the charts. But fame doesn't come easy, and everyone needs a helping hand sometimes. So we've got... | Read more »
AppSpy is hiring a part time Staff Write...
| Read more »
How to save lives in ER Surgery Simulato...
A serious earthquake has struck a nearby town in ER Surgery Simulator - Emergency Doctor, and it’s up to you to save the victims. [Read more] | Read more »
Tips and tricks to get a high score in G...
Ketchapp Games loves the endless runner genre. And its newest game, Gravity Switch, is no exception. Gravity Switch takes a fresh approach, though, as you move a block, suspended in zero gravity, safely through a maze of shifting pillars. If the... | Read more »
Tips and tricks to get a high score in S...
Smash Fu is a high-paced tile-tapping game that requires quick reflexes and some practice. You’ll have to smash bricks with the skill of a seasoned black belt to get a high score. To raise the stakes a bit, you’ll also have to avoid tapping any... | Read more »
How to keep the ball rolling in Dropple
If you're new to the minimalist puzzler Dropple, you may find yourself struggling to make it beyond the first couple of steps before your ball falls into the endless abyss below. [Read more] | Read more »
Game Craft releases new Legend of War ti...
Set for release at the end of this month, real time strategy title Legend of War seems sure to delight with a veritable feast of sweet features to get stuck into. Developed by Game Craft, the game is due for release through both the App Store and... | Read more »
How not to die in Traffic Rider
Traffic Rider, an Out Run-esque game in which your ride a motorcycle recklessly into trffic, might not seem particularly complicated. [Read more] | Read more »
How to adjust your chess game for Regici...
At first glance you might likenWarhammer 40,000: Regicide to Chess - and you'd be right. Regicideputs its own spin on the classic board game though, so some of your tried and true methods may not work quite so well here. [Read more] | Read more »

Price Scanner via

Textkraft Professional Becomes A Mobile Produ...
The new update 4.1 of Textkraft Professional for the iPad comes with many new and updated features that will be particularly of interest to self-publishers of e-books. Highlights include import and... Read more
SnipNotes 2.0 – Intelligent note-taking for i...
Indie software developer Felix Lisczyk has announced the release and immediate availability of SnipNotes 2.0, the next major version of his productivity app for iOS devices and Apple Watch.... Read more
Pitch Clock – The Entrepreneur’s Wingman Laun...
Grand Rapids, Michigan based Skunk Tank has announced the release and immediate availability of Pitch Clock – The Entrepreneur’s Wingman 1.1, the company’s new business app available exclusively on... Read more
13-inch 2.9GHz Retina MacBook Pro on sale for...
B&H Photo has the 13″ 2.9GHz Retina MacBook Pro (model #MF841LL/A) on sale for $1599 including free shipping plus NY tax only. Their price is $200 off MSRP. Amazon also has the 13″ 3.9GHz Retina... Read more
Apple price trackers, updated continuously
Scan our Apple Price Trackers for the latest information on sales, bundles, and availability on systems from Apple’s authorized internet/catalog resellers. We update the trackers continuously: - 15″... Read more
Clearance 12-inch Retina MacBooks available s...
B&H Photo has dropped prices on leftover 2015 12″ Retina MacBooks with models now available starting at $999. Shipping is free, and B&H charges NY tax only: - 12″ 1.1GHz Gray Retina MacBook... 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
New 2016 13-inch 256GB MacBook Air on sale fo...
B&H Photo has the new 13″ 1.6GHz/256GB MacBook Air (model MMGG2LL/A) on sale for $1149 including free shipping plus NY sales tax only. Their price is $50 off MSRP. Amazon has the 13″ 1.6GHz/256GB... Read more
Apple refurbished iPad Air 2s available start...
Apple has Certified Refurbished iPad Air 2 available starting at $339. Apple’s one-year warranty is included with each model, and shipping is free: - 128GB Wi-Fi iPad Air 2: $499 - 64GB Wi-Fi iPad... Read more
Accenture and Vatican Opera Romana Pellegrina...
Accenture has announced that the official mobile application for the Extraordinary Jubilee Year of Mercy declared by Pope Francis has been built and launched by Accenture Mobility, part of Accenture... Read more

Jobs Board

*Apple* Nissan Service Technicians - Apple A...
Apple Automotive is one of the fastest growing dealer...and it shows. Consider making the switch to the Apple Automotive Group today! At Apple Automotive , Read more
ISCS *Apple* ID Site Support Engineer - APP...
…position, we are looking for an individual who has experience supporting customers with Apple ID issues and enjoys this area of support. This person should be Read more
Automotive Sales Consultant - Apple Ford Linc...
…you. The best candidates are smart, technologically savvy and are customer focused. Apple Ford Lincoln Apple Valley is different, because: $30,000 annual salary Read more
*Apple* Support Technician II - Worldventure...
…global, fast growing member based travel company, is currently sourcing for an Apple Support Technician II to be based in our Plano headquarters. WorldVentures is Read more
Restaurant Manager (Neighborhood Captain) - A...
…in every aspect of daily operation. WHY YOU'LL LIKE IT: You'll be the Big Apple . You'll solve problems. You'll get to show your ability to handle the stress and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.