Jan 01 Challenge
Volume Number: 17
Issue Number: 1
Column Tag: Programmer's Challenge
By Bob Boonstra, Westford, MA
Tetris
When George Warner first suggested that I base a Challenge on Tetris, I was skeptical.
I hadn't played Tetris in a long time, and my recollection was that Tetris is a game not
only of strategy, but of manual dexterity as well. After some email conversation,
however, I think we've found a way to formulate Tetris info a meaningful Challenge.
You remember how Tetris is played, right? The game is played on a board sized
perhaps 10 cells wide and 20 cells high into which pieces of varying sizes are
dropped. The player is able to move the pieces left or right as they drop, or to rotate
them clockwise or counter-clockwise, or to drop them to the bottom of the board. The
player accumulates points as each piece is positioned into its final location. As one or
more rows become completely filled, those rows are removed, the other rows are
shifted down, and more points are accumulated. As rows are deleted, the game
progresses to higher and higher levels where the pieces drop faster and faster. The
game continues until there is no room for the next piece to drop into the board.
In this month's Challenge version of Tetris, the board size is generalized to something
potentially larger than 10x20, the game speed remains constant, and the game
continues until a specified time limit expires. You can make one move of the current
game piece, a translation or a rotation, for each tick of the game clock. You can take as
long as you like to figure out the best move, but every microsecond you use to calculate
your move subtracts from the time limit and reduces your opportunity to score
additional points. So you need to plan your moves both carefully and quickly.
The prototype for the code you should write is:
typedef char Piece[7][7];
/* aPiece[row][col] is 1 if aPiece occupies cell (row,col), 0
otherwise */
typedef char Board[256][256];
/* aBoard[row][col] is -1 if cell (row,col) is empty, otherwise it
is the Piece index */
/* row 0 is the top row, col 0 is the leftmost column */
kNoMove=0, /* allow
piece to fall normally */
kMoveLeft, kMoveRight, [TOKEN:12074] move piece left/right one
column */
kDrop,
/* drop piece to bottom of board */
kRotateClockwise, /* rotate piece
clockwise 90 degrees */
kRotateCounterClockwise /* rotate piece counterclockwise 90
degrees */
void InitTetris(
short boardWidth, /* width of board in
cells */
short boardHeight, /* height of board in
cells */
short numPieceTypes, [TOKEN:12074] number of types of pieces
*/
const Piece gamePieces[], /* pieces to play */
long timeToPlay /* game time, in
milliseconds */
);
MoveType /* move active piece */ Tetris(
const Board gameBoard,
/* current state of the game board,
bottom row is [boardHeight-1], left column is [0]
*/
short activePieceTypeIndex, /* index into gamePieces of active
piece */
short nextPieceTypeIndex, [TOKEN:12074] index into gamePieces of
next piece */
long pointsEarned, /* number of
points earned thus far */
long timeToGo /*
time remaining, in milliseconds */
);
void TermTetris(void);
The Tetris Challenge will work like this. Your InitTetris routine will be called first,
to allow you to set up the problem based on the board configuration and the Piece
shapes to be used in the problem. Next, your Tetris routine will be called multiple
times, allowing you to manipulate the falling Tetris pieces, with the objective of
accumulating as many points as possible. Your Tetris routine will continue to be called
until the specified timeToPlay has expired, or until no more Pieces can be placed on
the board. Then your TermTetris routine will be called, allowing you to deallocate any
dynamically allocated storage.
InitTetris will be provided with the width (boardWidth) and height (boardHeight) of
the game Board. It will also be given the numPieceTypes gamePieces to be used in the
game, and the length of the game (timeToPlay) in milliseconds.
Each call to Tetris gives you the current state of the gameBoard; you should determine
what you want to do with the active game Piece and return the corresponding
MoveType. The test code will attempt to translate or rotate the active game Piece
according to the MoveType you specify prior to dropping the Piece down one row. If the
Piece cannot be moved or rotated as you request, the Piece will simply drop down one
row. When the active Piece drops as far as it can, it will remain the active piece for
one more game cycle, so that you can move it left or right by one position should you so
choose. The Tetris parameters also provide you with the type of the next piece to be
played (nextPieceTypeIndex), the pointsEarned so far, and the timeToGo still
remaining in the game.
The gameBoard will contain the value -1 in each empty cell, and the index of the Piece
occupying that cell for nonempty cells. Game Piece shapes are specified in a 7x7
array, with a 1 indicating that the corresponding cell is occupied. Pieces rotations
occur about the central cell in that array. When Tetris is called with a new active game
Piece, the Piece will be positioned just above the gameBoard, with the bottom row of
the Piece due to appear on the gameBoard the next time Tetris is called.
The winner will be the solution that scores the most Tetris points within the specified
timeToPlay. You score 1 point for each row that a Piece falls when it is dropped. When
you eliminate a row, you earn 100 points. If multiple rows are completed at the same
time, you win additional points: the second row completed by dropping a block is worth
200 points, the third 300 points, and the fourth 400 points. If you should eliminate
all blocks on the board, you earn an additional 1000 points.
The Challenge prize will be divided between the overall winner and the best scoring
entry from a contestant that has not won the Challenge recently. If you have wanted to
compete in the Challenge, but have been discouraged from doing so, perhaps this is
your chance at some recognition and a share of the Challenge prize.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment.
Solutions may be coded in C, C++, or Pascal. You can also provide a solution in Java,
provided you also provide a test driver equivalent to the C code provided on the web for
this problem.
Three Months Ago Winner
Congratulations to Ernst Munter (Kanata, Ontario) for another Programmer's
Challenge victory. Ernst submitted the winning entry to the October "Which Bills Did
They Pay" Challenge. This Challenge required contestants to sort out a set of invoices
and a set of payments, matching payments to invoices. The solutions had to deal with
payments that settled multiple invoices and partial payments of an invoice. Scoring
was based on minimizing a "late-dollar-days" value that was the product of the amount
of the invoice (or part of an invoice) times the number of days the amount went
unpaid, thus encouraging the solution to apply payments to the oldest applicable
invoice.
Ernst beat out the second-place entry by new contestant Sue Flowers. Sue's solution
generated the same late-dollar-days value that Ernst's entry generated, but required
significantly more execution time to do so. In several of the larger test cases, Sue's
entry generated the same bill reconciliation log as Ernst's entry did, although this was
not true in all cases. Besides Ernst's and Sue's entries, two additional entries for this
Challenge were submitted, but neither solved the test cases correctly.
As always, Ernst's code is well commented. His entry makes two passes through the
payment list, the first time looking for either a perfect match with a single invoice or
a perfect match with multiple invoices. Ernst's CombineInvoices routine uses a
stack-based technique to find the combination of invoices that exactly matches the
payment amount. Although I didn't specifically analyze the performance of the
individual routines in Ernst's code, I believe that the CombineInvoices routine is key
to the performance Ernst achieved. In the second pass, his code looks for the "best
possible partial payment match, where "best" is defined as the invoice with the
invoiced amount closest to the payment amount. Finally, the code makes a third pass
through any remaining unpaid invoices to calculate the late-dollar-days statistic.
The table below lists, for each of the solutions submitted, the late-dollar-days value
produced by the combined test cases, the cumulative execution time, and the number of
reconciliation records generated. It also provides the code size, data size, and
programming language used for each entry. 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 $Days Time (msecs) Records Errors? Code Size Data Size
Lang
Ernst Munter (661) 1829792 0.43 679 no 2756 180 C++
Sue Flowers 1829792 46.54 712 no 4156 233 C
A.D. 44692680 0.78 11 yes 1272 24 C++
R. S. crash 13836 1775 C++
Top Contestants...
Listed here are the Top Contestants for the Programmer's Challenge, including
everyone who has accumulated 10 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.
Rank Name Points
1. Munter, Ernst 251
2. Saxton, Tom 96
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Boring, Randy 52
6. Shearer, Rob 48