Programmers’ Challenge

By Mike Scanlin, MacTech Magazine Regular Contributing Author

TILE WINDOWS

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,
 minVertSize)
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.

TWO MONTHS AGO WINNER

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.
 */
short
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;
 --z1;
 nStop = z0;
 z0 += 10;
 nStartX1 = 1;
 }

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


if (FIsDigitUsed(fDigitsUsedT,y1))
 continue;
 if (y1 == x1)
 continue;
 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
CountMagicAdditions()
{
 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))
 continue;
 fDigitsUsed = PowerTwo(z2) | PowerTwo(z1) |
   PowerTwo(z0);
 
 for (x2 = (z2-1)>>1; x2 > 0; --x2) {
 if (FIsDigitUsed(fDigitsUsed,x2))
 continue;
 y2 = z2 - x2;
 if (!FIsDigitUsed(fDigitsUsed,y2) &&
   (z0<8)) {
 cSolutions += NFind(fDigitsUsed |
   PowerTwo(x2) | PowerTwo(y2), z0,
   z1, 0);
 }
 --y2;
 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).