August 1998 Programmer's Challenge
BlockBuster
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Saturday, 1 August 1998
One of the Vice Presidents at the Real Job (we'll call him Don)
has a collection of unusual puzzles at his conference table. The kind
that require you to move a large block through a small hole, untangle
a set of intertwined metal loops, do the impossible with rope, or
otherwise do something that requires mastery of the fourth spatial
dimension or a greater aptitude toward right-brain thinking than I
possess. Don retired this week, and, in his honor, this month's
Challenge is devoted to a spatial reasoning exercise. Not a puzzle
that would have been worthy of his conference table, perhaps, but
something in that same spirit.
Our puzzle is a variation of the Soma Cube, reportedly conceived
by a writer from Denmark named Peter Hein as he was listening to a
lecture on quantum physics. (That's one class I don't remember being
able to daydream through!) The object of the Soma Cube is to form a
3x3 cube using seven shapes formed from three or four of the smaller
cubes:
Of course, the Soma can be assembled into other shapes besides a
cube, which forms the basis for our Challenge. Your job will be to
write code that will assemble a larger number of potentially larger
shapes into an even larger designated shape.
The prototype for the code you should write is:
#if defined(__cplusplus)
extern "C" {
#endif
#define kUnknown 0xFFFF
typedef struct Cubie {
SInt16 xCoord; /* x coordinate of cubie */
SInt16 yCoord; /* y coordinate of cubie */
SInt16 zCoord; /* z coordinate of cubie */
UInt16 value; /* ordinal value assigned to the Piece this cubie is
part of */
} Cubie;
typedef struct Piece {
UInt32 numCubies; /* number of individual cubies in this piece */
Cubie *theCubies; /* array of cubies in this piece */
/* NOTE: the declaration of theCubies is modified slightly from the
published version */
} Piece;
Boolean BlockBuster(
/* return TRUE if you were able to solve the puzzle */
long numPieces, /* number of pieces to assemble */
Piece thePieces[], /* the pieces to assemble */
Piece theGoal /* the structure you should assemble */
/* set theGoal.theCubies[i].value to
thePieces[k].theCubies[j].value
if cubie j of piece k occupies cubie i in the reassembled puzzle
*/
);
#if defined(__cplusplus)
extern "C" {
#endif
The building block for our puzzle is the Piece, which is formed
from numCubies individual cubes, provided to you in an array pointed
to by theCubies. Each Piece has a unique nonzero identifier, which is
associated with the value field in the Cubie structure. Cubies also
have x, y, and z coordinates that define their relative orientation
toward one another. There are no restrictions on the size or shape of
a Piece, except that the constituent Cubies will all be connected
(i.e., adjacent to another Cubie in the same Piece in x, y, or z.
Your BlockBuster routine is given an array (thePieces) of
numPieces Pieces to work with. It is also provided with theGoal, an
assembly of Cubies that you are to create from thePieces. For
convenience, theGoal is also described using the Piece data
structure. On input, the occupied coordinates are assigned a value of
kUnknown. On output you should replace that value with the value of
the Piece that occupies that coordinate. You may rotate and translate
thePieces as you desire, but you may not break them by changing the
relative orientation of the Cubies. You must use each Piece exactly
once in assembling theGoal shape. All puzzles will be solvable, but
if you feel you cannot solve a puzzle, BlockBuster should return
FALSE.
As an example, the Pieces in the standard Soma Cube might be
described as follows (with each 4-tuple representing the x, y, z, and
value components of a cubie:
{0,0,1, 5}, {1,0,1, 5}, {0,1,1, 5}, {0,0,0, 5},
{0,0,0, 1}, {1,0,0, 1}, {0,1,0, 1},
{0,0,0, 3}, {1,0,0, 3}, {2,0,0, 3}, {0,1,0, 3},
{0,0,0, 7}, {1,1,1, 7}, {0,1,0, 7}, {0,1,1, 7},
{0,0,0, 6}, {1,0,0, 6}, {0,1,0, 6}, {0,1,1, 6},
{0,0,0, 4}, {1,0,0, 4}, {2,1,0, 4}, {1,1,0, 4},
{0,0,0, 2}, {1,0,0, 2}, {2,0,0, 2}, {1,1,0, 2},
The winner will be the solution that assembles a number of theGoal
shapes in the minimum amount of time. There are no storage
constraints for this Challenge, except that it must execute on my
192MB 8500/200.
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".
|