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

WebSnapperPro 2.0.5 - $20.00
WebSnapperPro lets you capture full web pages exactly as they appear in your browser, with a single mouse click, without the need to "stitch" or cut-and-paste. Save the page as an image file or as... Read more
VOX 3.2.1 - Music player that supports m...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
Evernote 7.0 - Create searchable notes a...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
Hopper Disassembler 4.3.16- - Binary dis...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
VOX 3.2.1 - Music player that supports m...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
Evernote 7.0 - Create searchable notes a...
Evernote allows you to easily capture information in any environment using whatever device or platform you find most convenient, and makes this information accessible and searchable at anytime, from... Read more
Hopper Disassembler 4.3.16- - Binary dis...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
Default Folder X 5.2.2 - Enhances Open a...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click on... Read more
EtreCheck 4.0.1 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
Carbon Copy Cloner 5.0.9 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more

Latest Forum Discussions

See All

Our top 5 characters from casual RPG Cre...
Creature Quest definitely lives up to its name with a host of collectible creatures based on fantasy tales and world mythologies. To celebrate Creature Quest’s first birthday, we’re going to lay out what we think are the five best characters in the... | Read more »
Around the Empire: What have you missed...
Did you know that Steel Media has a whole swathe of other sites dedicated to all aspects of mobile gaming? Sure you'll get the very best iPhone news, reviews, and opinions right here at 148Apps, but we don't want you missing out on a single piece... | Read more »
All the best games on sale for iPhone an...
Oh hi there, and welcome to our round-up of the best games that are currently on sale for iPhone and iPad. You thought I didn't see you there, did you, skulking behind the bushes? Trust me though, the bushes aren't where the best deals are. The... | Read more »
The Battle of Polytopia Guide - How to H...
A new update just released for The Battle of Polytopia (formerly Super Tribes), which introduces online multiplayer. For all the fans of Midjiwan’s lite take on Civilization, this is certainly welcome news, but playing online isn’t as easy and... | Read more »
Here are the very best mobile games to p...
It's Valentine's Day! Did you get loads of cards and chocolates and other tacky, simple expressions of human affection? Did you send out tat because you find it almost impossible to express emotion unless there's a section dedicated to it at your... | Read more »
Florence (Games)
Florence 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: Florence is an interactive storybook from the award-winning lead designer of Monument Valley about the heart-racing highs and... | Read more »
Purrfect Date (Games)
Purrfect Date 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Cats are a lil’ like marmite. Either you absolutely head-over-heels love’ em, or… nahhh, who are we kidding?! Everyone... | Read more »
More monsters to collect and evolve in C...
A laid-back mix of RPG and TCG, Creature Quest is all about building your deck, evolving your creatures and winning in battle. It’s the creation of VC Mobile, set up by Might and Magic producer Jon Van Caneghem. There are elements of that classic... | Read more »
Check out this awesome hands-on with the...
Well, PlayerUnknown's Battlegrounds has come out on mobile. This isn't a clone, this isn't a riff on the battleroyale mechanics of the game, it's the official mobile port by Tencent. But there's a little bit of a hitch. [Read more] | Read more »
Hostage Negotiator (Entertainment)
Hostage Negotiator 1.1.0 Device: iOS Universal Category: Entertainment Price: $3.99, Version: 1.1.0 (iTunes) Description: Official app of the board game by AJ Porfirio and Van Ryder Games. In Hostage Negotiator, you play the part of... | Read more »

Price Scanner via MacPrices.net

13″ 3.1GHz/256GB Silver Touch Bar MacBook Pro...
Amazon has the Silver 13″ 3.1GHz/256GB Touch Bar MacBook Pro (MPXX2LL/A) on sale for $1649.99 including free shipping. Their price is $150 off MSRP, and it’s the lowest price available for a new 13″... Read more
Saturday Sale: Amazon offers 13″ 1.8GHz/256GB...
Amazon has the 13″ 1.8GHz/256B Apple MacBook Air on sale today for $250 off MSRP including free shipping: – 13″ 1.8GHz/256GB MacBook Air (MQD42LL/A): $949.99, $250 off MSRP Their price is the lowest... Read more
Roundup of Apple Certified Refurbished 12″ Ma...
Apple has Certified Refurbished 2017 12″ Retina MacBooks available for $200-$240 off the cost of new models. Apple will include a standard one-year warranty with each MacBook, and shipping is free.... Read more
Apple offers Certified Refurbished 10″ and 12...
Apple is now offering Certified Refurbished 2017 10″ and 12″ iPad Pros for $100-$190 off MSRP, depending on the model. An Apple one-year warranty is included with each model, and shipping is free: –... Read more
Apple Canada offers Certified Refurbished Mac...
 Canadian shoppers can save up to $560 on the purchase of a 2017 current-generation MacBook Pro, MacBook, or MacBook Air with Certified Refurbished models at Apple Canada. Apple’s refurbished prices... Read more
Sale! 13″ MacBook Airs for up to $180 off MSR...
B&H Photo has 13″ MacBook Airs on sale for $50-$120 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): $899, $... Read more
Sale! New 8-core iMac Pro for $4799, $200 off...
Adorama has the 8-core iMac Pro on sale for $4799 including free shipping plus NY & NJ sales tax only. Their price is $200 off MSRP, and it’s the currently lowest price available for an iMac Pro. Read more
Sale! Walmart lowers prices even more on 9″ i...
Walmart has lowered their sale price on 9.7″ Apple iPads to $80 off MSRP for a limited time. Sale prices are for online orders only, in-store prices may vary: – 9″ 32GB iPad: $249.99 $80 off – 9″... Read more
Roundup of 13″ MacBook Pro sales, models avai...
B&H Photo has 13″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only. Their prices are the lowest available for these... Read more
Roundup of 15″ MacBook Pros sale, models up t...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (... Read more

Jobs Board

*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113501424 Norman, Oklahoma, United States Posted: 15-Feb-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
Senior Program Manager - *Apple* Music - Ap...
# Senior Program Manager - Apple Music Job Number: 113393020 Seattle, Washington, United States Posted: 02-Feb-2018 Weekly Hours: 40.00 **Job Summary** Apple is Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.