Chris recently got internet at home. Much to his surprise, he’s gotten into onli
ID: 3687985 • Letter: C
Question
Chris recently got internet at home. Much to his surprise, he’s gotten into online games, but not the typical kind. Instead of WOW or other games with many players, Chris likes playing Boggle on-line. Although his job deals with computer science, he loves word games! Everything was going great as his online Boggle rating was increasing until he ran into Penelope Kinsley, or PK, as she prefers to be called, an unassuming wordsmith from the UK. PK soundly beat Chris in several rounds of Boggle. At first, Chris’s strategy was to simply try to log on at strange times so that PK wouldn’t be online. Yet, for whatever reason, PK seems to be very good at reading minds and just happened to be online no matter when Chris logged on. Next, Chris tried to distract PK by talking to her on Boggle chat. Unfortunately, this distracted him more than it distracted her.
Chris’s Boggle rating is steadily dropping and he needs your help!!! Since the game is played online, he can theoretically use the aid of a computer program that can search for words in a Boggle grid. Since computers run quickly, if you can write a program that will produce all the words in a Boggle grid, you can help your grade and help Chris defeat PK!!!
How to Play Boggle
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:
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.
Dictionary IN file: http://pastebin.com/Dc32u4cR
Sample Output: http://pastebin.com/nBZLgLRh
Sample Input: http://pastebin.com/FZprRjEC
NOte: below is the code I have for the trie and reading in the dictionary file
struct trie {
int isWord;
struct trie* next[26];
};
struct trie* myDictionary = init();
// Read in number of words.
int i, n,j,k;
FILE* ifp = fopen("dictionary.txt", "r");
fscanf(ifp, "%d", &n);
// Read in each word and insert it.
for (i=0; i<n; i++) {
char word[100];
fscanf(ifp, "%s", word);
insert(myDictionary, word, 0);
if (i%20000== 0) printf("%d word is %s ", i, word);
}
Explanation / Answer
boogle.txt
2
case
mopi
stre
napd
tred
ajce
iakm
felw
dictionary.txt
38
ale
ant
aorta
ape
blue
book
brown
budget
building
cake
case
chain
chair
computer
cop
cops
depot
dollar
elephant
face
football
green
leaked
money
mouse
opera
post
red
red
running
samosa
simple
street
table
tar
tree
tries
yellow
boogle.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define LETTERS 26
#define MAX_WORD_SIZE 10
#define DICTIONARY "/home/raphael/ClionProjects/boogle/dictonary.txt"
#define GRID "/home/raphael/ClionProjects/boogle/boogle.txt"
#define GRID_ROWS 4
#define GRID_COL 4
//data structure init
typedef struct trie{
int is_word;
struct trie* next_letter[LETTERS];
};
struct Coordinates{
char letter;
int coordinates[2];
int grid_map[4][4];
int bool;
};
//prototypes-----------------------------------------------------------
void insert_word(char *word, struct trie *node, int i);
int search_word(char string[], struct trie *pTrie, int i);
char *check_word_prefix(char *prefix, struct trie *pTrie, int i, struct Coordinates start, struct trie *root,
char **grid);
char **get_grids(int *grid_count);
struct Coordinates search_adjacent(char letter, char **grid, int y, int x, struct Coordinates coordinates);
struct trie * init();
//-----------------------------------------------------------------------
//----
int main() {
//iteration variables
int i, n, count = 0, input_case = 0;
//buffer
char *buff = malloc(sizeof(char) * MAX_WORD_SIZE);
//init struct root
struct trie *root = init();
//end of struct root init, ready to use
//scans the number of input cases
//-----------------------pulls from dictionary file-------------------------------------------
//collect information from dictionary file, houses all possible dictionary entries, additionally; dictionary values
//should be between 3 and 10 characters, so thats nice
FILE *fp = fopen(DICTIONARY, "r");
//catch in case of failure.
if (!fp) {
return 1;
}
//works now from fscanf, but not fgets, im not sure why :(
fscanf(fp, "%d", &i);
for (n = 0; n < i; n++) {
char word[100];
fscanf(fp, "%s", word);
insert_word(word, root, count); //seg faults when implemented in while
}
fclose(fp);
char **grid;
//---------------------------------------------------------------------------------------------
//char *store = malloc(sizeof(char) * 10);
//int check = search_word("case", root, count);
//printf("%d ", check);
struct Coordinates start;
start.coordinates[0] = 0;
start.coordinates[1] = 0;
int game = 0;
int iter = 0;
int grid_map = GRID_ROWS;
grid = get_grids(&game);
//logic area ----------------------------------------
//will print out all values found, it might even wrap all grids together. should be interesting.
for(iter = 0; iter < game; iter++) {
printf("Words for Game #%i ", iter + 1);
int j, k;
for (j = 0; j < (GRID_ROWS * game); j++) {
for (k = 0; k < GRID_ROWS; k++) {
char c = grid[j][k];
char str[2] = "";
str[0] = c;
start.coordinates[0] = j;
start.coordinates[1] = k;
int index = c - 'a';
//printf("%c: %i ", c, index);
//enter logic
check_word_prefix(str, root->next_letter[index], count, start, root, grid);
}
}
}
//int index = 2;
//check_word_prefix("c", root->next_letter[index], count, start, root, grid);
//free the mallocs
free(buff);
free(grid);
free(root);
return 0;
}
/*get_grids() - takes information from boggle.txt and places information in 2d char array.*/
char **get_grids(int *grid_count) {
char **grid = malloc(sizeof(char*) * GRID_ROWS * GRID_COL);
FILE *grid_file = fopen(GRID, "r");
int k = 0;
//same as above, collect data using fscanf and drop in 2d char array.
//collects number of grids for particular test case.
fscanf(grid_file, "%d", grid_count);
if(*grid_count > 1){
grid = realloc(grid, (size_t) ((*grid_count * GRID_ROWS) * (*grid_count * GRID_COL)));
} //realloc in case there are more then one test case
for(k = 0; (*grid_count * GRID_ROWS) > k; k++){
char buffer[5];
fscanf(grid_file, "%s", buffer);
grid[k] = strdup(buffer);
//printf("%s ", grid[k]);
}
fclose(grid_file);
//returns all grids, must be separated to individual games
return grid;
}
//taken from POSIX standard lib.
char *strdup (const char *s) { //my best friend
char *d = malloc (strlen (s) + 1); // Space for length plus nul
if (d == NULL) return NULL; // No memory
strcpy (d,s); // Copy the characters
return d; // Return the new string
}
//search_word() - searched trie to verify if word is in trie.
int search_word(char string[], struct trie *pTrie, int i) {
//returns one if word matches in trie struct
if (i == strlen(string))
return pTrie->is_word;
//printf("string: %c ", string[i]);
int index = string[i] - 'a';
if(pTrie->next_letter[index] == NULL) {
return 0;
}
return search_word(string, pTrie->next_letter[index], i + 1);
}
/*trie* init() - initalizes the trie*/
struct trie * init(){
//counter var
int i;
//create struct
struct trie* tree = malloc(sizeof(struct trie));
tree->is_word = 0;
//set childrens to NULL
for(i = 0; i < LETTERS; i++){
tree->next_letter[i] = NULL;
}
return tree;
}
char *check_word_prefix(char *prefix, struct trie *pTrie, int i, struct Coordinates start, struct trie *root,
char **grid) {
int index = prefix[i] - 'a'; //c - a = 2 ca - a
char letter;
char *prefix_arr = malloc(sizeof(char) * strlen(prefix + 1));
int k = 0, l, win = 0;
start.bool = 0;
//load prefix_arr
for (l = 0; l < strlen(prefix); l++){
prefix_arr[l] = prefix[l];
//printf("%c ", prefix_arr[l]);
}
for(k = 0; k < 26; k++){
if(pTrie != NULL && pTrie->next_letter[k] != NULL){
letter = (char) (k + 'a');
start.letter = letter;
prefix_arr[l] = letter;
start.grid_map[4][4] = 0;
start = search_adjacent(start.letter, grid, start.coordinates[0], start.coordinates[1], start);
//find if these letters are adjacent to corresponding letter.
//printf("%i ", start.bool);
if(start.bool == 1){
win = search_word(prefix_arr, root, 0);
if (win == 1)
printf("%s ", prefix_arr);
if(pTrie->next_letter[k] != NULL) {
check_word_prefix(prefix_arr, pTrie->next_letter[k], i + 1, (start), root, grid);
}
}
}
}
return prefix;
}
struct Coordinates search_adjacent(char letter, char **grid, int y, int x, struct Coordinates coordinates) {
//
//check adjacent squares
//set starting y and x to one...
coordinates.grid_map[y][x] = 1;
if(x < GRID_ROWS && y < 7) {
if (letter == grid[y][x + 1]) { //right one
coordinates.grid_map[y][x + 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y;
coordinates.coordinates[1] = x + 1;
//printf("%c found", grid[y][x + 1]);
return coordinates;
}
if (letter == grid[y + 1][x]) {
coordinates.grid_map[y + 1][x] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y + 1;
coordinates.coordinates[1] = x;
//printf("%c found", grid[y + 1][x]);
return coordinates;
} //down one
if (letter == grid[y + 1][x + 1]) {
coordinates.grid_map[y + 1][x + 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y + 1;
coordinates.coordinates[1] = x + 1;
//printf("%c found", grid[y + 1][x + 1]);
return coordinates;
} //diagonal one
if (x > 0 && y > 0) {
if (letter == grid[y - 1][x]){
coordinates.grid_map[y - 1][x] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y - 1;
coordinates.coordinates[1] = x;
//printf("%c found", grid[y - 1][x]);
return coordinates;
}
if (letter == grid[y][x - 1]){
coordinates.grid_map[y][x - 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y;
coordinates.coordinates[1] = x - 1;
//printf("%c found", grid[y][x - 1]);
return coordinates;
}
if (letter == grid[y - 1][x - 1]){
coordinates.grid_map[y - 1][x - 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y - 1;
coordinates.coordinates[1] = x - 1;
//printf("%c found", grid[y - 1][x - 1]);
return coordinates;
}
if (letter == grid[y - 1][x + 1]){
coordinates.grid_map[y - 1][x + 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y - 1;
coordinates.coordinates[1] = x + 1;
//printf("%c found", grid[y - 1][x + 1]);
return coordinates;
}
if (letter == grid[y + 1][x - 1]){
coordinates.grid_map[y + 1][x - 1] = 1;
coordinates.bool = 1;
coordinates.coordinates[0] = y + 1;
coordinates.coordinates[1] = x - 1;
//printf("%c found", grid[y + 1][x - 1]);
return coordinates;
}
}
}
coordinates.bool = 0;
return coordinates;
}
/*insert_word() - inserts word for trie. accepts 1 word and places into trie.
* recursion happens to find next letter in word. */
void insert_word(char *word, struct trie *node, int i) {
//checks if complete word is inserted, if so return 1 and is_word = 1
if(i == strlen(word)){
node->is_word = 1;
return;
}
//next letter create the word.
int index = word[i] - 'a';
if (node->next_letter[index] == NULL)
node->next_letter[index] = init();
//run for all words down the list.
insert_word(word, node->next_letter[index], i + 1);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.