Summary of task (COMPLETE IN C LANGUAGE): The game of Boggle comes with 16 dice,
ID: 3812899 • Letter: S
Question
Summary of task (COMPLETE IN C LANGUAGE):
The game of Boggle comes with 16 dice, each with six separate letters on each side. The Boggle “board” is a 4 x 4 grid of these dice. At the beginning of the game, the dice are randomly shaken and placed on the board, so theoretically, the dice can land in any order in the 16 squares, and each of the 6 sides of each die are equally likely to be face up. Once the dice all land, the playing board is set with one letter in each entry of the grid. Here is a valid Boggle playing grid: c a s e m o p i s t r e n a p d Once the grid is fixed, each player has a set time (around 3 minutes) to come up with as many words that can be formed by connecting letters in the grid. To connect letters in the grid, you must pick a starting letter (for example, the ‘a’ in the first row), and then pick each subsequent letter adjacent to the previous letter. To be adjacent, a square must be either above, below, to the left, to the right, or to a diagonal to the previous square. No square can be chosen twice. Thus, “mam” is not permissible, because it uses the ‘m’ in row 2 column 1 twice. But, “aorta” DOES count because we can go from the ‘a’ in row 1 column 2 to the ‘o’ in row 2 column 2. Then we can go to the ‘r’ in row 3 column 3, followed by the ‘t’ in row 3 column 2, finishing with the ‘a’ in row 4, column 2.
Simply put, a valid configuration in Boggle is a sequence of row, column coordinates such that no two sets of coordinates are equal, and each adjacent set of coordinates differ in row and column by no more than 1. (“aorta” has the sequence (1, 2), (2, 2), (3,3), (3, 2), and (4,2).) If a valid sequence corresponds to an English word, then you can play the word in Boggle.
After the three minutes is up, each player reveals the words they formed. A player receives points only for her unique words, words that no other player listed. In particular, a player receives 1 point for 3 or 4 letter words, 2 points for 5 letter words, 3 points for 6 letter words, 5 points for 7 letter words, and 11 points for words with 8 or more letters for her unique words. (Note: This is irrelevant to solving the problem at hand.)
Problem Solving Restrictions:
Dictionary Storage - Your program must check possible words and possible word prefixes against a dictionary. The dictionary must be stored in a trie. Here is the structure that will store one node within the trie:
typedef struct trie{
int isWord;
struct trie* nextLetter[26];
} trie;
To form this dictionary, dynamically allocate the root node in main, that is a single trie. This node will correspond to the empty string. In this node, set isWord to 0 (false), and set all 26 pointers in nextLetter to NULL.
Once this is done, your dictionary must support three functions:
1) Insert a word
2) Check if a word is stored in the dictionary
3) Check if a set of letters is the prefix to any word in the dictionary
Note: It also makes sense to have a function that frees all the memory in the dictionary.
To insert a word, you need to start at the root of the tree and find the pointers that correspond to each letter in the word. For example, if we insert “cat”, we first want to find the pointer in index 2 (since ‘c’ – ‘a’ is 2) of nextLetter from the root and go to the node it’s pointing to. If no node exists, we should create it. From that new node, we want to go to the pointer in index 0 (since ‘a’ – ‘a’ is 0) of nextLetter. If no node is there, we should create it again. Finally, from that node, we should take the pointer in index 19 (since ‘t’ – ‘a’ = 19) of nextLetter. In this last node, we must store isWord = 1, to indicate that “cat” is a valid word.
Basically, since we only create nodes when valid words are inserted, the tree won’t be nearly as big as it could be (2610 , for example, if we considered all strings of length 10.) If a word doesn’t exist, then no path will be created to the corresponding node, OR a 0 will be stored in that node’s isWord entry. (If the latter occurs, this means that some other word has these letters as a prefix.)
Note: Only add words with lengths in between 3 and 16, inclusive to the dictionary.
Searching Using Backtracking:
To search for all possible words in the boggle grid, we’ll start 16 searches, from all the possible starting points in the grid. For each search we’ll do as follows:
Recursively try all adjacent squares to the last square in the “prefix” we are trying as the next letter to add on. In this picture, if we are looking for words that start with c:
we want to try everything that starts with “ca”, followed by everything that starts with “co”, followed by everything that starts with “cm”. (Note: We can try these options in any order. I just randomly picked clockwise for this example. Recall the DX, DY array from assignment #2. That will come in handy here.) If what we are trying is a word, we print it. Then we continue. In general, we can think of our function as taking in the following information:
1) The prefix we are trying
2) Which board squares have already been used
3) Our current position on the board
Given these pieces of information (and the board and dictionary), the void recursive function we create will print the following: all the words that start with that prefix (with the last square as identified by the current position) that are valid words in the game.
For example, calling the function with the prefix “cor”, designating that (1,1), (2,2) and (3,3) have been used and that (3,3) is our current position, the function should print out the following words (using the dictionary posted online with 150315 words):
cor, corps, corpse, core, cored, cord.
Thus, what needs to be done is print “cor”, followed by recursively solving the problem for “corp”, “cori”, “core”, “cord”, “corp”, “cora” and “cort”. Note that we skipped “corr” and “coro” because both of the squares with the ‘r’ and ‘o’ had already been used.
If a function call is made on a prefix that doesn’t exist (in this grid, an example of such a prefix is “rp”, since no words start with “rp”), then we can immediately return and stop the function.
Note: Since we are trying all possible board configurations, it’s possible that the same word will print out twice because it appears in two different ways in the same board. In the sample posted online, notice that “cake” and “face” both appear twice in the second game. Viewing the game board verifies that there are TWO different ways to form both words. (This is because there are two different e’s adjacent to both ‘k’ and ‘c’ on the board.) There is no need to avoid these printing. If you would like store previously printed words globally and only print one copy of each word, feel free to do so.
Input File Specification (dictionary.txt) :
The first line of this input file will have a single positive integer, n, representing the number of words in the dictionary. The following n lines will contain one word each, all in lowercase letters, in alphabetical order.
Input Specification (standard input):
The input has a single positive integer, n, on its first line, specifying the number of games of Boggle to play. Each of the games will follow. For each game, there will be four strings of four lowercase letters each on four lines. Each game will be separated with a blank line for clarity’s sake. (This shouldn’t change how you read in the game boards using scanf.)
Output Specification:
For each input case, print out a header with the following format:
Words for Game #g:
where g represents the number of the game, starting with 1.
Then, starting on the following line, list each possible word that can be formed (according to the dictionary), with one word per line. The words can be listed in any order.
Separate the output for each case with TWO blank lines.
Note about output: The output for each test case is not unique, since you might print out all the correct words in a different order. We will use a checking program to determine the correctness of your output. The checker will judge your output as correct as long as each unique word that exists in the grid is outputted at least once and no invalid string (one that isn't in the dictionary or isn't in the grid) is outputted at all. Any valid string may be outputted more than once and this will not affect the correctness of your program.
Sample input:
Sample output:
Here's the framework for this program:
Here's the small dictionary for testing:
Lets see what you're made of!
c a s e m o p i s t r e n a p dExplanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 4
#define DIRECTION 8
#define MAX_LENGTH 16
// possible movements
const int DX[] = {-1,-1,-1,0,0,1,1,1};
const int DY[] = {-1,0,1,-1,1,-1,0,1};
struct trie {
int isWord;
struct trie* nextLetter[26]; // use array so don't have to worry about memory allocation
};
struct trie* loadDictionary();
struct trie* insert(struct trie* root, char word[], int index);
int inbounds(int x, int y);
int isWord(char word[], struct trie* dictionary);
int isPrefix(char word[], struct trie* dictionary);
void result(char board[][SIZE], struct trie* dictionary, int round);
void solve(char prefix[], int used[][SIZE], int curX, int curY, char board[][SIZE], struct trie* dictionary);
void freetree(struct trie* root);
int main() {
struct trie* dictionary = loadDictionary();
int numRounds, i;
scanf("%d", &numRounds);
for (i = 0; i < numRounds; i++) {
char board[SIZE][SIZE];
int j, k;
char line[SIZE + 1];
for (j = 0; j < SIZE; j++) {
scanf("%s", line); // read in line
for(k = 0; k < SIZE; k++) {
board[j][k] = line[k]; // copy each character read in into boggle board
}
}
result(board, dictionary, i + 1); // find all possible words
}
freetree(dictionary); // return borrowed memory
return 0;
}
// return trie holding all the words found in
// dictionary.txt that are within bounds of boggle
// length words to shorten time between inserting
// and searching through words that can't be used
struct trie* loadDictionary() {
FILE* dictFile = fopen("dictionary.txt", "r");
struct trie* dictionary = malloc(sizeof(struct trie)); // Set up the dictionary structure.
int numWords;
int i;
for (i = 0; i < 26; i++) {
dictionary->nextLetter[i] = NULL; // set each child to null
}
dictionary->isWord = 0; // set default to not being a word
fscanf(dictFile, "%d", &numWords);
for (i = 0; i < numWords; i++) {
char word[100];
fscanf(dictFile, "%s", word);
int wordLength = strlen(word); // get word length
if (3 <= wordLength && wordLength <= MAX_LENGTH)
dictionary->nextLetter[(int)(word[0] - 'a')] = insert(dictionary->nextLetter[(int)(word[0] - 'a')], word, 1);
}
fclose(dictFile); // close file
return dictionary;
}
// insert one letter at a time until reach end of
// word read from dictionary.txt, then flag as a word
// return root of child just inserted
struct trie* insert(struct trie* root, char word[], int index) {
if (root == NULL) { // if empty
struct trie* newnode = malloc(sizeof(struct trie));
int i;
for (i = 0; i < 26; i++)
newnode->nextLetter[i] = NULL; // set all children to null
if (index == strlen(word)) {
newnode->isWord = 1; // if index matches length of word full stored it into dictionary
} else {
newnode->isWord = 0; // don't have a match, continue inserting letters
newnode->nextLetter[(int)(word[index]-'a')] = insert(newnode->nextLetter[(int)(word[index]-'a')], word, index + 1);
}
return newnode;
}
// if dictionary isnt empty
if (index == strlen(word))
root->isWord = 1; // fully stored word into dictionary
else // else, keep working on it, store next letter in word
root->nextLetter[(int)(word[index]-'a')] = insert(root->nextLetter[(int)(word[index]-'a')], word, index+1);
return root;
}
// solves boggle to check all possible words to be made
// from boggle board, go through each row and column to
// start word from each location and mark letters already
// used during making current word
void result(char board[][SIZE], struct trie* dictionary, int round) {
printf("Words for Game #%d: ", round);
char word[MAX_LENGTH + 1]; // extra location for terminating 0
int usedLetter[SIZE][SIZE];
int row, column;
word[0] = '';
// mark all flags of letters as not being used yet
for (row = 0; row < SIZE; row++) {
for (column = 0; column < SIZE; column++)
usedLetter[row][column] = 0;
}
// loop through entire boggle board so each index can be beginning of word
for (row = 0; row < SIZE; row++) {
for (column = 0; column < SIZE; column++) {
word[0] = board[row][column];
word[1] = ''; // set index to null so doesn't read past
usedLetter[row][column] = 1; // set as being used again
solve(word, usedLetter, row, column, board, dictionary);
usedLetter[row][column] = 0; // set as not being used again
}
}
printf(" ");
}
// where get word if there is a word, if not word
// check if prefix, if prefix then continue search
// to make a word, else don't have word so do nothing
void solve(char word[], int used[][SIZE], int currX, int currY, char board[][SIZE], struct trie* dictionary) {
if (isWord(word, dictionary)) printf("%s ", word); // if word then print
if (isPrefix(word, dictionary)) { // break out since no words can be made
int length = strlen(word), i;
// floodfill to go through neighboring pieces
for (i = 0; i < DIRECTION; i++) {
int nextX = currX+DX[i];
int nextY = currY+DY[i];
// continue only if valid location and letter isn't being used
if (inbounds(nextX, nextY) && !used[nextX][nextY]) {
word[length] = board[nextX][nextY];
word[length + 1] = ''; // set next location to be end of word for string operations
used[nextX][nextY] = 1; // set location as being used
solve(word, used, nextX, nextY, board, dictionary); // continue search for word
word[length] = ''; // set terminating 0
used[nextX][nextY] = 0; // set letter as free to use
}
}
}
}
// searches to end of word, if get to end of trie
// before reaching end of word then know no word can
// be made, if get to end of word before getting to
// leaf node then word can be made from this prefix
int isPrefix(char word[], struct trie* dictionary) {
int i;
int length = strlen(word);
// Go through each letter.
for (i = 0; i < length; i++) {
// if no children then can't be a word
if (dictionary->nextLetter[(int)(word[i]-'a')] == NULL)
return 0;
dictionary = dictionary->nextLetter[(int)(word[i]-'a')]; // move onto next child
}
return 1; // if got to end of word then must be a prefix for word in dictionary
}
// returns weather or not a given word is found in
// dictionary using depth-first-search to traverse
// dictionary trie once get to end of word return
// that node's status of being a word in trie
int isWord(char word[], struct trie* dictionary) {
int i;
int length = strlen(word);
for (i = 0; i < length; i++) {
// if no children then can't be a word
if (dictionary->nextLetter[(int)(word[i]-'a')] == NULL)
return 0;
dictionary = dictionary->nextLetter[(int)(word[i]-'a')]; // move onto next child
}
return dictionary->isWord; // if get to end return weather or not we have a word
}
// check if within bounds of boggle board
int inbounds(int column, int row) {
return (0 <= column && column < SIZE) && ( 0 <= row && row < SIZE);
}
// give back memory borrowed for the dictionary
// using depth first search
void freetree(struct trie* root) {
if (root != NULL) {
int i;
for (i = 0; i < 26; i++) // recursively free up children
freetree(root->nextLetter[i]);
free(root); // free up current node after no children
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.