June 1999 Programmer's Challenge
Tetraminx
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm ET, Saturday, 5 June 1999
Due Date: 11:59pm ET, Saturday, 5 June 1999
The last Challenge I entered as a contestant was the Rubik’s Cube Challenge, where entries had to solve a scrambled Rubik’s cube. While that Challenge was difficult enough to cause me to retire from competition after winning, I’ve stayed interested in puzzles. Some time ago I ran across Meffert’s World Of Puzzles, an online puzzle vendor, and ordered a few of their puzzles. The Tetraminx is perhaps the least difficult puzzle, much simpler than the Cube, but still interesting enough that I thought it might make a good Challenge without driving any contestants into retirement.
The Tetraminx is formed by four hexagonal faces, each consisting of six triangles, joined in the shape of a tetrahedron, plus four triangles to complete the solid, as depicted here and below.
|
Your Challenge is to come up with a sequence of moves that will return the puzzle to the goal state, where each of the hexagonal faces consist of triangular facelets of a single color.
The prototype for the code you should write is:
#if defined (__cplusplus)
extern "C" {
#endif
typedef enum {
kYellow=1,kBlue,kRed,kGreen
} PieceColor;
typedef enum {
kLeftClockwise=1,kRightClockwise,
kBottomClockwise,kBackClockwise,
kLeftCounterClockwise,kRightCounterClockwise,
kBottomCounterClockwise,kBackCounterClockwise
} Move;
typedef enum {
/* single triangular faces named after the opposite hexagonal face */
kLeft,kRight,kBottom,kBack,
/* edge faces named kXY, where X is the hexagonal face they are part of,
and Y is the adjacent hexagonal face */
kBR,kRK,kKB,
kLB,kBK,kKL,
kKR,kRL,kLK,
kLR,kRB,kBL,
/* corner faces named cXY, where X is the hexagonal face they are part of,
and Y is the hexagonal face opposite the adjacent single triangle */
cRL,cKL,cBL,
cLR,cBR,cKR,
cRB,cLB,cKB,
cLK,cRK,cBK
} PieceType;
typedef struct {
PieceType piece;
PieceColor color;
} PieceState;
long /*numberOfMoves*/ Tetraminx (
PieceState state[28], /* initial state of the 28 pieces */
Move moves[], /* moves you generate */
long maxMoves /* maximum storage in move array */
);
#if defined (__cplusplus)
}
#endif
The puzzle is manipulated with four pairs of 120-degree rotation moves that we will call kLeftXXX, kRightXXX, kBottomXXX, and kBackXXX, corresponding to the four hexagonal faces of the Tetraminx. The moves are named for the hexagonal face that remains fixed during the move.. Opposite each of those hexagonal faces are the single triangular faces whose positions remain fixed for all moves (except for rotation). Each move pair consists of a clockwise move and a counterclockwise move, as viewed from the opposite single facelet, through the Tetraminx, at the face for which the move is named.
The PieceType enum names the 28 triangular facelets. Facelets come in three types, and it is important to understand the naming convention for the facelets. The first type consists of the single triangular faces, and those are named kLeft, etc., for the move that rotates the piece, and for the opposite hexagonal face. The second type is an "edge" facelet, one with a single adjoining triangle, and those are named kXY, where X (L, R, B, or K) is the hexagonal face containing the piece, and Y (also L, R, B, or K) contains the adjacent facelet. Finally, "corner" facelets have three adjacent triangles, two of them on the same hexagonal face, and one a single triangular face. These are named cXY, where X is the hexagon containing the piece, and Y is the single triangular face.
This is probably impossible to understand without a picture, so I’ve included one. A color version of the picture is available here and below. The blue, red, yellow, and green faces are the left, right, bottom, and back faces, respectively. The face comprised of the single center (yellow) triangle is the kBack facelet. Starting with the blue triangle next to the kBack facelet, and moving clockwise around the blue face, are the cLK, kLB, cLR, kLK, cLB, and kLR facelets.
The kBackClockwise move rotates the yellow kBack facelet in a clockwise direction, moving the kLR piece (Blue-Red) to where the kRB piece (Red-Yellow) is, and the kRB piece to where the kBL piece (Yellow-Blue) is.
|
If the nomenclature for facelets and moves seems confusing, the test code available via the Challenge mailing list will make it clearer. Alternatively, for those of you that are into group theory, the four clockwise moves perform the following permutations on the facelets:
kRightClockwise: (kKL, kLB, kBK) (kLK, kBL, kKB) (cLR, cBR, cKR) kLeftClockwise: (kRK, kKB, kBR) (kKR, kBK, kRB) (cRL, cKL, cBL) kBottomClockwise: (kKR, kRL, kLK) (kRK, kLR, kKL) (cRB, cLB, cKB) kBackClockwise: (kLR, kRB, kBL) (kRL, kBR, kLB) (cLK, cRK, cBK)
Your code should place the moves needed to solve the puzzle in moves and return the number of moves generated, or return zero if you cannot solve the puzzle in maxMoves moves.
Instructions for solving the Tetraminx are available here. Since you probably don’t have a Tetraminx handy, test code will be available to help you see the effects of the moves you make to solve the puzzle. The winner will be the solution that solves the puzzle in the fewest number of moves, with a 10% penalty added for each second of execution time.
This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.
Test code for this Challenge is available.
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
