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

Notion 2.1.9 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks More guests: invite up to 10 collaborators, friends & family to your pages Page... Read more
Spotify 1.2.0.1165 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Thunderbird 102.5.1 - Email client from...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Pinegrow 7.03 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
Adobe After Effects 2022 23.1 - Create p...
The new, more connected Adobe After Effects can make the impossible possible. Get powerful new features like a Live 3D Pipeline that brings CINEMA 4D scenes in as layers - without intermediate... Read more
SteerMouse 5.6.7 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Wireshark 4.0.2 - 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
Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as $54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password 8.9.10 - Powerful password man...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more

Latest Forum Discussions

See All

‘Awaken Legends: Idle RPG’ Celebrates th...
Awaken Legends: Idle RPG is adding its first update since the game was soft-launched in November, letting players get their hands on a new hero “Hera Valen". Players can also look forward to the Covenant of the Dark Knight event and the Wishing Well... | Read more »
‘Horizon Chase 2’ Japan World Tour Expan...
Horizon Chase 2 () from Aquiris is getting a major expansion today on Apple Arcade. The Japan World Tour expansion brings in 11 new races across 9 cities and it should be rolling out now as of this writing. I expect it to be available worldwide... | Read more »
Dark Fantasy Visual Novel ‘The 13th Mont...
Originally announced for release in August, The 13th Month from Japanese developer Kobayashimaru and publisher Kodansha released on PC via Steam worldwide this month. The dark fantasy visual novel that reimagines the classic Sleeping Beauty tale, is... | Read more »
Tom Clancey’s The Divison Resurgence ann...
Ubisoft has announced the latest Live Test dates for Tom Clancy’s The Division Resurgence, the hotly anticipated mobile entry in the Divison series. Starting December 8th and ending on the 22nd, the test will offer a huge amount of content for the... | Read more »
‘Easy Come Easy Golf’ New Update Adds St...
Easy Come Easy Golf () from Clap Hanz is one of my favorite games on Apple Arcade. It has been updated quite a bit since launch bringing in new modes and improvements. It recently launched on Nintendo Switch as well. | Read more »
Out Now: ‘Magic vs Metal’, ‘Suzerain’, ‘...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 7th, 2022. Today can be accurately described as Mikhail Madness, with a whopping four reviews from our pal-est of pals. Football Manager 2023 Touch, Wobbledogs, Soccer Story... | Read more »
Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »
‘Genshin Impact’ Version 3.3 Update Now...
HoYoverse recently revealed the next major update for Genshin Impact (Free) in the form of version 3.3 ‘All Senses Clear, All Existence Void’. | Read more »

Price Scanner via MacPrices.net

New! Details on Verizon’s Christmas/Holiday p...
Verizon is offering discounts on iPhones, Apple Watch models, and iPads with specific promo codes as part of their Christmas/Holiday 2022 offerings. Codes are valid when adding a new line of service... Read more
Apple MagSafe accessories are back on Holiday...
Amazon has Apple MagSafe Chargers and Apple’s MagSafe Battery on sale for up to 24% off MSRP again as part of their Christmas/Holiday sale. Shipping is free, and all models are in stock: – MagSafe... Read more
13″ M2 MacBook Airs on sale again for the low...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $150 off MSRP as part of their Christmas/Holiday Sale, prices start at $1049. Shipping is free. They are the lowest prices... Read more
Get an Apple 16″ MacBook Pro for $400 off MSR...
16″ MacBook Pros with Apple’s M1 Pro CPUs are in stock and on sale today at B&H Photo for $300-$400 off Apple’s MSRP for a limited time. Prices start at $2099 for M1 Pro models with 512GB or 1TB... Read more
Holiday clearance sale! Previous-generation A...
Amazon has 2nd generation 32GB and 64GB 4K Apple TVs with Siri remotes and 32GB Apple TV HDs on clearance sale for $80-$90 off original MSRP. Shipping is free, and delivery is available in time for... Read more
Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for $159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is $90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take $400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The $400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to $60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s $...
If you switch to Xfinity Mobile and open a new line of service, they will take $500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for $269.99 shipped as part of their Christmas/Holiday Sale. Their price is $60 off Apple’s MSRP. Free delivery... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.