January 1999 Programmer's Challenge
Sphere Packing
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Sunday, 3 January 1999
Due Date: 11:59pm ET, Sunday, 3 January 1999
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)
extern "C" {
#endif
typedef struct Position {
double coordinate[3]; /* coordinate[0]==X position, [1]==Y, [2]==Z */
} Position;
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.
You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".
- SPREAD THE WORD:
- Slashdot
- Digg
- Del.icio.us
- Newsvine
