Document version number: 1.1.
Please check the CITS1210 web-site to ensure that you have the latest version.

Project 1: Wordsquares

You must submit your project before the submission deadline above. The penalty for late submission is discussed in the unit outline.

The Problem

For example, consider the wordsquare below:

dhieffLxyd
NzHELLOrTm
qUytemOpHa
glFdgjTwEs
tdyohptpRx
dxeFzofuEB
iphgIfDtOr
wqpdcNdLze
swaqIpDmkl
DROWfuytzs

Highlighted in red capital letters are 8 words (there may be others too), indicating the different directions words may appear. Notice that while words can appear in any direction, the letters making up the word must be contiguous (one after another in a "straight" line). Also notice that words may share letters with other words (e.g. find and wind both share the n character).

Your task in this project is to write an ISO-C99 program that automatically determines which words from a list of words appear in a given wordsquare. Your program will need to read the 2D grid of letters and the list of words from two separate files (the grid-file and words-file respectively), search for the words in the wordsquare, and report which words were located and which were not. For those words found in the wordsquare, the number of times the word was found should also be reported. Your program will also need to highlight (by capitalising) all the characters in the wordsquare used to form any of words from the list. Should a word appear multiple times, all occurrences of the word in the wordsquare must be highlighted.

After locating all occurrences of words listed in the words-file, your program must then search through a dictionary file (a text file containing words, one word per line) to find the longest word that can be made up of characters not used (not highlighted) in the wordsquare, reporting both the unused characters contained in the wordsquare (in left-to-right, top-to-bottom order) and the longest word in the dictionary that can be formed from just these characters. Should there be multiple matching longest words in the dictionary, your program should report the first longest word found in the dictionary.

While the name of the puzzle may imply otherwise, there is no reason the wordsquare should necessarily be square. Indeed, in this project we will allow rectangular wordsquares, but note that each row of the wordsquare must contain the same number of characters.

Also, while traditionally wordsquare puzzles allow words to be found in any of the eight different search directions, in this project, we will allow the user to specify which search directions can be used for each word in the words-file. To achieve this, the words-file will specify for each word the search directions to use for that word. Search directions are specified by a string of digits; each digit representing a search direction corresponding to the direction of that digit from the centre digit on the numerical keypad of a standard computer keyboard. For example, the digit 6 specifies searching in the left-to-right direction while the digit 1 specifies searching diagonally down in the right-to-left direction. We will assume the digit 5 is used as a shortcut to represent all eight search directions.

Each line of a words-file is hence split into two parts: the word (a contiguous sequence of one or more lower-case alphabetic characters), and a search directions string (a contiguous sequence of one or more digits), separated by a contiguous sequence of one ore more whitespace (space or tab) characters.

So, for example, if your program was given the wordsquare:

dogxbxxxnoon
rhellotherex
okciuqbrownm
wxwgexlxhjij
oozokvuxdrow
rlxdrxextxja
drowblonkgod

and the following words-file:

hello 5
help 5
dog 5
brown 5
join 5
row 5
word 5
quick 5
averyverylongword 5
noon 5
z 5
blue 5
blunt 5
even 5
blink 5
noon 8624
noon 9317
noon 82
noon 64
noon 6
noon 4
row 8624
row 9317
row 82
row 64
row 6
row 4
word 123
word         123
word	123
word 1111111111111111111111123

The word "hello" was found 1 time using search directions 5.
The word "help" was NOT found using search directions 5.
The word "dog" was found 3 times using search directions 5.
The word "brown" was found 1 time using search directions 5.
The word "join" was found 1 time using search directions 5.
The word "row" was found 7 times using search directions 5.
The word "word" was found 4 times using search directions 5.
The word "quick" was found 1 time using search directions 5.
The word "averyverylongword" was NOT found using search directions 5.
The word "noon" was found 2 times using search directions 5.
The word "z" was found 1 time using search directions 5.
The word "blue" was found 2 times using search directions 5.
The word "blunt" was NOT found using search directions 5.
The word "even" was found 1 time using search directions 5.
The word "blink" was NOT found using search directions 5.
The word "noon" was found 2 times using search directions 8624.
The word "noon" was NOT found using search directions 9317.
The word "noon" was NOT found using search directions 82.
The word "noon" was found 2 times using search directions 64.
The word "noon" was found 1 time using search directions 6.
The word "noon" was found 1 time using search directions 4.
The word "row" was found 5 times using search directions 8624.
The word "row" was found 2 times using search directions 9317.
The word "row" was found 2 times using search directions 82.
The word "row" was found 3 times using search directions 64.
The word "row" was found 3 times using search directions 6.
The word "row" was NOT found using search directions 4.
The word "word" was found 1 time using search directions 123.
The word "word" was found 1 time using search directions 123.
The word "word" was found 1 time using search directions 123.
The word "word" was found 1 time using search directions 1111111111111111111111123.

Note that palindromes (words that read the same forwards as they do backwards) count twice (see the output for the word noon above).

Your program should also highlight all the characters in the wordsquare used to form any of words from the words-file, thus transforming the wordsquare into (red font used for emphasis only):

DOGxBxxxNOON
RHELLOtherex
OKCIUQBROWNm
WxWGExLxhjIj
OOZOkVUxDROW
RlxDRxExtxJa
DROWbloNkGOD

Finally, your program should report the unused characters in the wordsquare and the longest word found in the dictionary file that can be formed from just these characters. For example, if your program was informed to use the (standard) /usr/share/dict/words dictionary, your program should additionally output the text:

Unused characters in the wordsquare: xxxxtherexmxxxhjjkxlxxxtxablok.
The longest word found in '/usr/share/dict/words' using the pattern 'xxxxtherexmxxxhjjkxlxxxtxablok' is: bottlemaker.

Your program should accept the name of the files containing the grid (the grid-file), list of words to search for (the words-file), and the dictionary file (the dictionary-file) as command-line arguments to the program.

Your program will need to check the validity of the contents of both the grid-file and words-file (no validity checks are needed on the dictionary file). A grid-file must be rectangular (a square is deemed to be rectangular) and must contain only lower-case characters. Lines in the words-file must meet the specification detailed above. You must also ensure that the wordsquare will "fit" into the allocated array in your program (see the MAXSIZE #define in the provided template file below), and importantly, that your program does not crash if the wordsquare is too large. There is no constraint on the number of words that may appear in a words-file or dictionary-file.

One possible extension to this problem is detailed in the document Advanced Functionality. Note that you do not need to complete these advanced tasks in order to obtain full marks (100%) for the project.

Provided Files

1. wordSquare.c - a template ISO-C99 program that contains the start of a solution to the project. This file provides the main function for your program and a number of function "stubs" that specify the behaviour of functions needed to complete this project. You should write code to complete these functions in your copy of this file. This file also contains a number of constants (#defines) and structure definitions that you should use in your program. Make sure that you understand them fully before you start. The file also details the one global variable you need to complete this project. You should not need to add any extra global variables to your program. While you are free to add your own additional functions, you must meet the provided specification precisely, including the name and type of each function specified in the template file. This means that under no circumstances can you change how a function behaves.
2. wordSquare (execute /cslinux/examples/CITS1210/WWW/Project1/wordSquare) - a MacOSX binary executable file that constitutes a working solution to the problem. You should use this executable to compare your program to the sample solution. You must replicate the behaviour of this solution (including the format of the output) precisely.
3. compare (execute /cslinux/examples/CITS1210/WWW/Project1/compare) - a simple testing script that will help you compare the output of your program to that of the sample solution.
4. SampleGrid - a sample grid-file containing the second wordsquare shown above.
5. SampleWords - a sample words-file containing the list of words above.

Assessment

The project should be completed in pairs (teams of two).

As always, you are expected to show professionalism in your approach by making appropriate use of the features of the language, following the principles of good program design, and adhering to the programming conventions outlined in this unit. During the marking, attention will obviously be given to the correctness of your solution. However, a correct and efficient solution should not be considered as the perfect nor necessarily desirable form of solution. Preference will be given to well presented, well documented solutions that use the appropriate features of the language to complete tasks in an easy to understand and easy to follow manner. That is, do not expect to receive full marks for your program simply because it works correctly. Remember, a computer program should not only convey a message to the computer, but also to other human programmers.

Marks will be allocated to each function according to:

1. correctness: a function must implement the specification exactly and completely,
2. clarity: a function must be easy to understand, and
3. appropriate use of the features of the language.

As a rough estimate, marks will be awarded as follows: 20 (out of 30) marks to program correctness (i.e., how well your functions match the specification of the questions asked), and 10 (out of 30) marks to coding style (i.e. how well you have written the functions in terms of clarity and use of the features of the language).

Part marks to questions may be awarded, so if you are not able to get a function working correctly, you should still submit what you have done. However, you will be significantly penalised if:

1. your submitted program does not compile successfully (e.g. if it contains any compilation errors), or
2. your functions do not meet the provided specification, including the name and type of the function.

You do not need to complete the tasks detailed in the Advanced Functionality document in order to obtain full marks (100%) for the project. Those who undertake and complete significant parts of the advanced functionality tasks will have the opportunity to "recover" marks lost (deducted) in the first part of the project. As a rough estimate, completing the advanced part of the project may allow a student to recover up to 5 (out of 30) lost marks. Note: a score of >100% is not possible.

Submission

1. wordSquare.c - a commented ISO-C99 source file that contains your solution to the problem specified above.

Make sure that the name of your file and the names of your functions match the specifications exactly. You will be penalised significantly if they do not.

Your submission should begin with the following lines:

/*
   CITS1210 Project 1
   Names: <your name> <your name>
   Student numbers: <your student number> <your student number>
   Date: <date of submission>
*/

You must submit your program electronically using the cssubmit facility, available via the URL: https://secure.csse.uwa.edu.au/run/cssubmit. No other method of submission is allowed. The cssubmit facility will give you a receipt of your submission. You should print and retain this receipt in case of any dispute.

Ensure that you submit the correct file to cssubmit. The system does not perform any checks on your submission. Submitting the wrong file may result in a mark of zero for your project. Note also that the cssubmit facility does not archive submissions and will simply overwrite any previous submission with your latest submission.

Only one team member should submit a solution to the project. Teams which make multiple submissions under different user accounts may have their submission incorrectly assessed. Ensure the names and student numbers of team members are listed at the top of your submission.

Good luck!

Submission deadline: 4pm, Friday 4 September 2009