TweetFollow Us on Twitter

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;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

macOS Catalina 10.15.7 - An Operating Sy...
macOS Catalina gives you more of everything you love about Mac. Experience three all-new media apps: Apple Music, Apple TV, and Apple Podcasts. Locate a missing Mac with the new Find My app. And now... Read more
BlueStacks 4.230.10 - Run Android applic...
BlueStacks App Player lets you run your Android apps fast and fullscreen on your Mac. Feature comparison chart How to install Bluestacks on your Mac Go to MacUpdate and click the green "Download"... Read more
Kodi 18.8 - Powerful media center tool f...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
Wireshark 3.2.7 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Fantastical 3.2 - Create calendar events...
Fantastical is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
Mindjet MindManager 13.2.132 - Professio...
MindManager is a powerful mind mapping tool that increases your productivity. From business plans or developing a new website, its robust mind maps have all the features you need to accomplish your... Read more
Tweetbot 3.4.3 - Popular Twitter client.
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more
OmniPlan 4.0.2 - Professional-grade proj...
With OmniPlan, you can create logical, manageable project plans with Gantt charts, schedules, summaries, milestones, and critical paths. Break down the tasks needed to make your project a success,... Read more
Numbers 10.2 - Apple's spreadsheet...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
A Better Finder Attributes 6.25 - Change...
A Better Finder Attributes 6 allows you to change JPEG & RAW shooting dates, JPEG EXIF meta-data tags, file creation & modification dates, file flags and deal with invisible files. Correct... Read more

Latest Forum Discussions

See All

BTS Universe Story, the social game that...
Netmarble's highly anticipated social game, BTS Universe Story, is available now for iOS and Android. It's the second collaboration between the hugely successful mobile developer and the K-pop superstars following BTS World. [Read more] | Read more »
The 5 Best Mobile Games Like Hades
Supergiant Games finally released Hades upon the world this week, and we’re loving it. The game plays to all of the studio’s strengths while still retaining a strong sense of identity. It also just so happens to play rather well using the Steam... | Read more »
A Year of Apple Arcade: The Good, The Ba...
Apple Arcade has persisted for just over a year at this point, and although that means I've been busy ranking and re-ranking every game on the service for just about as long, I haven't done much reflection on the service as a whole. [Read more] | Read more »
Animal Restaurant anniversary event team...
Animal idle simulator Animal Restaurant is celebrating its first-year anniversary with a crossover event with popular YouTube series Aaron’s Animals. [Read more] | Read more »
Raziel: Dungeon Arena is a hack 'n...
Raziel: Dungeon Arena is available now on mobile and will appeal to fans of both comic books and old school dungeon crawlers. Not only will you hack 'n' slash your way through mobs of enemies but there's also fully-narrated animated comic to enjoy... | Read more »
Steam Link Spotlight - Hades
Steam Link Spotlight is a feature where we look at PC games that play exceptionally well using the Steam Link app. Our last entry was on Disco Elysium. Read about how it plays using Steam Link over here. | Read more »
Microsoft has acquired ZeniMax Media and...
In the latest of a series of blockbuster moves, Microsoft has now acquired Zenimax Media and its subsidiary, Bethesda Softworks, for $7.5 billion. [Read more] | Read more »
Infinity Mechs is an upcoming idle game...
Indie developer SkullStar studio has announced an upcoming idle mech game called Infinity Mechs. It draws inspiration from the mobile game Iron Saga and has been officially licensed by Game Duchy. It's set to launch for both iOS and Android on... | Read more »
PUBG Mobile Lite's latest update se...
PUBG Mobile Lite, the streamlined version of the popular battle royale that's designed to work on less powerful devices, sees the return of a popular game variant today, Survive Till Dawn mode. It arrives as part of the 0.19.0 content update. [... | Read more »
Matchy Catch, Jyamma Games’ new hyper-ca...
Matchy Catch is a new hyper-casual puzzler from Jyamma Games, the Italian studio behind the Pong-inspired puzzle-adventure Hi-Ball Rush. It’s only the developer’s second game for iOS and Android devices, but it promises to be every bit as fun and... | Read more »

Price Scanner via MacPrices.net

Lowest price anywhere: New 13″ 2.0GHz MacBook...
Amazon has new 2020 13″ 2.0GHz/512GB MacBook Pros with 10th generation Intel processors back in stock on sale today for $200 off Apple’s MSRP. Shipping is free. Be sure to purchase the MacBook Pro... Read more
Apple Pro Display XDR with Nano-Texture Glass...
Amazon Apple Premier Partner GatorTec has the Apple Pro Display XDR with Nano-Texture Glass on sale for $5599 shipped, on Amazon. Their price is $400 off Apple’s MSRP, and it’s the cheapest price... Read more
Get a 2019 13″ MacBook Air for only $779 toda...
Apple has clearance, Certified Refurbished, 2019 13″ 1.6GHz/128GB MacBook Airs available again for $779. Each MacBook features a new outer case, comes with a standard Apple one-year warranty, and is... Read more
2020 11″ iPad Pros on sale today for $50-$75...
Apple reseller Expercom has new 2020 11″ Apple iPad Pros on sale for $50-$75 off MSRP, with prices starting at $749. These are the same iPad Pros sold by Apple in their retail and online stores: – 11... Read more
Apple has restocked 2020 13″ MacBook Airs sta...
Apple has restocked Certified Refurbished 2020 13″ MacBook Airs starting at only $849 and up to $200 off the cost of new Airs. Each MacBook features a new outer case, comes with a standard Apple one-... Read more
Apple’s new 8th generation 10.2″ iPads are on...
Amazon is discounting new 2020 8th generation 10.2″ Apple iPads by up to $35 off MSRP with prices starting at only $299. Shipping is free. These are the same iPads sold by Apple in their retail and... Read more
Today on Woot: Apple refurbished 16″ MacBook...
Amazon-owned Woot has Apple refurbished 16″ MacBook Pros available today for up to $605 off the cost of new models. Shipping is free for Prime members: – 16″ 6-Core MacBook Pros: $1874.99 $525 off... Read more
Apple offers last year’s iMacs for as little...
Apple has dropped prices on last year’s 21″ iMacs, Certified Refurbished, by up to $240 off the original cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Get last year’s 32GB iPad for only $279 today...
Amazon has dropped prices on clearance 2019 Silver 32GB WiFi Apple iPads by $50 to $279 shipped. That’s the cheapest price available for a new 10.2″ iPad from any Apple reseller. Act now if you’re... Read more
New Apple Watch Series 6 and SE models now on...
Amazon is the first Apple reseller to offer the new Apple Watch Series 6 and Apple Watch SE models at discounted sale prices. These are the same Watches sold by Apple in their retail and online... Read more

Jobs Board

Security Officer ($23.00/Hourly) - *Apple*...
**Security Officer \($23\.00/Hourly\) \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated Read more
*Apple* Certified Macintosh Technician - Exc...
Apple Certified Macintosh Technician Summary Title: Apple Certified Macintosh Technician ID:350 Department:All Location:Falls Church, VA Description Apple Read more
Department Manager- Tech Shop/ *Apple* Stor...
…their parents want, and our faculty needs. As a Department Manager in our Tech Shop/ Apple Store you will spend the majority of your time on the sales floor engaging Read more
Security Officer ($23.00/Hourly) - *Apple*...
**Security Officer \($23\.00/Hourly\) \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated Read more
Product Manager, *Apple* Commercial Sales -...
Product Manager, Apple Commercial Sales Austin, TX, US Requisition Number:77652 As an Apple Product Manager for the Commercial Sales team at Insight, you Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.