The deadline for odd-numbered groups is Tuesday 26 October
2004, 23:59:59 hours.
The deadline for even-numbered groups is Tuesday 2 November
2004, 23:59:59 hours.
Submission for even-numbered groups will not be
available on Wednesday 27 October 2004 (due to the lab that is
going on for odd-week).
Your file must be named boggle.c, incorrect filename will
result in zero marks. This part of the lab is worth one
mark.
You are strongly advised to complete and understand part
1.
As a grand finale to your labs, we'll apply all that we have learnt in this course and design a program for playing the classic Boggle game. The game of Boggle is played with a 4 x 4 tray filled with 16 random letters (not necessarily unique). The objective of the game is to form words by concatenating adjacent letters with the following rules of the game.
+---+---+---+---+ | Y | A | T | R | +---+---+---+---+ | P | H | N | E | +---+---+---+---+ | X | C | E | Y | +---+---+---+---+ | S | V | L | Q | +---+---+---+---+Here are some words that can be found:
ANY
CHANT
PANEL
PATH
TRENCH
QUEEN -- Q is treated as two letters QU
CHANCE -- uses C twice
CHAPS -- S is not adjacent
Cell with the following members:
letter of type char that stores the random
letter; and
visited flag of type short that is used to
conveniently denote whether the corresponding letter has
already been used to form part of the word. We use short
instead of int to save space.
typedef struct {
char letter;
short visited;
} Cell;
The tray is declared in the main function as Cell
tray[SIZE][SIZE] with SIZE defined as a constant.
The second object is the dictionary which is realized using a linked
list where each node refers to a single word. This is by far one of
the worst implementations for the dictionary. But what to do? You have
to learn how to construct linked lists anyway. The C structure
WordNode for each node, together with their corresponding
type definitions, is implemented as shown below. A separate but similar
linked list structure will also be used to keep track of the list of words
that have been found during the game.
typedef struct WordStruct WordNode;
typedef WordNode *WordPtr;
struct WordStruct {
char *word;
WordPtr next;
};
Your task is to design a program that allows the user to play a single game of Boggle. The program will terminate when the user enters any number. The skeleton code is provided below with details on the specific implementation.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#define SIZE 4
/**
The constant SIZE can be defined to suit your needs.
It need not necessarily denote the actual size of the tray.
**/
#define FILENAME "/usr/share/lib/dict/words"
/**
The filename indicated above is the dictionary provided in sunfire.
If you need an exact copy, you can download from here (right-click
and choose "Save Link As... or Save Target As...")
http://www.comp.nus.edu.sg/~cs1101cl/lab4/part1/words.txt
**/
typedef struct WordStruct WordNode;
typedef WordNode *WordPtr;
struct WordStruct {
char *word;
WordPtr next;
};
typedef struct {
char letter;
int visited;
} Cell;
/**
Function Prototypes.
Please refer to the individual functions below for implementation details.
**/
void PlayBoggle(Cell [][], WordPtr);
void InitTray(Cell [][]);
void ResetFlag(Cell [][]);
void ReadDictionary(WordPtr *);
void AddWord(WordPtr *, char *);
void PrintTray(Cell [][]);
void PrintList(WordPtr);
int WordInTray(Cell [][], char *);
int WordInList(WordPtr, char *);
/**
Function that plays the Boggle game.
DO NOT MODIFY THE CODE.
**/
int main()
{
Cell tray[SIZE][SIZE]; /* 2D array representation for the tray */
WordPtr dict; /* Head of the dictionary linked list */
ReadDictionary(&dict); /* Read in the dictionary as a linked list */
PlayBoggle(tray,dict); /* Play a single game of Boggle */
}
/**
Function that plays a single game of Boggle with the randomized tray
and the dictionary linked list.
Understand how the different sub functions are invoked and used.
DO NOT MODIFY THE CODE.
**/
void PlayBoggle(Cell tray[][SIZE], WordPtr dict)
{
char word[101];
WordPtr wordList = NULL;
/* Initialize the tray with random letters */
InitTray(tray);
/* Display the tray with letters */
PrintTray(tray);
/* Read in a word */
printf("\nEnter word (any number to quit): ");
gets(word);
/*
Check if a word has its first char as a digit.
If yes, then terminate the loop
*/
while (!isdigit(word[0]))
{
/* Reset the visited flag of all the cells on the tray */
ResetFlag(tray);
/* Condition 1: A word should be 3 letters or more */
if (strlen(word) > 2)
/* Condition 2: Check if the word can be found on the tray */
if (WordInTray(tray,word))
/* Condition 3: Check if the word is in the dictionary */
if (WordInList(dict, word))
/* Condition 4: Check if the word has been previously found */
if (!WordInList(wordList,word))
{
/* Add the valid word into the list of found words */
AddWord(&wordList,word);
/* Print the list of words already found */
printf("\n--- Word(s) Found ---\n");
PrintList(wordList);
printf("---------------------\n\n");
/* Display the tray with letters again */
PrintTray(tray);
}
else
printf("\"%s\" has already been found\n", word);
else
printf("\"%s\" is not found in the dictionary\n", word);
else
printf("\"%s\" is not found on the tray\n", word);
else
printf("Word must be at least 3 letters\n");
/* Read in another word */
printf("\nEnter another word (any number to quit): ");
gets(word);
}
printf("\nProgram Terminated...\n");
}
/**
This function initializes the tray with random letters.
To simplify the implementation, each cell is simply randomized with any
of the 26 capital letters from the alphabet.
**/
void InitTray(Cell tray[][SIZE])
{
/* Enter your code here */
}
/**
This function clears the visited flag (i.e. assign with zero) in all
cells of the tray. The flags need to be cleared before we begin
looking for a new word on the tray.
**/
void ResetFlag(Cell tray[][SIZE])
{
/* Enter your code here */
}
/**
Read the dictionary file and represent each word as a node of the linked list dict.
In each node, you need to dynamically allocate an array for storing the word.
The code for reading each word from the dictionary is given below. In each loop,
a new word from the dictionary is stored into the variable word.
You task is to create the desired linked list. You can assume that the
file that is read is already in proper sorted order.
**/
void ReadDictionary(WordPtr *dict)
{
char word[101];
FILE *filein;
/** include other variables **/
if ( (filein = fopen(FILENAME, "r")) == NULL )
{
fprintf(stderr, "Error reading file\n");
exit(1);
}
fscanf(filein, "%s", word);
while (!feof(filein))
{
/**
include the code to store a copy of word
into a node in the linked list.
**/
fscanf(filein, "%s", word);
}
fclose(filein);
}
/**
Function that inserts a node representing the word at the appropriate
position in the linked list wordList.
In each node, you need to dynamically allocate an array for storing the word.
The linked list must always be maintained in a sorted order.
**/
void AddWord(WordPtr *wordList, char *word)
{
/* Enter your code here */
}
/**
This function prints the tray according to the following format:
+---+---+---+---+
| Y | A | T | R |
+---+---+---+---+
| P | H | N | E |
+---+---+---+---+
| X | C | E | Y |
+---+---+---+---+
| S | V | L | Q |
+---+---+---+---+
**/
void PrintTray(Cell tray[][SIZE])
{
/* Enter your code here */
}
/**
Print the linked list, wordList, of words.
**/
void PrintList(WordPtr wordList)
{
/* Enter your code here */
}
/**
Function that checks the existence of a word on the tray.
This function is case-insensitive.
Function returns 1 if the word is found; 0 otherwise.
Hint: One way is to invoke another function (probably recursive) to
check the existence of the word beginning with a particular
cell of the tray.
**/
int WordInTray(Cell tray[][SIZE], char *word)
{
/* Enter your code here */
}
/**
Function that performs a linear search on the linked list
wordList and checks the existence of the word.
This function is case-insensitive.
Function returns 1 if the word is found; 0 otherwise.
**/
int WordInList(WordPtr wordList, char *word)
{
/* Enter your code here */
}
helloKitty@sf3:~[123]$ gcc boggle.c helloKitty@sf3:~[124]$ a.out +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter word (any number to quit): la Word must be at least 3 letters Enter another word (any number to quit): lan "lan" is not found in the dictionary Enter another word (any number to quit): lane --- Word(s) Found --- 1 lane --------------------- +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter another word (any number to quit): nine "nine" is not found on the tray Enter another word (any number to quit): line --- Word(s) Found --- 1 lane 2 line --------------------- +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter another word (any number to quit): cane --- Word(s) Found --- 1 cane 2 lane 3 line --------------------- +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter another word (any number to quit): lane "lane" has already been found Enter another word (any number to quit): queen --- Word(s) Found --- 1 cane 2 lane 3 line 4 queen --------------------- +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter another word (any number to quit): inconsequential --- Word(s) Found --- 1 cane 2 inconsequential 3 lane 4 line 5 queen --------------------- +---+---+---+---+ | S | Q | E | T | +---+---+---+---+ | N | E | N | I | +---+---+---+---+ | N | O | A | L | +---+---+---+---+ | I | C | L | Y | +---+---+---+---+ Enter another word (any number to quit): inconsequentially "inconsequentially" is not found in the dictionary Enter another word (any number to quit): 123 Program Terminated... helloKitty@sf3:~[125]$