Jul 93 Challenge
Volume Number:   9

Issue Number:   7

Column Tag:   Programmers' Challenge

Programmers’ Challenge
By Mike Scanlin, MacTech Magazine Regular Contributing Author
TILE WINDOWS
This month we have our very first Macintoshspecific 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 1based 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 trapsthey are the reason why most tiling routines are slow; they cause too much intermediatestep screen redrawing while the tiling is going on.
TWO MONTHS AGO WINNER
Wow! I received 40 entries to the “Magic Additions” challengealmost 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 (9z2) 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 (9z2) in the z0
* forloop.
*
* 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 bitarray 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 (g1)/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 ifstatement in NFind handles initializing
* the forloop start & end parameters. The start and
* end parameters are derived from the tables for valid
* a + b = c shown later on.
*
* In the forloops, valid c & f are selected and
* checked to see if the digits they correspond to are
* already being used. If not, then the second forloop
* 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 18gh,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 singledigit 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 (g1)/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 ... (g1)/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...(c1)/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 = (z01)>>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 aj 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 = (z21)>>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” Tshirt (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 email 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, email  AppleLink: MT.PROGCHAL, Internet: progchallenge@xplain.com, 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.