Apr 01 Challenge
Volume Number: 17 (2001)
Issue Number: 4
Column Tag: Programmer's Challenge
Programmer's Challenge
By Bob Boonstra, Westford, MA
Crossword II
Several years ago we held a Programmers Challenge based on crossword puzzles. So when my son came home from school with an idea for a crossword Challenge, my first thought was that we had been there and done that. The old Challenge required readers to solve a crossword puzzle, fitting the available words into a predefined pattern, without the benefit of clues. My son's problem, to generate a crossword puzzle, is sufficiently different to make a potentially interesting Challenge.
The prototype for the code you should write is:
typedef struct Words {
char *theWord; /* null terminated string */
short value; /* points value for theWord */
} Words;
typedef struct WordPositions {
short whichWord; /* index in Words array of word being placed */
short row; /* row in which the first letter of the word is placed */
short col; /* col in which the first letter of the word is placed */
short orientation; /* 0==down, 1==across */
} WordPositions;
long /* numberOfWordPositions */ CrosswordII (
short puzzleSize, /* puzzle has puzzleSize rows and columns */
const Words words[], /* words to be used to form the puzzle */
short numWords, /* number of words[] available */
WordPositions positions[] /* placement of words in puzzle */
);
The homework assignment that inspired this Challenge was from Chemistry class. Students were required to generate a 20x20 crossword puzzle using the names of the first 103 elements from the periodic table. Each word placed had a value equal to the atomic number for that element. So placing the word "lawrencium" earns you 103 points, "molybdenum" is worth only 42, but "lead" is worth 82. The assignment was to generate a crossword puzzle worth as many points as possible.
For the Challenge, we'll generalize the problem to work with an arbitrary list of words and arbitrarily assigned values. The puzzle dimension will be puzzleSize x puzzleSize instead of 20x20. You should decide which words to place where in the puzzle and return your word placements in the positions array, specifying in positions[].whichWord the index in words of the word being placed, the cell in which the first letter of the word is placed in positions[].row and positions[].col, and the direction the word is being placed in positions[].orientation. Your CrosswordII routine should return the number of words placed in the puzzle.
A few constraints: Each of the words will be at least 3 letters long and terminated with a zero byte. Every pair of adjacent letters in the puzzle you form must be part of some word. No word may occur more than once in the puzzle. Words may be placed horizontally or vertically, but not diagonally.
The winner will be the solution that earns the most points. Points will be based on the value of the words you place in your crossword puzzle, minus a penalty of 1% for each minute of execution time. 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.
This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal. You may provide a solution in Java instead, 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 Willeke Rieken for winning the January Tetris Challenge. The Tetris Challenge required readers to provide a player for the classic Tetris game. Willeke actually won by default, as his was the only entry. As I've said before, you can't win if you don't play. With this win, Willeke vaults into second place in our Challenge points standings.
Willeke describes his solution as "low tech". The heavy lifting is done in his MovePiece routine, where he determines the position and orientation of the current piece that provides the best fit. His heuristic for best fit takes into consideration the number of unreachable empty spaces created by placing a piece, with special weighting against placements that create "deep pits". The solution does not take advantage of the opportunity to move a piece after it has been dropped, nor does it use the information provided about the next piece to be placed.
Top Contestants...
Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 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 |
281 |
| 2. |
Rieken, Willeke |
85 |
| 3. |
Saxton, Tom |
76 |
| 4. |
Maurer, Sebastian |
68 |
| 5. |
Boring, Randy |
52 |
| 6. |
Shearer, Rob |
48 |
| 7. |
Taylor, Jonathan |
36 |
| 8. |
Wihlborg, Charles |
29 |
... and the Top Contestants Looking For a Recent Win
Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.
| 9. |
Downs, Andrew |
12 |
| 10. |
Jones, Dennis |
12 |
| 11. |
Day, Mark |
10 |
| 12. |
Duga, Brady |
10 |
| 13. |
Fazekas, Miklos |
10 |
| 14. |
Flowers, Sue |
10 |
| 15. |
Sadetsky, Gregory |
10 |
| 16. |
Selengut, Jared |
10 |
| 17. |
Strout, Joe |
10 |
| 18. |
Hala, Ladislav |
7 |
| 19. |
Miller, Mike |
7 |
| 20. |
Nicolle, Ludovic |
7 |
| 21. |
Schotsman, Jan |
7 |
| 22. |
Widyyatama, Yudhi |
7 |
| 23. |
Heithcock, JG |
6 |
There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:
| 1st place |
20 points |
| 2nd place |
10 points |
| 3rd place |
7 points |
| 4th place |
4 points |
| 5th place |
2 points |
| finding bug |
2 points |
| suggesting Challenge |
2 points |
Here is Willeke's winning Tetris solution:
tetris.cp
Copyright © 2001
Willeke Rieken
/*
a piece is dropped at each column and points are given for
creating empty cells and adding height. points are subtracted
for fitting in existing holes. the column with the lowest
score wins. the moves to drop the piece in the winning
column are placed in an array. in subsequent calls of Tetris
the next move is returned.
this is a low tech solution without using the next piece or
the possibility to move a piece after it dropped.
*/
#include <stdio.h>
#include <string.h>
#include "Tetris.h"
#define kPieceSize 7
#define kHalfPieceSize 3
#define kMaxBoardSizeSize 256
#define kMaxNrRotations 4
typedef struct PieceInfo {
long pieceLeft, pieceRight, pieceTop, pieceBottom;
long nrOfRorations;
} PieceInfo;
static const Piece *gGamePieces;
static MoveType gMovesToDo[(kMaxBoardSizeSize / 2) + 3];
// (max board size/2) lefts or rights + 2 rotations + drop
static PieceInfo *gPieceInfo;
static long gNrMovesToDo, gMoveNr;
static long gLastPieceIndex, glastNextPieceIndex;
static long gNumRows, gNumCols;
static long gNumPieceTypes, gMaxPieceSize;
PieceFits
static short PieceFits(const Board gameBoard, long *theTopOfPieces,
Piece theActivePiece,
long thePieceLeft, long thePieceRight,
long thePieceTop, long thePieceBottom,
long theRow, long theCol,
short theMustFitInBoard)
// check if the piece will fit on the board at
// position (theRow,theCol), if theMustFitInBoard then
// the total piece has to be on the board
{
long aRowOffset, aColOffset;
long aRow, aCol;
aRowOffset = theRow - thePieceBottom - 1;
aColOffset = theCol - kHalfPieceSize;
for (aRow = thePieceTop; aRow <= thePieceBottom; aRow++)
for (aCol = thePieceLeft; aCol <= thePieceRight; aCol++)
{
if (theActivePiece[aRow][aCol])
{
if (aRowOffset + aRow < 0)
if (theMustFitInBoard)
return 0;
else
break;
if (theMustFitInBoard)
if (aRowOffset + aRow >=
theTopOfPieces[aColOffset + aCol])
return 0;
if (gameBoard[aRowOffset + aRow][aColOffset + aCol] >= 0)
return 0;
}
}
return 1;
}
RotatePiece90
static void RotatePiece90(Piece theActivePiece,
long *aPieceLeft, long *aPieceRight,
long *aPieceTop, long *aPieceBottom)
// rotates the piece 90° clockwise
{
Piece aRotatedPiece;
long aRow, aCol;
for (aRow = 0; aRow < kPieceSize; aRow++)
for (aCol = 0; aCol < kPieceSize; aCol++)
aRotatedPiece[aCol][kPieceSize - 1 - aRow] =
theActivePiece[aRow][aCol];
memcpy(theActivePiece, aRotatedPiece, sizeof(Piece));
aRow = *aPieceLeft;
*aPieceLeft = kPieceSize - 1 - *aPieceBottom;
*aPieceBottom = *aPieceRight;
*aPieceRight = kPieceSize - 1 - *aPieceTop;
*aPieceTop = aRow;
}
RotatePiece180
static void RotatePiece180(Piece theActivePiece,
long *aPieceLeft, long *aPieceRight,
long *aPieceTop, long *aPieceBottom)
// rotates the piece 180°
{
Piece aRotatedPiece;
long aRow, aCol;
for (aRow = 0; aRow < kPieceSize; aRow++)
for (aCol = 0; aCol < kPieceSize; aCol++)
aRotatedPiece[kPieceSize - 1 - aRow][kPieceSize - 1 - aCol]
= theActivePiece[aRow][aCol];
memcpy(theActivePiece, aRotatedPiece, sizeof(Piece));
aRow = *aPieceTop;
*aPieceTop = kPieceSize - 1 - *aPieceBottom;
*aPieceBottom = kPieceSize - 1 - aRow;
aRow = *aPieceLeft;
*aPieceLeft = kPieceSize - 1 - *aPieceRight;
*aPieceRight = kPieceSize - 1 - aRow;
}
RotatePiece270
static void RotatePiece270(Piece theActivePiece,
long *aPieceLeft, long *aPieceRight,
long *aPieceTop, long *aPieceBottom)
// rotates the piece 90° counter clockwise
{
Piece aRotatedPiece;
long aRow, aCol;
for (aRow = 0; aRow < kPieceSize; aRow++)
for (aCol = 0; aCol < kPieceSize; aCol++)
aRotatedPiece[kPieceSize - 1 - aCol][aRow] =
theActivePiece[aRow][aCol];
memcpy(theActivePiece, aRotatedPiece, sizeof(Piece));
aRow = *aPieceTop;
*aPieceTop = kPieceSize - 1 - *aPieceRight;
*aPieceRight = *aPieceBottom;
*aPieceBottom = kPieceSize - 1 - *aPieceLeft;
*aPieceLeft = aRow;
}
FindCompletedLines
static void FindCompletedLines(const Board gameBoard,
short theCompletedLines[kPieceSize],
long *theNrCompletedLines,
Piece theActivePiece,
long thePieceLeft, long thePieceRight,
long thePieceTop, long thePieceBottom,
long theRow, long theCol)
// find the lines that are completed and will disappear after the piece dropped
{
long aRowOffset, aColOffset;
long aRow, aCol;
aRowOffset = theRow - thePieceBottom - 1;
aColOffset = theCol - kHalfPieceSize;
for (aRow = 0; aRow < kPieceSize; aRow++)
theCompletedLines[aRow] = 0;
*theNrCompletedLines = 0;
for (aRow = thePieceTop; aRow <= thePieceBottom; aRow++)
{
theCompletedLines[aRow] = 1;
for (aCol = thePieceLeft; aCol <= thePieceRight; aCol++)
if ((!theActivePiece[aRow][aCol]) &&
(gameBoard[aRowOffset + aRow][aColOffset + aCol] == -1))
{
theCompletedLines[aRow] = 0;
break;
}
if (theCompletedLines[aRow])
{
for (aCol = 0; aCol < aColOffset + thePieceLeft; aCol++)
if (gameBoard[aRowOffset + aRow][aCol] == -1)
{
theCompletedLines[aRow] = 0;
break;
}
}
if (theCompletedLines[aRow])
{
for (aCol = aColOffset + thePieceRight + 1;
aCol < gNumCols; aCol++)
if (gameBoard[aRowOffset + aRow][aCol] == -1)
{
theCompletedLines[aRow] = 0;
break;
}
}
if (theCompletedLines[aRow])
(*theNrCompletedLines)++;
}
}
CountEmptySpaces
static long CountEmptySpaces(long *theTopOfPieces,
short theCompletedLines[kPieceSize],
Piece theActivePiece,
long thePieceLeft, long thePieceRight,
long thePieceTop, long thePieceBottom,
long theRow, long theCol)
// count the empty cells as a result of the piece being dropped
// at theCol. don't include the empty cells that will be part
// of the big space at the top after de completed lines are removed
{
long aRowOffset, aColOffset;
long aRow, aCol, aNrOfEmptySpaces;
aRowOffset = theRow - thePieceBottom - 1;
aColOffset = theCol - kHalfPieceSize;
aNrOfEmptySpaces = 0;
for (aCol = thePieceLeft; aCol <= thePieceRight; aCol++)
{
short aPieceInColumn = 0;
for (aRow = thePieceTop; aRow <= thePieceBottom; aRow++)
if (theActivePiece[aRow][aCol] &&
(!theCompletedLines[aRow]))
{
aPieceInColumn = 1;
break;
}
if (aPieceInColumn)
{
aRow = thePieceTop;
while ((!theActivePiece[aRow][aCol]) &&
(aRow <= thePieceBottom))
aRow++;
while ((aRow + aRowOffset <
theTopOfPieces[aColOffset + aCol]) &&
(aRow <= thePieceBottom))
{
if (!theActivePiece[aRow][aCol])
aNrOfEmptySpaces++;
aRow++;
}
if (aRow + aRowOffset < theTopOfPieces[aColOffset + aCol])
if ((theTopOfPieces[aColOffset + aCol] - aRow - aRowOffset)
> gMaxPieceSize)
aNrOfEmptySpaces += gMaxPieceSize;
else
aNrOfEmptySpaces += (theTopOfPieces[aColOffset + aCol] -
aRow - aRowOffset);
}
}
return aNrOfEmptySpaces;
}
CountTouches
static long CountTouches(const Board gameBoard,
long *theTopOfPieces, Piece theActivePiece,
long thePieceLeft, long thePieceRight,
long thePieceTop, long thePieceBottom,
long theRow, long theCol)
// count at how many cells the piece will touch the pieces on
// the board, subtract points for creating deep pits
{
long aRowOffset, aColOffset;
long aRow, aCol, aNrOfTouches;
aRowOffset = theRow - thePieceBottom - 1;
aColOffset = theCol - kHalfPieceSize;
aNrOfTouches = 0;
for (aRow = thePieceTop; aRow <= thePieceBottom; aRow++)
for (aCol = thePieceLeft; aCol <= thePieceRight; aCol++)
if (theActivePiece[aRow][aCol])
{
// touches on the left
if (aColOffset + aCol == 0)
aNrOfTouches++;
else
if (((aCol == thePieceLeft) ||
(!theActivePiece[aRow][aCol - 1])) &&
(gameBoard[aRowOffset + aRow][aColOffset + aCol - 1]
!= -1))
aNrOfTouches++;
// touches on the right
if (aColOffset + aCol == gNumCols - 1)
aNrOfTouches++;
else
if (((aCol == thePieceRight) ||
(!theActivePiece[aRow][aCol + 1])) &&
(gameBoard[aRowOffset + aRow][aColOffset + aCol + 1]
!= -1))
aNrOfTouches++;
// touches on the bottom
if (aRowOffset + aRow == gNumRows - 1)
aNrOfTouches++;
else
if (((aRow == thePieceBottom) ||
(!theActivePiece[aRow + 1][aCol])) &&
(gameBoard[aRowOffset + aRow + 1][aColOffset + aCol]
!= -1))
aNrOfTouches++;
}
// check for deep pits
if ((aColOffset + thePieceLeft > 0) &&
(theTopOfPieces[aColOffset + thePieceLeft - 1] >
aRowOffset + thePieceBottom + 1))
{
aNrOfTouches -=
((theTopOfPieces[aColOffset + thePieceLeft - 1]) -
(aRowOffset + thePieceTop + 1));
aRow = thePieceTop;
while (!theActivePiece[aRow][thePieceLeft])
{
aRow-;
aNrOfTouches++;
}
}
if ((aColOffset + thePieceRight < gNumCols - 1) &&
(theTopOfPieces[aColOffset + thePieceRight + 1] >
aRowOffset + thePieceBottom + 1))
{
aNrOfTouches -= ((theTopOfPieces[aColOffset +
thePieceRight + 1]) -
(aRowOffset + thePieceTop + 1));
aRow = thePieceTop;
while (!theActivePiece[aRow][thePieceRight])
{
aRow-;
aNrOfTouches++;
}
}
return aNrOfTouches;
}
ValidMove
static short ValidMove(const Board gameBoard,
short activePieceTypeIndex,
long *theTopOfPieces, long theTopTopOfPieces,
long theCol, long theRotation)
// check if the piece can reach its column without
// colliding with pieces on the board
{
long aCol, aRow, aNrMovesToDo;
Piece anActivePiece;
long aPieceLeft, aPieceRight, aPieceTop, aPieceBottom;
memcpy(anActivePiece, gGamePieces[activePieceTypeIndex],
sizeof(Piece));
aPieceLeft = gPieceInfo[activePieceTypeIndex].pieceLeft;
aPieceRight = gPieceInfo[activePieceTypeIndex].pieceRight;
aPieceTop = gPieceInfo[activePieceTypeIndex].pieceTop;
aPieceBottom = gPieceInfo[activePieceTypeIndex].pieceBottom;
aRow = 1 - aPieceBottom;
// count moves
aNrMovesToDo = 0;
switch (theRotation)
{
case 0:
break;
case 1:
aNrMovesToDo++;
break;
case 2:
aNrMovesToDo++;
aNrMovesToDo++;
break;
case 3:
aNrMovesToDo++;
break;
}
if (theCol > gNumCols / 2)
aNrMovesToDo += theCol - gNumCols / 2;
else
aNrMovesToDo += gNumCols / 2 - theCol;
// check if the piece can move without hitting pieces on the board
if (aNrMovesToDo >= theTopTopOfPieces)
{
switch (theRotation)
{
case 0:
break;
case 1:
RotatePiece90(anActivePiece,
&aPieceLeft, &aPieceRight,
&aPieceTop, &aPieceBottom);
aRow++;
break;
case 2:
RotatePiece180(anActivePiece, &aPieceLeft,
&aPieceRight, &aPieceTop,
&aPieceBottom);
aRow++;
aRow++;
break;
case 3:
RotatePiece270(anActivePiece,
&aPieceLeft, &aPieceRight,
&aPieceTop, &aPieceBottom);
aRow++;
break;
}
aRow += aPieceBottom;
for (aCol = gNumCols / 2 + 1; aCol < theCol; aCol++)
if (!PieceFits(gameBoard, theTopOfPieces, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow + (aCol - (gNumCols / 2 + 1)), aCol, 0))
return 0;
for (aCol = gNumCols / 2 - 1; aCol > theCol; aCol-)
if (!PieceFits(gameBoard, theTopOfPieces, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow + ((gNumCols / 2 - 1) - aCol), aCol, 0))
return 0;
}
return 1;
}
MovePiece
static void MovePiece(const Board gameBoard,
short activePieceTypeIndex)
// determine the column for the piece and prepare the moves
{
Piece anActivePiece;
long aPieceLeft, aPieceRight, aPieceTop, aPieceBottom;
long aRow, aCol, aRotation;
long aTopOfPieces[kMaxBoardSizeSize];
long aBottomTopRow, aTopTopRow;
long aColScore[kMaxNrRotations][kMaxBoardSizeSize];
long aBestScore, aBestCol, aBestRotation;
long anExtraScore, aNrCompletedLines;
short aCompletedLines[kPieceSize];
short aValidMove;
memcpy(anActivePiece, gGamePieces[activePieceTypeIndex],
sizeof(Piece));
aPieceLeft = gPieceInfo[activePieceTypeIndex].pieceLeft;
aPieceRight = gPieceInfo[activePieceTypeIndex].pieceRight;
aPieceTop = gPieceInfo[activePieceTypeIndex].pieceTop;
aPieceBottom = gPieceInfo[activePieceTypeIndex].pieceBottom;
// find top of pieces in board
aBottomTopRow = 0;
aTopTopRow = gNumCols;
for (aCol = 0; aCol < gNumCols; aCol++)
{
aRow = 0;
while ((aRow < gNumRows) &&
(gameBoard[aRow][aCol] == -1)) aRow++;
aTopOfPieces[aCol] = aRow;
if (aBottomTopRow < aRow)
aBottomTopRow = aRow;
if (aTopTopRow > aRow)
aTopTopRow = aRow;
}
// find where the piece fits best
for (aRotation = 0;
aRotation < gPieceInfo[activePieceTypeIndex].nrOfRorations;
aRotation++)
{
for (aCol = 0; aCol < gNumCols; aCol++)
{
aColScore[aRotation][aCol] = 1000000;
if ((aCol >= kHalfPieceSize - aPieceLeft) &&
(aCol < gNumCols - aPieceRight + kHalfPieceSize))
{
aRow = aTopOfPieces[aCol] + kPieceSize - 1;
if (aRow > aBottomTopRow)
aRow = aBottomTopRow;
while ((!PieceFits(gameBoard, aTopOfPieces, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow, aCol, 1)) &&
(aRow >= 0))
aRow-;
if (aRow > (aPieceBottom - aPieceTop - 1))
{
aColScore[aRotation][aCol] =
((aBottomTopRow - aRow) +
(aPieceBottom - aPieceTop)) * 2;
FindCompletedLines(gameBoard, aCompletedLines,
&aNrCompletedLines, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow, aCol);
anExtraScore = CountEmptySpaces(aTopOfPieces,
aCompletedLines, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow, aCol);
aColScore[aRotation][aCol] += anExtraScore * 5;
anExtraScore = CountTouches(gameBoard,
aTopOfPieces, anActivePiece,
aPieceLeft, aPieceRight, aPieceTop, aPieceBottom,
aRow, aCol);
aColScore[aRotation][aCol] -= anExtraScore;
}
}
}
RotatePiece90(anActivePiece,
&aPieceLeft, &aPieceRight, &aPieceTop, &aPieceBottom);
}
aBestCol = 0;
aBestRotation = 0;
aValidMove = 0;
while (!aValidMove)
{
aBestScore = 1000000;
for (aRotation = 0;
aRotation < gPieceInfo[activePieceTypeIndex].nrOfRorations;
aRotation++)
for (aCol = 0; aCol < gNumCols; aCol++)
if (aColScore[aRotation][aCol] < aBestScore)
{
aBestScore = aColScore[aRotation][aCol];
aBestCol = aCol;
aBestRotation = aRotation;
}
if (aBestScore < 1000000) // found valid move
{
if (ValidMove(gameBoard, activePieceTypeIndex,
aTopOfPieces, aTopTopRow, aBestCol, aBestRotation))
aValidMove = 1;
else
aColScore[aBestRotation][aBestCol] = 1000000;
}
else
{
// no valid moves, give up
aBestCol = gNumCols / 2;
aBestRotation = 0;
aValidMove = 1;
}
}
// prepare moves
gNrMovesToDo = 0;
switch (aBestRotation)
{
case 1:
gMovesToDo[gNrMovesToDo] = kRotateClockwise;
gNrMovesToDo++;
break;
case 2:
gMovesToDo[gNrMovesToDo] = kRotateClockwise;
gNrMovesToDo++;
gMovesToDo[gNrMovesToDo] = kRotateClockwise;
gNrMovesToDo++;
break;
case 3:
gMovesToDo[gNrMovesToDo] = kRotateCounterClockwise;
gNrMovesToDo++;
break;
}
if (aBestCol > gNumCols / 2)
for (aCol = gNumCols / 2; aCol < aBestCol; aCol++)
{
gMovesToDo[gNrMovesToDo] = kMoveRight;
gNrMovesToDo++;
}
else
for (aCol = aBestCol; aCol < gNumCols / 2; aCol++)
{
gMovesToDo[gNrMovesToDo] = kMoveLeft;
gNrMovesToDo++;
}
gMovesToDo[gNrMovesToDo] = kDrop;
gNrMovesToDo++;
gMovesToDo[gNrMovesToDo] = kNoMove;
gNrMovesToDo++;
}
GetPieceInfo
static void GetPieceInfo()
// determine the bounds of the piece and if rotating
// the piece results in the same piece
{
long i;
for (i = 0; i < gNumPieceTypes; i++)
{
long aPieceLeft = kPieceSize - 1, aPieceRight = 0;
long aPieceTop = kPieceSize - 1, aPieceBottom = 0;
Piece anActivePiece;
long aRow, aCol, aRowOffset, aColOffset;
short aPiecesMatch;
memcpy(anActivePiece, gGamePieces[i], sizeof(Piece));
for (aRow = 0; aRow < kPieceSize; aRow++)
for (aCol = 0; aCol < kPieceSize; aCol++)
if (anActivePiece[aRow][aCol])
{
if (aRow < aPieceTop)
aPieceTop = aRow;
if (aRow > aPieceBottom)
aPieceBottom = aRow;
if (aCol < aPieceLeft)
aPieceLeft = aCol;
if (aCol > aPieceRight)
aPieceRight = aCol;
}
gPieceInfo[i].pieceLeft = aPieceLeft;
gPieceInfo[i].pieceRight = aPieceRight;
gPieceInfo[i].pieceTop = aPieceTop;
gPieceInfo[i].pieceBottom = aPieceBottom;
if (aPieceRight - aPieceLeft > gMaxPieceSize)
gMaxPieceSize = aPieceRight - aPieceLeft;
if (aPieceBottom - aPieceTop > gMaxPieceSize)
gMaxPieceSize = aPieceBottom - aPieceTop;
gPieceInfo[i].nrOfRorations = kMaxNrRotations;
RotatePiece90(anActivePiece,
&aPieceLeft, &aPieceRight, &aPieceTop, &aPieceBottom);
if ((aPieceRight - aPieceLeft) == (aPieceBottom - aPieceTop))
{
aPiecesMatch = 1;
aRowOffset = gPieceInfo[i].pieceTop - aPieceTop;
aColOffset = gPieceInfo[i].pieceLeft - aPieceLeft;
for (aRow = aPieceTop; aRow <= aPieceBottom; aRow++)
for (aCol = aPieceLeft; aCol <= aPieceRight; aCol++)
if ((anActivePiece[aRow][aCol] &&
!gGamePieces[i][aRow + aRowOffset][aCol +
aColOffset]) ||
(!anActivePiece[aRow][aCol] &&
gGamePieces[i][aRow +
aRowOffset][aCol + aColOffset]))
aPiecesMatch = 0;
if (aPiecesMatch)
gPieceInfo[i].nrOfRorations = 1;
}
if (gPieceInfo[i].nrOfRorations == kMaxNrRotations)
{
RotatePiece90(anActivePiece,
&aPieceLeft, &aPieceRight, &aPieceTop, &aPieceBottom);
aPiecesMatch = 1;
aRowOffset = gPieceInfo[i].pieceTop - aPieceTop;
aColOffset = gPieceInfo[i].pieceLeft - aPieceLeft;
for (aRow = aPieceTop; aRow <= aPieceBottom; aRow++)
for (aCol = aPieceLeft; aCol <= aPieceRight; aCol++)
if ((anActivePiece[aRow][aCol] &&
!gGamePieces[i][aRow +
aRowOffset][aCol + aColOffset]) ||
(!anActivePiece[aRow][aCol] &&
gGamePieces[i][aRow +
aRowOffset][aCol + aColOffset]))
aPiecesMatch = 0;
if (aPiecesMatch)
gPieceInfo[i].nrOfRorations = 2;
}
}
}
InitTetris
void InitTetris(
short boardWidth, /* width of board in cells */
short boardHeight, /* height of board in cells */
short numPieceTypes, /* number of types of pieces */
const Piece gamePieces[], /* pieces to play */
long timeToPlay /* game time, in milliseconds */
) {
gNumRows = boardHeight;
gNumCols = boardWidth;
gNumPieceTypes = numPieceTypes;
gGamePieces = gamePieces;
gNrMovesToDo = 0;
gMoveNr = 0;
gLastPieceIndex = -1;
glastNextPieceIndex = -1;
gPieceInfo = new PieceInfo[gNumPieceTypes];
gMaxPieceSize = 0;
GetPieceInfo();
gMaxPieceSize++;
}
Tetris
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, /* index into gamePieces of next piece */
long pointsEarned, /* number of points earned thus far */
long timeToGo /* time remaining, in milliseconds */
) {
// try to detect a new piece,
// will fail when a piece appears three times in a row
if ((gLastPieceIndex != activePieceTypeIndex) ||
(glastNextPieceIndex != nextPieceTypeIndex))
gMoveNr = gNrMovesToDo;
gLastPieceIndex = activePieceTypeIndex;
glastNextPieceIndex = nextPieceTypeIndex;
if (gMoveNr >= gNrMovesToDo)
{
// calculate the moves for a new piece
MovePiece(gameBoard, activePieceTypeIndex);
gMoveNr = 0;
}
// return next move
return gMovesToDo[gMoveNr++];
}
TermTetris
void TermTetris(void) {
delete[] gPieceInfo;
}
