Prog 5 Scramble

Updates shown in blue. Even more updates shown in green. Even even more shown in ? color.

Write a program that plays a game similar to Scrabble. You play against the computer and have to create words that are played on a 10 by 10 playing board. Each player receives 7 letter tiles, and as those tiles are played they are replenished from a set of 98 original tiles, until there are no more tiles left. The first word is placed anywhere on the board by the human player, and subsequent to that all words must be connected by only the first letter of the word to some letter already on the board. E

ach letter is worth only 1 point.

Playing the game looks like the following:

Welcome to the game of scramble, where you try to build English words on a board. The board itself is two dimensional, with rows marked by letters, and columns marked by numbers. A combination of row and column uniquely identify each square.

Each word you create (after the first one) must start with an existing letter on the board, and the subsequent letters must be played into blank squares. Words must be created out of the tiles you have in your "hand".

When a new word has letters adjacent to existing letters, you do not need to create valid words with those adjacent letters. One point is given per letter played. The winner is the player with the most points.

For each move you need to enter a row, a column, a move direction (a or d), and the word to be played at that spot. You may also enter 'X' to exit or 'H' for help. Input can be either upper or lower case.

E.g. "E3 d rap" puts the word "rap" starting at row E, column 3, going downwards.

Alternatively "E3 a rap" would put the word "rap" starting at row E, column 3, going across.

Please press the return key to continue...

 1 2 3 4 5 6 7 8 9 10  A . . . . . . . . . .  B . . . . . . . . . .  C . . . . . . . . . .  D . . . . . . . . . .  E . . . . . . . . . .  F . . . . . . . . . .  G . . . . . . . . . .  H . . . . . . . . . .  I . . . . . . . . . .  J . . . . . . . . . .                 Player             Computer     Tiles: A A V P P R R      I Q T C A R N    Scores:       0                  0    Enter row, column, move direction (a or d), and word.  You may also enter 'P' to pass, 'X' to exit or 'H' for help. --> b2 d rap    Best computer word found was: ARCTAN, played across starting at C2    1 2 3 4 5 6 7 8 9 10  A . . . . . . . . . .  B . R . . . . . . . .  C . A R C T A N . . .  D . P . . . . . . . .  E . . . . . . . . . .  F . . . . . . . . . .  G . . . . . . . . . .  H . . . . . . . . . .  I . . . . . . . . . .  J . . . . . . . . . .                 Player             Computer     Tiles: E A V A P E R      I Q R E E D N    Scores:       3                  6   

In the example shown above the human player chooses the word "rap" as the first move, starting at b2 and moving downwards. The computer then generates all permutations of it’s seven letter tiles (I Q T C A R N), prepended by each letter on the board. Each of these permutations is looked up in the dictionary, and the best (longest) word is remembered. In this case the best computer generated word was "arctan", which connects in to the "a" in "rap." Note that all words (after the first) must connect by only the first letter to a letter already on the board.

One point is given for each letter in a word that is played. Note that although the computer only puts down 5 of the 6 letters in "arctan," it gets six points, since the connecting "a" from "rap" also counts. Note what the board looks like a few turns later, after the human chooses

C5 d taper

and the computer responds with

B2 a render

1 2 3 4 5 6 7 8 9 10  A . . . . . . . . ..  B . R E N D E R . . .  C . A R C T A N . . .  D . P . . A . . . . .  E . . . . P . . . . .  F . . . . E . . . . .  G . . . . R . . . . .  H . . . . . . . . . .  I . . . . . . . . . .  J . . . . . . . . . . 

When the computer played "taper" going across starting ab b3, its letters end up adjacent to the letters in "arctan." The resulting adjacent letters do not need to form new words, as we see here.  Similarly the last letter of a word can be the starting letter of a new word, and the resulting longer word formed by the two individual words together need not be in the dictionary.  Thus in the diagram above the word "PEN" could be placed starting at D2 going downwards, but "RAPPEN" need not be in the dictionary.

Note that due to the use of the dictionary file as-is, it is not possible to type in plurals for a word unless they are already in the dictionary. There are also some abbreviations and names in the dictionary file that you would not necessarily expect when playing scrabble.

Recommendations

• 1. Write your program modularly, one step at a time, testing each section before going on to the next. This is a non-trivial program, so plan accordingly. Due to the length, you should definitely indent and comment as you go, and break things up using functions.

  2. For user-defined constant values, use #defines up at the top of your program, e.g.

  3.      #define BOARD_SIZE 10

  4. Then use these throughout your program. Should you need to change these values, you can then change them in only one place.

  5. The main part of your program should be very brief, something like a function call to do initializations, then a main loop consisting of the human’s turn, the computer’s turn, and a check to see if you are at the end of the game yet.

  6. Figure out how to use a debugger. This could save you a lot of time.

  7. Liberally do "sanity checks" in your code. Then as you change something and it has an undesired side-effect, you will already have "built-in" a mechanism to help guide you to finding the problem.

Notes:

1. To run a version of this program, login to your CS account on oscar/bert/ernie or grover, change directories into the directory where the executable code is, and run it from there.  The commands to do this are:

2.     cd ~reed/141/scramble

3.   ./scramble

   1. You may assume "perfect input" and do not need to do error checking of user input. In other words, you can assume that the input line typed by the user is correctly formatted.

   2. You do, however, need to do error checking regarding the content of the input the user gives. In other words, you must give an error message if the proposed word goes off the end of the board, overlaps squares that are currently occupied, or are not found in the dictionary. Take a look at my on-line version of the program for examples of what I expect.

   3. You must use 0 as the seed for your random number generator used in picking letter tiles for each player. Please use "rand" rather than "random" for your random number generator to make it easier to grade your programs.

   4. Your dictionary and your board should both be implemented as a two-dimensional arrays.

4. Your program should use this file for the dictionary words. The name for this file should again be hard-coded into your program as: dictionary.txt

• 1. See this code for an example of how to read in dictionary words.  Alternatively see the sample program on the strings page of the course notes.  Note that the provided dictionary has 23,732 words of length 8, after words with punctuation have been eliminated

  2. To eliminate a word with punctuation when reading in the dictionary you can use the  isalpha( word[ i])  to check the ith character of the word.  To use this you need:    #include <ctype.h>

5. Your program must also read in the number of each tile from a file called letters.txt    Please use the version and format that I’ve given you in this file. Note that you don't need to store all the information in the file.  It is a good idea to read the number on the first line, then ignore the rest of that line (read it into a string which then gets ignored.)  The second line should be read and discarded.  You can use the C fgets function to read an entire line into a string as follows:

• 1. // declarations

  2. FILE *fTiles;

  3. char inputLine[ 81];

  4.  

  5. // Open the input file

  6. fTiles = fopen( "letters.txt", "r");

  7.  

  8. // read an entire line at a time from the input file into a string

  9. fgets( inputLine, LINE_LENGTH, fTiles);                // read in an entire line

  10.  

  11. // use sscanf to scan from inputLine string rather than from the input

  12. sscanf( inputLine, "%d", &totalTiles);        // read number from input line

  13.  

  14. // use fgets again to read the next line, which you will simply ignore…

6. In fact you only need to use an array of 26 integers to store the counts for each letter.  After that is done I recommend you make a large array of char, of size 98 in this case, and populate it with the actual characters.  Then you can simply pick one when it is time to choose a random tile. Only replace the tiles that are played on the board.

7. You must do a binary search when looking up words in the dictionary. Otherwise you will find that it may take a long time between moves for the computer to generate and look up all permutations of possible words.  Convert both your input as well as the dictionary entries into the same case (either upper or lower), otherwise binary search will be thrown off.

8. Look at permute.c for an example on how to generate permutations of a word.

9. Differentiating between user input of 'H' for Help and user input of a word at row 'H'

10. Again read in an entire line of user input, this time from stdin rather than from a file:

11.            fgets(userInput, LINE_LENGTH, stdin);

• 1. Then check the userInput string to see if the first character of the userInput is 'H'.  If it is and there is no other characters, then you know 'H' for help was entered.  Similarly handle 'x' for exit in this way.

  2. Extra hint: Note that sscanf returns the number of values successfully read.  Thus you can use it to read all the input (row, column, direction, word) but if the return value is 1, then you know that input was given for only the first variable (row).

  3. 'H' for help should again display the instructions on what the user should provide as input.

12. Do not turn in a copy of the dictionary file or the letters file along with your program.

13. Turn in only your scramble.c file into Blackboard.

Approximation of Grading Criteria (out of 55 points for execution)

1. ( 0 points) Display instructions and board

2. (25 points) Read in dictionary and letters file.  Handle user input for a word. Verify word is valid and place on board.

3. (15 points) Ensure that words placed overlap on only the 1st character.

4. (10 points) Computer chooses highest scoring word and places it correctly on board

5. ( 5 points) Menu options for 'X' and 'H' and 'P' handled correctly.

Keep in mind for the following assignment (Program #6):

(You can totally ignore this section for now if you want to.)

The next (and last) program will likely look the same as this one when executing, but have differences "under the hood." It will probably include:

• 1. Handling command-line parameters (using the argv and argc arguments to main() ). I’ll be giving you sample code for this.

  2. The board will be implemented using linked-lists, and will wrap around at the sides and top.

  3. Dictionary words will not be read into a two-dimensional array, but rather will have space dynamically allocated for each word as they are read in. This way there will be no wasted space for large array elements with small words in them.  Similarly the same will be true for the letters.txt file.

  4. Scoring using values for each letter, rather than simply 1 point per letter.