Jun 00 Challenge
Volume Number: 16
Issue Number: 3
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Rub*k Rotation
Readers sometimes write me to ask whether they can solve the Challenge on a platform
other than a Mac. Now, I'm not sure why a reader of this publication would want to do
that, but in many cases the Challenge is platform agnostic and quite amenable to
solution an another machine. Sometimes I get mail thanking me for creating
non-Mac-specific problems. Then again, I also get mail asking why problems that have
nothing to do with the Mac appear in a Macintosh publication. Paraphrasing Lincoln,
you can't please all of the people all of the time. But it has been a while since we've had
a Macintosh-specific problem, so we're going to offer one this month. The last
Challenge I competed in required readers to solve the puzzle known as Rub*k's Cube, a
3x3 cube of smaller cubies where each cube face was colored with a different color.
Solving that Challenge took me right to the midnight deadline, past many midnights
before that one, and actually pushed me over the edge into Challenge retirement (as a
contestant, anyway). As I write this column, having watched another midnight come
and go, I thought we'd revisit the Cube, but from a completely different perspective.
Your Challenge this month is to write a program that will display the cube, animating
both rotations of the cube and the moves used to solve the cube. The prototype for the
code you should write is:
typedef enum { /* identify the cube face */
kFront=0, kBack, kLeft, kRight, kUp, kDown
typedef enum { /* identify the axes of rotation */
kFrontBack=0, kLeftRight, kUpDown
/* rotation axis kXY is oriented viewing face X, through the cube,
toward face Y */
kClockwise=1, kCounterClockise=-1
void InitCube(
CWindowPtr cubeWindow,
/* window where the rotating cube should be rendered */
const RGBColor cubeColors[6],
/* colors to use in rendering, indexed by CubeFace */
const short cubieColors[3][3][3],
/* cubieColors is the index into cubeColors for individual cubies
*/
/* cubeColors[cubieColors[f][r][c]] is the color of the cubie on
face f, row r, col c*/
/* Row and column orientations are as follows: */
/* cubieColors[kFront][0][0] is adjacent to kUp and kLeft */
/* cubieColors[kFront][0][2] is adjacent to kUp and kRight */
/* cubieColors[kBack][0][0] is adjacent to kUp and kRight */
/* cubieColors[kBack][0][2] is adjacent to kUp and kLeft */
/* cubieColors[kLeft][0][0] is adjacent to kUp and kBack */
/* cubieColors[kLeft][0][2] is adjacent to kUp and kFront */
/* cubieColors[kRight][0][0] is adjacent to kUp and kFront */
/* cubieColors[kRight][0][2] is adjacent to kUp and kBack */
/* cubieColors[kUp][0][0] is adjacent to kBack and kLeft */
/* cubieColors[kUp][0][2] is adjacent to kBack and Right */
/* cubieColors[kDown][0][0] is adjacent to kFront and kLeft */
/* cubieColors[kDown][0][2] is adjacent to kFront and kRight */
short cubeWidth,
/* size in pixels of a cube in the standard orientation (kFront
visible) */
short stepSize
/* granularity to redraw, stepSize steps is one full 360 degree
rotation */
);
void QuarterTurn(
CubeFace face, /* turn this face one quarter turn */
TurnDirection direction /* turn the face in this direction */
/* turn orientation is looking at the face from outside the cube
toward the center
of the cube */
);
void RotateCube(
CubeAxis axis, /* rotate cube about the specified axis */
TurnDirection direction,
/* rotate the cube in this direction about the specified axis */
/* clockwise about the kFrontBack face is determined viewing from
the kFront
face, through the cube to the kBack face */
short stepsToTurn
);
void TermCube(void);
This Challenge will start with a call to your InitCube routine providing a number of
problem parameters. The window in which you should render the cube, a color window
with a pixelSize of 32 bits, will be provided in cubeWindow. The colors making up the
cube faces will be provided in cubeColors, and the individual cubie colors will be
specified by cubieColors as indices into cubeColors. You should center your display of
the cube in the cubeWindow, and size the cube so that it is cubeWidth pixels on a side,
in its initial position, oriented along the u-v axes, and viewed along the cube normal.
InitCube should draw the cube in its initial posiiton, viewing the kFront face along the
kFrontBack axis, with the kUp face at the top of the cube, perpendicular to the view
plane. The cube may be displayed with a perspective projection, from a reasonable
distance, or from an orthographic projection from infinity.
The final parameter provided to InitCube is the stepSize, used by the QuarterTurn and
RotateCube calls in animating cube turns and rotations. The stepSize parameter
specifies how granular the animations and rotations should be, with stepSize rotation
steps constituting one full rotation. The value of stepSize will be a multiple of 4, so
that quarter turns will contain an integral number of steps.
The QuarterTurn routine is called to turn the 9 cubies on one face of the cube by 90
degrees relative to the rest of the cube. When QuarterTurn is called, you should rotate
the specified face in the specified direction, animated in increments determined by
stepSize. Any internal portions of the cube not normally visible, but visible during the
turn, should be displayed in a gray or black color of your choice.
The RotateCube routine is called to rotate the entire cube, respectively. When
RotateCube is called, you should rotate the entire cube about the specified cube axis in
the specified direction. As multiple calls are made to RotateCube, the axes of rotation
will become arbitrarily oriented with respect to the view vector, although the cube
will remain centered in the cubeWindow.
Finally, the TermCube routine will be called at the end of the test, allowing you to
clean up any memory you might have allocated before returning. There may be
multiple test cases, each bracketed with an InitCube and a TermCube call.
The commentary in the code for the CubeAxis describe the orientation used to perform
clockwise and counterclockwise rotations of the cube. Similarly, the commentary for
the CubeFace in the QuarterTurn prototype describes the orientation for performing
face quarter turns. If these explanations are not clear, please send me a note on the
Challenge mailing list for clarification.
Scoring will be based first on the quality of the accuracy of the display, and the
absence of tearing or other display anomalies. Among the accurate entries with
acceptable display quality, the winner will be the solution requiring the least
execution time.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment.
Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted,
but Java entries must be accompanied by a test driver that uses the interface provided
in the problem statement.
Three Months Ago Winner
Congratulations to Ernst Munter (Kanata, ON, Canada) for taking first place in the
March Sum Of Powers Challenge, narrowly beating out the second place entry from
Miklos Fazekas. You might recall that the March Challenge required you to find a set of
terms which, added or subtracted together, formed a given positive integer. The terms
were required to be integers raised to a power greater than 1. Scoring was based on the
number of terms used to form the result and on the amount of execution time used to
calculate the solutions, with a penalty of 1 term per 100 milliseconds of execution