Jan 99 Prog Challenge
Volume Number: 15
Issue Number: 1
Column Tag: Programmer's Challenge
January 1999 Programmer's Challenge
by Bob Boonstra, Westford, MA
Sphere Packing
This month we're going to help you recover from the clutter that might result from the
holiday season. Imagine that your post-holiday household is filled with gifts, all of
which have to be put somewhere. Imagine further that those gifts include sports
equipment given to your children, or parents, or siblings, or grandchildren, as the
case may be. And finally, imagine that the sports equipment includes a collection of
balls of various sizes - basketballs, baseballs, soccer balls, beach balls, etc. (OK, if
I've stretched your imagination to the breaking point, think of some other reason you
might have a large collection of spherical objects.) We've got to find somewhere to
store all of those balls, and space is at a premium. Fortunately, we also have a very
large collection of boxes of various sizes, so many, in fact, that you can count on
finding a box of the exact size that you might need. In keeping with our desire for a few
less difficult problems, your Challenge is to pack the balls into the smallest box
possible, so that we can store them efficiently.
The prototype for the code you should write is:
#if defined(__cplusplus)
#if defined (__cplusplus)
typedef struct Position {
double coordinate[3]; /* coordinate[0]==X position, [1]==Y,
[2]==Z */
void PackSpheres(
long numSpheres, /* input: number of spheres to pack */
double radius[], /* input: radius of each of numSpheres
spheres */
Position location[] /* output: location of center of each
sphere */
);
#if defined (__cplusplus)
}
#endif
Your PackSpheres routine will be given the number of balls (numSpheres) to be
packed away, along with the radius of each of those spheres. The task is simple.
Arrange the collection of balls into a rectangular parallelepiped ("box") such that no
ball intersects any other ball (i.e., the distance between the centers of any two balls is
greater than or equal to the sum of their radii). PackSpheres returns back the
coordinates of the center of each ball in the location parameter. Your objective is to
minimize the volume of the box that contains all the balls, where the extent of the box
in each dimension (X, Y, and Z) is determined by the maximum and minimum
coordinates of the balls, considering both the location of the center of the ball and its
radius.
While you must ensure that the balls do not intersect, you need not ensure that the
balls touch. In our storage room, boxes of balls can contain balls that levitate in the
open space between other balls.
The winner will be the solution that minimizes the volume of the box containing all the
balls, plus a penalty of 1% of additional storage volume for each millisecond of
execution time.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment.
Solutions may be coded in C, C++, or Pascal.
Three Months Ago Winner
Congratulations to Pat Brown (Staunton, VA) for submitting the winning solution to
the October Hearts Challenge. Pat's solution beat the second-place entry submitted by
Tom Saxton and "dummy" entries that rounded out a tournament of four players. Pat's
solution was both the faster of the two and the more successful at avoiding point cards,
capturing approximately one third fewer points than Tom's solution.
Pat's strategy was fairly simple. His passing strategy is to pass the three highest cards
in his hand. By not including a low heart in the pass, this strategy can aid a shoot
attempt by an opponent, as well as being dangerous if it passes the queen of spades to
the left. When leading, the playing strategy is to force out the queen of spades as
quickly as possible, unless of course he has the queen. While he does not attempt to
"shoot the moon", he is watchful for attempts by other players to shoot, and holds on to
high cards until any potential shoot is spoiled. Otherwise, Pat tries to play the highest
legal card that is lower than the current trick leader.
Tom submitted two solutions, a simple one (used in the tournament at Tom's request),
and a more sophisticated (but less successful) one. The simple solution also tries to
avoid taking tricks and does not attempt to shoot. It is a little more clever in selecting
the pass, in that it tries to create a void if possible. It does not keep track of who might
be attempting to shoot, and therefore does not attempt to stop them. Tom's second
player keeps track of who is void in what suits and tries to shoot when it has a strong
hand. However, it isn't quite perfected, and does much worse in a tournament than the
first player.
I've included a Point Comparison chart that helps explain the performance of the two
players. The vertical bars indicate the number of hands in which each player captured
the number of points shown along the horizontal axis. You can see that Pat's solution
was slightly more successful at capturing fewer than 4 points in a hand, very
successful at avoiding being stuck with the queen of spaces, and extremely effective at
capturing fewer than 20 points in a hand. The line graphs show the cumulative effect
of the respective strategies on the score.
The table below summarizes the scoring for Pat and Tom's Hearts entries. The teams
played a total of 24 matches, consisting of over 25000 hands of 13 tricks each. The
Total Points column in the table lists the number of hearts captured during all of those
tricks, plus 13 points for each Queen of Spades, and -26 points for each shoot. The
table shows the number of tricks "won" by each player, and the number of times each
successfully "shot the moon". You can see that Pat's winning solution did not attempt to
shoot, and was very successful at avoiding being stuck with all of the point cards.
Although not shown in the table, the less-than-intelligent "dummy" players "shot the
moon" more often than either Pat or Tom. This was a consequence of their simplistic
"strategy" for not taking points, which led them to hold on to high cards longer than a
more sophisticated player would have done. Also shown in the table are the execution
time of each solution in milliseconds, the total score, including the penalty of one point
per millisecond of execution time, and the code and data sizes. As usual, the number in
parentheses after the entrant's name is the total number of Challenge points earned in
all Challenges prior to this one.
Name Total Points Tricks Won Shoots Time (msec) Score Code Size Data Size
Pat Brown 94775 59703 1 833 95608 3152 398
Tom Saxton (49) 157105 80902 67 1230 158335 2548
72
Top Contestants
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 20 or more points during the past two years. The
numbers below include points awarded over the 24 most recent contests, including
points earned by this month's entrants.
1. Munter, Ernst 204
2. Saxton, Tom 59
3. Boring, Randy 56
4. Mallett, Jeff 50
5. Rieken, Willeke 47
6. Cooper, Greg 44
7. Maurer, Sebastian 40
8. Heithcock, JG 37
9. Murphy, ACC 34
10. Nicolle, Ludovic 34
11. Lewis, Peter 31
12. Hart, Alan 21
13. Antoniewicz, Andy 20
14. Brown, Pat 20
15. Day, Mark 20
16. Higgins, Charles 20
17. Hostetter, Mat 20
18. Studer, Thomas 20
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2)
being the first person to find a bug in a published winning solution or, (3) being the
first person to suggest a Challenge that I use. The points you can win are:
1st place ›20 points
2nd place ›10 points
3rd place ›7 points
4th place ›4 points
5th place ›2 points
finding bug ›2 points
suggesting Challenge ›2 points
Here is Pat's winning Hearts solution:
MyHearts.c
Copyright © 1998 Pat Brown
/* ***************************************************
* Hearts.c
*
* Author: Pat Brown
*
* Trivia: there are 5.36447377655x10^28 different ways that a
* deck can be dealed out for a game of Hearts.
*/
#define gMAX 52
#define gMIN 1
// Just the relative rankings, 1..52.
// Can be referenced easily using spot and suit value.
/*
2C,2D,2S,3C,3D,3S,4C,4D,4S,5C,5D,5S,6C,6D,6S,2H,3H,4H,
5H,6H,7C,7D,7S,8C,8D,8S,9C,9D,9S,7H,8H,9H,10C,10D,10S,
JC,JD,JS,QC,QD,KC,KD,AC,AD,10H,JH,QH,KS,AS,KH,AH,QS
*/
static const int gCardValue[5][14] =
{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // NoSuit
{0, 3, 6, 9,12,15,22,25,28,35,38,52,48,49}, // Spade
{0,16,17,18,19,29,30,31,32,45,46,47,50,51}, // Heart
{0, 2, 5, 8,11,14,21,24,27,34,37,40,42,44}, // Diamond
{0, 1, 4, 7,10,13,20,23,26,33,36,39,41,43} // Club
};
inline int getCardValue(theSuit, theSpot)
{ return gCardValue[theSuit][theSpot]; }
inline UInt16 NEXTSEAT(UInt16 theSeat)
{ return (theSeat+1)%4; }
/************
Prototypes
*************/