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 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
*
* 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 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-g h,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
*
* Now since abc + def = def + abc = ghj, where a
* 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
* 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 [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 [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
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 short number of Magic Additions
*/
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).
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: 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.
Referenced by (2):