1 Introduction
Numerous games can actually be played rather well by computers. Amongst all the different games types existing, we consider here a set of games where the goals require the constitution of english words from a set of letters (rep- resented on tiles, cards, ...).
We propose to write in this assignement an algorithm for computing, given a set of letters, a list of possible words. For example, given "a,b,c" we can compute "a", "b", "c", or "cab". This programming exercise will also be the opportunity to practice with strings, C language, trees and complexities.
2 Algorithm
Basically to have a fast algorithm we propose to build a large tree to store all english words. The provided american-english file contains a list of words. Each word will be inserted in the tree and will end in a leaf node. The tree contains 27 levels. At first level (root node) nothing is specified. From there M + 1 edges go down to the next level where M is the maximal number of times any letter can appear in a word. The first edge will correspond to words which do not contain current level letter. The second edge will correspond to words which contain exactly one such letter, and so on.
When the occurence of all letters is chosen we reach a leaf node which contains a list of words containing exactly the same letters. Figure 1 il- lustrates the start of the tree for M = 9 while Figure 2 shows a leaf node example.
We need to program two different algorithms : one for inserting the words in the tree and the other one for displaying words from the tree. Both algorithm work in a recursive manner. The insertion algorithm takes four different parameters: a node pointer, a word signature, the current letter being processed, a pointer to currently inserted word. The signature is just an array of letter frequencies for current word. It allows to get very quickly the number of times a letter appears in a word. To be more precise,
Figure 2: leaf node
a b c d e f g h i j k l m n o p q r s t u v w x y z
the number of times 'a' appears in the word is stored in the first cell of the array. The number of times 'b' appears, in the second cell, and so on...
The algorithm works as follows: first we check current letter. If we reach the last letter then we insert the word in the corresponding list. If not, we do call the insertion algorithm recursively on the corresponding child of current node. For example, while inserting "cab" with current letter 'b', we continue by recursively inserting with current letter 'c' on the child corresponding to exactly one 'b'.
On the other side we also need an algorithm to display all words which can be built using a set of letters. The algorithm takes as input a dictionary, a signature encoding the letters we can use and the current letter. Again the algorithm works recursively. It works as a depth first search with the condition the all children explored must be reachable with the given signa- ture. For example, when starting from the root, we consider all children corresponding to 0 'a', 1 'a', 2 'a', and so on. If the signature only contains
2 'a' then there is no need to explore the children corresponding to 3 or more
'a' but we must explore all others since it is allowed to leave some letters unused. Once a leaf is reached, all words in the list are printed to the screen.
3 Programming Work
All files are to be downloaded at https://www-id.imag.fr/Laboratoire/ Membres/Wagner_Frederic/mosig.html
You are provided a words.c file which helps you by giving you input output functions. Both the main and read_words functions are given and will read a file containing a list of words (american-english), store them in a dictionary and wait for input on stdin to search for words. It is possible to test for a list of words using standard unix redirections, for example by using time ./words < my_test_list > /dev/nul l.
3.1 Basic Algorithm
You are required to code the algorithms from section 2. Dictionary struc- tures are already defined but you need to define list structures to store words. The following functions are left to be completed:
• list_new : returns an empty list
• list_append : adds a word at end of a list
• list_display : displays all words in a list
• compute_signature : returns the signature array for a given string
• dict_insert : the recursive insertion function
• dict_search_and_display : the recursive search function
3.2 Advanced Algorithm
Once the basic algorithm is working we ask you to write an extension. Both the basic and extended versions of your program need to be submitted so the best is surely to copy your file to a new file before starting.
We ask you to modify your algorithms in order to allow the use of jokers. The joker letter which we will take as '*' is a letter which can be used to replace any other one. For example, if your letters are 'r,c,e,a,*' you can build "reach" using the joker as an 'h' or "carve" using the joker as a 'v'.
We consider here that only one joker is available in the game. Any func- tion prototype can be modified as you like. You are in charge of providing an algorithm.
4 Report
Additionally to your code, you need to send a small 2 pages report. In this report you should explain what you did. Are all required algorithms working ? Can you evaluate the performances of your algorithms ? What is the "joker" version doing and is it fast ?
Please also answer the following list of questions where M denotes the maximal number of appearances of any letter in any word and N denotes the total number of words :
• Give an asymptotic worst case execution cost for the basic insertion algorithm.
• How can you evaluate the cost for a basic search ?
• Give the memory consumption for basic algorithms.
• Give an asymptotic worst case execution cost for the advanced (with the joker) insertion algorithm.
• How does the cost of a search changes when switching from basic to advanced version ?
• What is the memory consumption for your advanced algorithms ? Both code and report are to be sent to [email protected] before
friday November 25.
Attachment:- algo_words.tgz