/* scramble.c - Play scrabble against computer Author: Dale Reed Date: 4/22/99 Class: EECS 171 System: gcc compiler running under UNIX Input: Interactive user's commands letters text file dictionary text file Output: Resulting 2-D board configuration, tiles in hand, score Approach: This program implements a pseudo-scrabble game. The human plays against the computer, and the goal is to play the most number of tiles from one's "hand", making a valid word on the board. The first letter of each word must be an existi ng letter on the board. The exception, of course, is the first w ord, which must be entered by the user. Note that words can "wrap around" the right-hand and lower sides of the board. The program checks each word by comparing it again st a dictionary file. The words in the dictionary file are read into a dynamically allocated large array, and a binary search is done for each word lookup. The computer tries all possible words by genera ting all permutations of the letter tiles in its "hand," prepended by each sq uare on the board. The sum of the points for each letter then determines t he point value for that word. These points are taken from the letters inp ut text file. The word with the highest point value is then selected. Note that when a new word has letters adjacent to existing letters, unlike scrabble the new adjacent letters need not form a word. */ /* * Include libraries */ #include < stdio.h> #include < stdlib.h> #include < string.h> #include < ctype.h> #include < assert.h> /* * Global constants */ #define INCREMENT 5000 // size of chunk for dynamic memory allocation for dictionary #define ROWS 26000 // dictionary number of words max. #define WORDLENGTH 8 // max. size of a word in dictionary #define LINE_LENGTH 81 // max length of a line #define BOARD_SIZE 10 // size of board on a side #define TRUE 1 #define FALSE 0 #define NUMBER_OF_LETTERS 98 // Number of letters stored (no blanks) #define LETTERS_IN_ALPHABET 26 // Number of letters in the alphabet being used #define TILES_IN_HAND 7 // # of tiles a player has at a time #define WARNING 1 // severity level 1 for error m essage #define TERMINATE 2 // severity level 2 for error m essage #define CLEAR_SCREEN 1 // flag to indicate clearing screen #define DO_NOT_CLEAR_SCREEN 0 // flag indicating do not clear /* * Typedefs & Structs */ typedef char WordType[ WORDLENGTH+1]; // extra space for NULL typedef struct tileList * TileListStructP; // for linked list of t iles typedef struct tileList TileListStruct; // for linked list of t iles struct tileList { char letter; TileListStruct *nextP; }; /* * Global Variables */ WordType *Dictionary = NULL; // This will point to the dictionary int NumberOfDictionaryWords = 0; // Number of Dictionary words int DictionarySize = 0; // total size of dictionary //-------------------------------------------------------------------------- void error( char message[], // the message int severity, // severity: 1 or 2 (most sever e) int clearScreen) // display error message. Depending on severity, exit. { if ( clearScreen == TRUE) { system( "clear"); } printf("\n*** %s ***\n", message); fflush( stdout); if ( severity == TERMINATE) { printf("Abnormal termination of program...\n"); fflush( stdout) ; exit (-1); } } //-------------------------------------------------------------------------- void displayWords() // number of words in dictionary // display words in dictionary limited by size. Used for debugging. { int size; // stores size of strings int i; // loop counter int min, max; // limits on word sizes to display // Selectively display words from dictionary array. We do not // display them all because there are usually tens of thousands // of them. printf("Please enter min. and max. sizes of strings to display: "); scanf("%d %d", &min, &max); printf("\nWords stored in array are: \n"); for (i=0; i< NumberOfDictionaryWords; i++) { size = strlen( Dictionary[ i]); if ( (size >= min) && (size = DictionarySize) { // Allocate space for new, bigger array pTemp = (WordType *) malloc( sizeof( WordType) * (DictionarySiz e + INCREMENT) ); assert( pTemp != NULL); // sanity check on memory alloc ation // copy old dictionary array into new temporary array for (i=0; i < DictionarySize; i++) { strcpy( pTemp[ i], Dictionary[ i]); } // initialize new space in array to NULL characters for (i = DictionarySize; i < (DictionarySize + INCREMENT); i++) { pTemp[ i][0] = '\0'; } // free space from old array if there was any if ( Dictionary != NULL) { free( Dictionary); } // make old pointer point to new array Dictionary = pTemp; // Update new size of array DictionarySize += INCREMENT; } // We know there is space for the element to be added at this point, // Store the value in the appropriate spot strcpy( Dictionary[ NumberOfDictionaryWords], theWord); } //-------------------------------------------------------------------------- void getDictionaryWords( char dictionaryFileName[] ) // Read dictionary words into dictionary array { FILE *fin; // input file p ointer char tempString[ LINE_LENGTH]; // stores a single string int size; // string size int dictionarySize = 0; // dictionary size int i; // loop counter fin = fopen( dictionaryFileName, "r" ); // Open file while ( fscanf( fin, "%s", tempString ) != EOF ) { size = strlen( tempString); for (i=0; i< strlen( tempString); i++) { if ( islower( tempString[ i])) { tempString[ i] = toupper( tempString[ i]); } } /* Only store words that aren't too long */ if ( size < WORDLENGTH ) { store( tempString); } } fclose( fin); // Done, close input file // Now display the number of words found based on word size. // Used for debugging. // displayWords( ); } //-------------------------------------------------------------------------- int foundInDictionary( char *pWord, // poin ter to a word char dictionary[][ WORDLENGTH+1], // dictionary array int numberOfDictionaryWords) // number of words in d ictionary array // Look up the word in the dictionary array, returning 1 if found, 0 otherwise { int i; // counter to go through dictionary int low, mid, high; // array indices for binary search int searchResult; // Stores 0 if search succeeded // First eliminate any spaces in the words by substituting a NULL // character for any space found for (i=0; i< TILES_IN_HAND; i++) { if ( pWord[ i] == ' ') { pWord[ i] = '\0'; // End of string marker } } // Binary search for word low = 0; high = numberOfDictionaryWords - 1; while ( low letter = ' '; tileNodeP->nextP = NULL; return tileNodeP; } //-------------------------------------------------------------------------- void createTileList( TileListStruct ** theTiles) // Create the linked list for the tiles { TileListStruct * tileNodeP; // temporary tile node pointer TileListStruct * currentP; // pointer to current node on list int i; // loop counter // Create first element *theTiles = mallocANode(); currentP = *theTiles; // Create subsequent elements for (i=1; i< TILES_IN_HAND+1; i++) { currentP->nextP = mallocANode(); currentP = currentP->nextP; } } //-------------------------------------------------------------------------- void setTileValue( TileListStruct * theTiles, // the tile list to be used int index, // the element to be used char charValue) // the value to be stored at index // Store the charValue at position 'index' in linked list 'theTiles' { TileListStruct * tileNodeP; // temporary tile node pointer TileListStruct * currentP; // pointer to current node on list int itemNumber; // item number on the list // find the element at the "index" spot on the list. If the index goes // past the end of the list it was an invalid value. itemNumber = 0; currentP = theTiles; while ( itemNumber < index) { if ( currentP->nextP == NULL) { // error, index was invalid printf("Error, index of %d was invalid.\n", index); ffl ush(stdout); exit (-1); } currentP = currentP->nextP; itemNumber++; } // Now currentP points to the node on the "index" spot of the list // Return the address of the character part of that node, so it can // be used on the l.h.s. of an assignment statement. currentP->letter = charValue; } //-------------------------------------------------------------------------- char getTileValue( TileListStruct * theTiles, // the tile list to be used int index) // location at which we look // return the character at the "index" position in the list { TileListStruct * currentP; // pointer to current node on list int itemNumber; // item number on the list // find the element at the "index" spot on the list. If the index goes // past the end of the list, index was invalid itemNumber = 0; currentP = theTiles; while ( currentP != NULL) { if ( itemNumber == index) { return ( currentP->letter); } // advance to next list element currentP = currentP->nextP; itemNumber++; } // index was invalid return '\0'; } //-------------------------------------------------------------------------- void getTiles( TileListStruct * playerTiles, // tiles player has char letters[], // tiles remaining int *tilesRemaining) // # of tiles remaining // Get new tiles for player and correspondingly update tilesRemaining { int i; // loop counter int tileIndex; // the tile to get // replace blank tiles for (i=0; i< TILES_IN_HAND; i++) { if ( getTileValue( playerTiles, i) == ' ') { // Pick a random tile, use linear probing if it is alre ady taken tileIndex = rand() % NUMBER_OF_LETTERS; // Verify that all tiles haven't been used up if ( *tilesRemaining > 0) { while ( letters[ tileIndex] == ' ') { tileIndex = (tileIndex + 1) % NUMBER_OF _LETTERS; } // got one, now decrement # available and assig n it (*tilesRemaining)--; setTileValue( playerTiles, i, letters[ tileInde x]); letters[ tileIndex] = ' '; // Tile taken, blank it out } } // end if( player... } // end for ... } //-------------------------------------------------------------------------- void help( int letterPoints[]) // letterPoints has the points per lett er // Display help information { char returnCharacter; int i; printf("\n"); printf(" For each move you need to enter a row, a column, a move\n" ); printf("direction (a or d), and the word to be played at that spot.\n") ; printf("You may also enter 'X' to exit or 'H' for help. Input can\n"); printf("be either upper or lower case.\n"); printf("\n"); printf("E.g. \"E3 d rap\" puts the word \"rap\" starting at row E,\n" ); printf("column 3, going downwards.\n"); printf("Alternatively \"E3 a rap\" would put the word \"rap\" starting at\n"); printf("row E, column 3, going across.\n"); printf("\n"); printf("Here are the points each character is worth: \n"); for (i=0; i< LETTERS_IN_ALPHABET; i++) { // print the le tters if (letterPoints[ i] > 9) { // extr a space for larger point values printf(" "); } printf("%2c", 'A' + i); } printf("\n"); for (i=0; i< LETTERS_IN_ALPHABET; i++) { // print the point valu es if (letterPoints[ i] > 9) { printf(" "); // leave an extra space for large values } printf("%2d", letterPoints[ i]); // print the po int value } printf("\n\n"); printf("Please press the return key to continue..."); scanf("%c", &returnCharacter); } //-------------------------------------------------------------------------- void initialize( char board[ ][ BOARD_SIZE], // the board char letters[], // stores scrabble letter tiles int letterPoints[], // poin ts per letter char lettersFileName[], // file name for tiles TileListStruct ** computerTiles, // linked lis t of tiles the computer has TileListStruct ** humanTiles, // linked list of tiles human has int *tilesRemaining) // # of tiles remaining // Initialize data structures for game { int i,j; // loop counters int totalTiles; // total tiles, used for sanity check FILE *fTiles; char aLine[ LINE_LENGTH]; // Store an entire input line at a time char letter; // Stores letter read in from i nput line int howManyLetters; // How many of that letter ther e are int value; // Value for that lette r for scoring. // Not used i n this program. int currentLetterIndex = 0; // iterator used to track current spot // to store a l etter in letters array char returnCharacter; // stores extra return character // Display initial welcome and game explanation. system( "clear"); // clear the screen printf(" Welcome to the game of scramble, where you try to build \n "); printf("English words on a board. The board itself is two dimensional,\ n"); printf("with rows marked by letters, and columns marked by numbers.\n") ; printf("A combination of row and column uniquely identify each square.\ n"); printf(" Each word you create (after the first one) must start \n") ; printf("with an existing letter on the board, and the subsequent \n"); printf("letters must be played into blank squares. Words must be \n"); printf("created out of the tiles you have in your \"hand\".\n"); printf(" When a new word has letters adjacent to existing letters,\ n"); printf("you do not need to create valid words with those adjacent lette rs.\n"); printf("One point is given per letter played. The winner is the player with\n"); printf("the most points."); printf("\n\n"); printf("Please press the return key to continue..."); scanf("%c", &returnCharacter); // initialize 2-D board with periods for (i=0; i< BOARD_SIZE; i++) { for (j=0; j < BOARD_SIZE; j++) { board[ i][ j] = '.'; } } fTiles = fopen( lettersFileName, "r"); fgets( aLine, LINE_LENGTH, fTiles); // read in an entire li ne sscanf( aLine, "%d", &totalTiles); // read number from inp ut line fgets( aLine, LINE_LENGTH, fTiles); // skip title line if ( totalTiles != NUMBER_OF_LETTERS) { // Sanity check printf( " *** Error, number of tiles: %d ", totalTiles); printf( "in file %s", lettersFileName); printf(" doesn't match NUMBER_OF_LETTERS: %d\n", NUMBER_OF_LETT ERS); printf(" Exiting program...\n"); exit( -1); } // zero out totalTiles and use it to accumulate sum of number of tiles // to again verify totals are correct totalTiles = 0; // Read number of each type of tile in from file while ( fgets( aLine, LINE_LENGTH, fTiles) != NULL) { sscanf( aLine, "%c %d %d", &letter, &howManyLetters, &value); // store points per letter, assuming letters are upper case letterPoints[ letter - 'A'] = value; totalTiles += howManyLetters; for (i=currentLetterIndex; i< currentLetterIndex + howManyLette rs; i++) { letters[ i] = letter; } currentLetterIndex+= howManyLetters; } // Verify sum of individual letters equals total at top of file if ( totalTiles != NUMBER_OF_LETTERS) { // Sanity check printf(" *** Error, sum of number of letters: %d ", totalTiles) ; printf("in file %s ", lettersFileName); printf(" doesn't match NUMBER_OF_LETTERS: %d\n", NUMBER_OF_LETT ERS); printf(" Exiting program...\n"); exit( -1); } fclose( fTiles); // Seed random number generator used for getting tiles srand( 0); // initialize tiles for computer and human // first initialize to blanks so the "getTiles" function works properly createTileList( humanTiles); createTileList( computerTiles); // set end of string character setTileValue( *humanTiles, TILES_IN_HAND, '\0'); setTileValue( *computerTiles, TILES_IN_HAND, '\0'); getTiles( *humanTiles, letters, tilesRemaining); getTiles( *computerTiles, letters, tilesRemaining); } //-------------------------------------------------------------------------- void displayBoard( char board[ ][ BOARD_SIZE], // the board TileListStruct *humanTiles, // human's tiles TileListStruct *computerTiles, // computer's tiles int humanScore, // human's score int computerScore) // computer's score // Display the board, including the current scores { int i,j; // loop counters // display top header printf("\n "); for (i=0; i< BOARD_SIZE; i++) { printf("%d ", i + 1); } printf("\n"); // display 2-D board with row #'s on left for (i=0; i< BOARD_SIZE; i++) { printf("%c ", 'A'+i); for (j=0; j < BOARD_SIZE; j++) { printf("%c ", board[ i][ j]); } printf("\n"); } printf("\n"); // display human's and computer's tiles & scores printf(" Player Computer\n"); printf(" Tiles: "); for (i=0; i< TILES_IN_HAND; i++) { printf("%c ", getTileValue( humanTiles, i)); } printf(" "); for (i=0; i< TILES_IN_HAND; i++) { printf("%c ", getTileValue( computerTiles, i)); } printf("\n"); printf(" Scores: %d %d\n", humanScore, computer Score); } //-------------------------------------------------------------------------- int targetSquaresAreValid( char theWord[], // the word bei ng checked char board[][ BOARD_SIZE], // the board int row, // prop osed row for the word int column, // prop osed column for the word char direction, // 'A' for acro ss or 'D' for down char warningMessage[]) // Possibly stores a wa rning message // Verify that target squares do not already contain letters. { int rowOffset, columnOffset; // used to know how to change subscript s int wordLength; // length of theWord int i; // loop counters wordLength = strlen( theWord); // compute the length of the word // Initialize and set offsets rowOffset=columnOffset=0; if ( direction == 'A') { columnOffset = 1; } else if (direction == 'D') { rowOffset = 1; } else { // Sanity check sprintf( warningMessage, "*** Direction was %c, not 'A' or 'D'. ", direction); error( warningMessage, TERMINATE, DO_NOT_CLEAR_SCREEN); } // Now verify that target squares are on board and are blank for (i=0; i< wordLength; i++) { if ( board[ row][ column] != '.') { sprintf( warningMessage, "Destination not blank, retry. "); return FALSE; // square not blank (actually ' .'), invalid move } // Only one of the following will actually change value row = (row + rowOffset) % BOARD_SIZE; column = (column + columnOffset) % BOARD_SIZE; } // Passed all tests, so squares must be valid return TRUE; } //-------------------------------------------------------------------------- convertToString( TileListStruct *theTiles, // linked list of tiles char tilesAsString[]) // correspondin g string // Create a string that corresponds to the letters in the linked list { TileListStruct *currentP = theTiles; int i = 0; while (currentP != NULL) { tilesAsString[ i++] = currentP->letter; currentP = currentP->nextP; } tilesAsString[ i] = '\0'; // terminate string } //-------------------------------------------------------------------------- int validHumanMove( int row, // board row for word int column, // board column for word char direction, // direction 'D' or 'A' char theWord[], // the actual word TileListStruct * playerTiles, // player's til es char board[][ BOARD_SIZE], // the board char dictionary[][ WORDLENGTH+1], // dict ionary int numberOfDictionaryWords, // # words in d ictionary int tilesRemaining) // # of tiles remaining to use /* Verify that the word is found in the dictionary and destination squares are valid, and human has those tiles to play. This verifies the human' s moves. */ { char errorLine[ LINE_LENGTH]; // used to display error messages char userTilesCopy[ LINE_LENGTH]; // copy of tiles in user's hand . // This is used to verify tiles in proposed // word are actually in user's hand. int wordLength; // length of proposed w ord int i,j; // loop counter s int startPosition; /* position to start checking a words letters to verify the y are in user's hand. This is 0 for the first wo rd, but 1 for subsequent words since the first lette r for those words should already be on the board and n ot in the users hand. */ // if 'H' for help was selected (and there was no valid column value sp ecified) if ( ( row == 'H') && (column == 0)) { return FALSE; } // if 'P' for pass was selected (and there was no valid column value sp ecified) if ( ( row == 'P') && (column == 0)) { return FALSE; } // if 'R' for refresh was selected (and there was no valid column value specified) if ( ( row == 'R') && (column == 0)) { return FALSE; } if ( ! foundInDictionary( theWord, dictionary, numberOfDictionaryWords) ) { sprintf( errorLine, "Word not found in dictionary, retry."); error( errorLine, WARNING, CLEAR_SCREEN); return FALSE; } // Make sure player has those tiles to play // wordLength = strlen( theWord); // compute the length of proposed word // computer starting position to start checking for letter tiles if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2)) ) { // Is NOT the first move; first character will not be checked startPosition = 1; // skip checking the first lett er } else { // IS the first move; first character will be checked startPosition = 0; // check all letters } // ensure player has the tiles necessary for the word convertToString( playerTiles, userTilesCopy); // for each letter in the proposed word... for (i=startPosition; i< wordLength; i++) { // clear each letter tile to be played from copy of user's hand for (j=0; j< TILES_IN_HAND; j++) { if ( theWord[ i] == userTilesCopy[ j]) { userTilesCopy[ j] = ' '; // blank out th at letter break; // Found it. Go to next letter in outer loop } } if( j == TILES_IN_HAND) { // This should only happen if human user is trying to p lay tiles // that are not in the human's hand sprintf( errorLine, "You are trying to play a letter no t in your hand."); error( errorLine, WARNING, CLEAR_SCREEN); return FALSE; } } /* Ensure target squares are valid. If it is the first move, the word can start anywhere. If it is not the first move, the first letter of the proposed word must also already be found on the board at the proposed playing position. */ // To find out if it is the first move we must // compare against the formula below because the initialize() functio n // has already given each player tiles to start out if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2)) ) { // Is NOT the first move // first verify that first letter of word to play is the same // as the letter stored on the board at the playing position if ( board[ row][ column] != theWord[ 0]) { // First letter doesn't match, word can't be played the re sprintf (errorLine,"First letter doesn't match. Can't d o that."); error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); return FALSE; } /* We now know that the first letter matches. Skip the first le tter of the word to check as well as the first chara cter on the board when verifying that target squares are va lid. */ if ( direction == 'A') { // word is proposed to go across if ( ! targetSquaresAreValid( theWord + 1, board, row, c olumn+1, direction, errorLine ) ) { error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN) ; return FALSE; } } else if ( direction == 'D') { // word is proposed to go down if ( ! targetSquaresAreValid( theWord + 1, board, row+1 , c olumn, direction, errorLine ) ) { error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN) ; return FALSE; } } else { // Sanity check sprintf( errorLine, "%s", "Invalid direction for word." ); error( errorLine, TERMINATE, CLEAR_SCREEN); } } // end if (tilesRemaining... else { // IS the first move if ( ! targetSquaresAreValid( theWord, board, row, colum n, direction, errorLine ) ) { // display the error which was found in above function call error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN); // target squares were not valid return FALSE; } } // all tests passed if we got here, so human move is valid return TRUE; } //-------------------------------------------------------------------------- int pointsValue( char theWord[], // Current word being checked int letterPoints[]) // points per letter ar ray /* compute the number of points theWord is worth. The point values are passed in the letterPoints array, and those values originally come from the letters input file. */ { int i; int sum = 0; int wordLength; wordLength = strlen( theWord); // Compute the length of the wo rd in question for (i=0; i< wordLength; i++) { sum += letterPoints[ theWord[ i] - 'A']; } return sum; // Return the computed number of points this wo rd is worth } //-------------------------------------------------------------------------- void makeMove( int row, // boar d row for word int column, // board column for word char direction, // direction 'D' or 'A' char theWord[], // the actual word TileListStruct * playerTiles, // player's til es char board[][ BOARD_SIZE], // the board int tilesRemaining, // overall tiles remaining int letterPoints[], // points per letter array int *score) // score to be updated /* Move has been verified, so place theWord on board at row,column using direction to specify 'A' for across or 'D' for down. */ { int rowOffset, columnOffset; // used to know how to change subscript s int wordLength; // length of theWord int i, j; // loop counter s int startPosition; /* position to start checking a words letters to verify the y are in user's hand. This is 0 for the first wo rd, but 1 for subsequent words since the first lette r for those words should already be on the board and n ot in the users hand. */ wordLength = strlen( theWord); // compute the length of the word // update score, where the points per character is taken from letterPoi nts array *score += pointsValue( theWord, letterPoints); // Initialize and set offsets rowOffset=columnOffset=0; if ( direction == 'A') { columnOffset = 1; } else if (direction == 'D') { rowOffset = 1; } else { // Sanity check printf("*** Direction was %c, not 'A' or 'D'. Exiting..\n", dir ection); fflush( stdout); exit( -1); } // Now store word at that location. First figure out whether the first // letter should be taken into account or not. // // Find computer starting position to start checking for letter tiles if ( tilesRemaining < (NUMBER_OF_LETTERS - (TILES_IN_HAND*2)) ) { // Is NOT the first move; first character will not be checked startPosition = 1; // skip checking the first lett er } else { // IS the first move; first character will be checked startPosition = 0; // check all letters } // Actually store the word, tile by tile for (i=0; i< wordLength; i++) { board[ row][ column] = theWord[ i]; // Only one of the following will actually change value row = (row + rowOffset) % BOARD_SIZE; column = (column + columnOffset) % BOARD_SIZE; } // clear those tiles to make space for new ones for (i=startPosition; i< wordLength; i++) { // clear each letter tile played from user's hand for (j=0; j< TILES_IN_HAND; j++) { if ( theWord[ i] == getTileValue( playerTiles, j)) { setTileValue( playerTiles, j, ' '); // blank it out, it's been used break; // go to next letter in outer loop } } if( j == TILES_IN_HAND) { // j == TILES_IN_HAND should only be true when no match was // found in the above loop // Sanity check. If letters matched, should never get here printf("*** Letters played not found in users hand.\n") ; printf("Error occured in word %s looking for letter %c\ n", theWord, theWord[ i]); printf("Exiting program...\n"); fflush(stdout); exit ( -1); } } } //-------------------------------------------------------------------------- void humanMove( char board[ ][ BOARD_SIZE], // the board int *notDone, // stor es when user wants to exit TileListStruct *humanTiles, // human's tiles TileListStruct *computerTiles, // comp uter's tiles char dictionary[][ WORDLENGTH + 1], // dict ionary int numberOfDictionaryWords, // # words in d ictionary char letters[], // tile s remaining int *tilesRemaining, // # of tiles remaining int letterPoints[], // poin ts per letter array int *humanScore, // huma n's score int computerScore) // comp uter's score // Prompt for and make the human's move { char userInput[ 80]; // temporarily store input line int i; // loop counter char row; // board row for word to be put int column; // board column for word to be put char direction; // direction: 'A' for across, or 'D' fo r down char theWord[ LINE_LENGTH]; // stores the word to be put on the boa rd char errorLine[ LINE_LENGTH]; // used to display error messages do { printf("\n"); printf("Enter row, column, move direction (a or d), and word.\n "); printf("You may also enter 'P' to pass, 'X' to exit, 'R' to ref resh, or 'H' for help.\n"); printf("Your command --> "); // Get an input line fgets(userInput, LINE_LENGTH, stdin); // ensure it is upper case for (i=0; i< strlen( userInput); i++) { if ( islower( userInput[ i])) { userInput[ i] = toupper( userInput[ i]); } } // Parse input line column = 0; // this is needed to differentiate betw een help & row 'H' sscanf( userInput, "%c%d %c %s", &row, &column, &direction, the Word); // prematurely exit if 'x' was entered if (row == 'X') { *notDone = FALSE; return; } // If 'H' was entered for help, but no column info was entered if ( (row == 'H') && ( column == 0) ) { help( letterPoints); // Display help informa tion displayBoard( board, humanTiles, computerTiles, *humanScore, computerScore); continue; } // If 'R' was entered for refresh, but no column info was enter ed if ( (row == 'R') && ( column == 0) ) { displayBoard( board, humanTiles, computerTiles, *humanScore, computerScore); continue; } if (row == 'P') { // 'P' to pass this turn was chosen. Return from this function. if ( *tilesRemaining == (NUMBER_OF_LETTERS - (TILES_IN_ HAND*2)) ) { // IS the first move; disallow passing on this turn. Human // must enter first word, otherwise computer ha s no letters // with which to start its words. sprintf( errorLine, "%s", "Can't pass on your f irst turn."); error( errorLine, WARNING, DO_NOT_CLEAR_SCREEN) ; continue; } else { return; } } row -= 'A'; // convert lower case character row val ues to numbers column -= 1; // Fix index, since column #'s start at 1, not 0 } while ( ! validHumanMove( row, column, direction,theWord, humanTiles, board, dictiona ry, numberOfDictionaryWords, *tilesRemaining ) ); // Move must have been valid to get here makeMove( row, column, direction, theWord, humanTiles, board, *tilesRemaining, letterPoints, humanScore); getTiles( humanTiles, letters, tilesRemaining); } //-------------------------------------------------------------------------- void swap( char theString[], int i, int j) { int temp = theString[ i]; theString[ i] = theString[ j]; theString[ j] = temp; } //-------------------------------------------------------------------------- int thisIsBestWord( char answer[], // Current word being checked char bestWord[], // Best word fo und so far int letterPoints[], // Points per l etter int currentRow, // Current star ting position row int currentColumn, // Current star ting position column char *theDirection, // Direction fo r best word char board[ ][ BOARD_SIZE]) // the board. /* See if this is the best word found so far. For a word to be the best, it must have a higher or equal point score to any other word, and the w ord must fit into that position on the board. In order to even call this function we know that the first character of the word matched a startin g position on the board. */ { char errorMessage[ LINE_LENGTH] = {" "}; // for error messages // Check point score if ( pointsValue( bestWord, letterPoints) >= pointsValue( answer, lette rPoints) ) { // length is no longer than current best word, so simply return return FALSE; } // If there is not a valid move across or a move down, return // // find out the direction of the valid move *theDirection = ' '; /* set theDirection if a valid move is found. Increment answer to start checking for valid squares *after* the first character, which is the same character as the first character stored on the board. For the same reason also increment either row or column. */ // check for valid move going Across ('A') if ( targetSquaresAreValid( answer+1, board, currentRow, currentColumn+1 ,'A', errorMessage) ) { *theDirection = 'A'; return TRUE; } // check for valid move going Down ('D') if ( targetSquaresAreValid( answer+1, board, currentRow+1, currentColumn,' D', errorMessage) ) { *theDirection = 'D'; return TRUE; } // Target squares not valid. Error message should have been generated return FALSE; } //-------------------------------------------------------------------------- void permute( char theString[], // current string char answer[], // constructed using 1s t. char of string // a t each recursive level int position, // spot in answer where we're currently // s toring the next character int maxDepth, // used to limit recurs ive depths and // g enerate answers of different lengths char dictionary[][ WORDLENGTH+1], // dictionary int numberOfDictionaryWords, // # words in dictionar y int letterPoints[], // points per l etter char bestWord[], // stor es best word found int *bestRow, // Stor e row for bestWord int *bestColumn, // Stor e column for bestWord char *bestDirection, // Direction fo r best word char board[ ][ BOARD_SIZE]) // the board. Used to pass // along to verify if a // found word is the best. /* Generate all permutations of a word, which are then looked up in the dictionary and verified as to position on the board. The word with the highest point score is returned in 'bestWord' */ { int length; // stores string length of permutation being checked int i; // loop counter int row, column; // row & column indices for traversing board char theDirection; // Used to store direction if a new best word i s found char wordToLookup[ LINE_LENGTH] = {" "}; length = strlen( theString); if (length == maxDepth) { // construct word to lookup by appending permutation to a chara cter alreay // on the board. To do this, go through each character on boar d and make // it the first character of the word to check. for (row=0; row< BOARD_SIZE; row++) { for (column=0; column< BOARD_SIZE; column++) { // make sure there is a character there if ( board[ row][ column] == '.') { // no character there continue; } // Construct the word to lookup wordToLookup[ 0] = board[ row][ column]; // store first character for word // variable "answer" has blanks on the end of i t, so we don't want to copy those // Find the number of chacters until we get to the first blank. for (i=0; (answer[i]!= ' ') && (answer[i]!= '\0 '); i++) { wordToLookup[ i+1] = answer[ i]; // offset destination 'cause of link letter } wordToLookup[ i + 1] = '\0'; // Properly ter minate destination string if ( foundInDictionary( wordToLookup, dictionar y, numberOfDictionaryWords)) { // See if we've found a new best word. if ( thisIsBestWord( wordToLookup, best Word, letterPoints, row, column, &theDi rection, board) ) { strcpy( bestWord, wordToLookup) ; // store new best word *bestRow = row; // store best row & column *bestColumn = column; *bestDirection = theDirection; // store direction for best word } } } // end for (column... } // end for (row... return; } // end if (length == maxDepth) // For each starting character for (i=0; i< length; i++) { swap( theString, 0, i); // swap items answer[ position] = theString[ 0]; // recursive call without first letter permute( &(theString[ 1]), answer, position+1, maxDepth, dictionary, numberOfDictionaryWords, letterPoi nts, bestWord, bestRow, bestColumn, bestDirection, board); swap( theString, 0, i); // swap items back to original position } } //-------------------------------------------------------------------------- void computerMove( char board[ ][ BOARD_SIZE], // the board TileListStruct *computerTiles, // comp uter's tiles char dictionary[][ WORDLENGTH + 1], // dictionary int numberOfDictionaryWords, // # wo rds in dictionary char letters[], // tiles remaining int letterPoints[], // points per letter array int *tilesRemaining, // # of tiles remaining int *computerScore) // computer's score // Make the computer's move { char permutedWord[ TILES_IN_HAND + 1]; // permuted word, + 1 for NULL int i; // loop counters int maxDepth; // used for generating different size s trings char bestWord[ TILES_IN_HAND + 2] = {""}; // best word found int bestRow, bestColumn; // location for best word char bestDirection; // direction 'A' or 'D' for bes t word char computerTilesAsString[ TILES_IN_HAND + 1]; // By varying the maximum recursive call depth, we create strings of // different lengths. I.e. when max depth is 0, recursive calls are ma de // until all characters in the string are exhausted. When MAX-1 is the // max. depth, then recursion ends right away giving strings of length // one only. convertToString( computerTiles, computerTilesAsString); for ( maxDepth = 0; maxDepth < TILES_IN_HAND + 1; maxDepth++) { // blank out initial permuted word for (i=0; i< TILES_IN_HAND; i++) { permutedWord[ i] = ' '; } permutedWord[ TILES_IN_HAND] = '\0'; // mark end of string // Generate permutations, look them up in dictionary, // and get "best" word that fits into board permute( computerTilesAsString, permutedWord, 0, maxDepth, dictionary, numberOfDictionaryWords, letterPoi nts, bestWord, &bestRow, &bestColumn, &bestDirectio n, board); } printf("\nBest computer word found was: %s, ", bestWord); printf("played %s ", (bestDirection == 'A') ? "across" : "down"); printf("starting at %c%d", bestRow+'A', bestColumn+1); // Move must have been valid to get here makeMove( bestRow, bestColumn, bestDirection, bestWord, computerTiles, board, *tilesRemaining, letterPoints, comp uterScore); getTiles( computerTiles, letters, tilesRemaining); } //-------------------------------------------------------------------------- void display_usage() // Display program usage message { printf("\n"); printf(" USAGE: \n"); printf(" links -l let -d dct \n"); printf(" \n"); printf(" where the parameters are: \n"); printf(" -l let = the letters file name \n"); printf(" -d dct = the dictionary file name \n"); printf(" \n" ); printf(" e.g. links -l letters.txt -d /usr/dict/words \n\n"); exit( 0); } //-------------------------------------------------------------------------- void get_arguments( int argc, /* number of args, including prog. name */ char *argv[], /* array of strings */ char **dictionaryFileName, /* dictionary f ile name command line parameter */ char **lettersFileName) /* lett ers file name command line parameter */ // Retrieve & store command line arguments { char errorMessage[ LINE_LENGTH]; /* Used to display error messag es */ if (argc == 1) /* No arguments at all */ display_usage(); else { while ( (argc -= 2) > 0) { /* while there is another p air of strings */ if (argv[ 1][ 0] != '-') /* Invalid syntax, no " -" before option */ display_usage(); switch (argv[ 1][ 1]) { /* handle options */ case 'l': *lettersFileName = argv[ 2]; break; case 'd': *dictionaryFileName = argv[ 2]; break; default: sprintf( errorMessage, "%s: %s" , "Incorrect parameter", &argv[ 1][ 1]); error( errorMessage, TERMINATE, DO_NOT_CLEAR_SCREEN); } /* end switch */ argv += 2; /* advance to next pair of command line options */ } /* while end*/ } /* else end*/ } //-------------------------------------------------------------------------- int main( int argc, // argument counter char *argv[]) // arguments themselves, stored in a 2- D array { // Set all file names here in one place to make it easier to change // later if needed. Pass the names to functions where nee ded. char *dictionaryFileName = NULL; // dictionary file name from command line char *lettersFileName = NULL; // scrabble letters fil e name from command line char board[ BOARD_SIZE][ BOARD_SIZE]; // the scrabble board int notDone = TRUE; // Flag to indi cate when we're done char letters[ NUMBER_OF_LETTERS]; // Stores scrabble lett er tiles int letterPoints[ LETTERS_IN_ALPHABET]; // stores points per le tter TileListStruct * computerTiles = NULL; // Linked list of computer Tiles // char computerTiles[ TILES_IN_HAND + 2]; // computer's letters // Extra space needed to add in a character from the bo ard TileListStruct * humanTiles = NULL; // Link ed list of human's tiles // char humanTiles[ TILES_IN_HAND + 2]; // human's letters int tilesRemaining = NUMBER_OF_LETTERS; // tiles left for anyon e to use int humanScore = 0; // huma n score int computerScore = 0; // computer sco re // Get dictionary and letters file names from command line args get_arguments( argc, argv, &dictionaryFileName, &lettersFileName); // Read dictionary words into dictionary array getDictionaryWords( dictionaryFileName); // Initialize board to '.', initialize letters array to the letters // from file, Give human and computer their starting lette rs initialize( board, letters, letterPoints, lettersFileName, &computerTiles, &humanTiles, &tilesRemaining); // display help information for first time through help( letterPoints); // main loop do { // Display board displayBoard( board, humanTiles, computerTiles, humanScore, com puterScore); // Prompt for input and make human's move, get new tiles humanMove( board, ¬Done, humanTiles, computerTiles, Diction ary, NumberOfDictionaryWords, letters, &tilesRema ining, letterPoints, &humanScore, computerScore); if ( notDone) { // if human has not indicated being done yet // Determine computers move, get new tiles computerMove( board, computerTiles, Dictionary, NumberO fDictionaryWords, letters, letterPoints, &tiles Remaining, &computerScore); } } while ( notDone); printf("Thanks for playing.\n"); }