Reference no: EM13924051

Our problem domain is a puzzle we'll refer to as "Elemental Words". The idea of the game is for multiple human players to take the symbols from a periodic table of elements and recombine them to form English words. The idea of this assignment is to write a program which will do the tedious recombining part for us in order to present us with words spelled using only elements symbols.

Step #0 - Familiarize yourself with the legacy code

Most programmers do not get to design new programs all the time. Someone has to deal with the maintenance & future extensions of existing programs, often referred to as legacy code. Therefore, being assigned on a project often means getting used to the existing work in order to be able to improve it.

GPA-2 gives you a very rudimentary taste of what it is about. Unlike GPA-1, you have a bit more existing source to peruse before you jump in to write your own functions.

It is imperative you fully understand the files provided to you to start working on the project before to modify anything. Skipping this step would most likely result in piling bug on top of bug until you're unable to turn in any of the features.

Overview of the provided files

This project, following in the footsteps of recent PAs, has many files included. Let us start by an overall view of the role of each of these files. In red are the files you should not modify during this project;

main.c - Holds the main function which does little but start the series of automated tests by invoking runAllTests.

tests.c tests.h

- These files implement the functions related to the automated testing of our other functions

words.c words.h

- This file implements the functions related to managing a list of English words
- The list is implemented as a static array in order for it to be usable by all functions in words.c but no other functions.
- The other files of the project will therefore have to use the functions you defined in this file in order to manipulate the data structure
- You are provided with a wordsInitialize function which loads all the data

from a text file also provided - see below

elements.c elements.h

- These files implement the functions related to managing data about the periodic table of elements; name of the elements, symbol of the elements
- This table is indexed starting at 1 - not 0 - so that the index represents the atomic number of the element.

game.c game.h

- These files implement the functions related to the game itself
- They use the functions and data from the elements & words files.

words.txt elements.txt

- This plain text files are read by your program when it starts to load the data it will be using
- The functions wordsInitialize & elementsInitialize do this for you so no need to learn to read from text files for this GPA

You will have to modify & extend these files in order to implement the various features expressed in the requirements.

Design Philosophy

While we are not able to leverage object-oriented programming design techniques in the language we study this semester, you will note that GPA-2 illustrate a design philosophy which attempts to implement "modules" of sorts.
- Everything related to the storage of data about the list of elements, along with the available functions to manipulate it, is in the files elements.c & elements.h.

Similarly, everything related to the words list we are using is in words.c & words.h.

- We use static global variables in these files in order to achieve something close to instance variables in object oriented programming. These variables are not accessible from other files, see definition of "static" in textbook, therefore, they may only be modified by the functions provided by these files to the rest of the project. This is similar to methods allowing programmer to modify the data in an object while the attributes holding it are out of reach.

Step #1 - Find a word in our words list

Objectives

Our first step will be to implement the features needed by the wordsFind function in words.c. Right now this function only returns 0, meaning false, to indicate it was not able to find the string passed as parameter in our words list.

We need to implement an algorithm allowing us to search through the word list for the parameter string and return true if it was found or false if it wasn't.

How to implement it

You will note that the body of the wordsFind function has a return 0; line which you will comment. It also has a return wordsFindSlow(w); line which you need to uncomment for this step. It delegates the work to another helper function named wordsFindSlow which we are going to implement.

The idea of this function is to search for its parameter in the words array in the most elementary manner. This means going through all the words from our words list, comparing w to each of them, and returning true as soon as we found a match. If we go over all elements of words without finding a match, we return false.

Make sure that the comparison between something like "NiNTeNdO" and "nintendo" returns true. To do so, use the strcasecmp function which you will find defined at
https://linux.die.net/man/3/strcasecmp
We will study more string manipulation functions by module [203] but for now this is the only one you are allowed to use.

Step #2 - Find a word but faster this time

Objectives

We want to implement a faster search algorithm in a function named wordsFindFast which we are then going to use from within wordsFind instead of the wordsFindSlow version we implemented during the previous step.
This step relies on the binary search technique presented in module [201].

How to implement it

You have probably noted that, in addition to the line invoking wordsFindSlow, we have another commented-out line in the function wordsFind which invokes wordsFindFast.
You need to comment the return wordsFindSlow(w); line then uncomment the return wordsFindFast(w); line.

Then, you need to implement the wordsFindFast function so it does the same work than your wordsFindSlow but by using a binary search algorithm to speed up the search process.

You may implement it using loops or using recursion. If you opt for the later, you may have to add another function to the program to help you implement the recursion.

Step #3 - Generating words from Elements' Symbols

Objectives

We will now implement the elementsBuildWord function in file elements.c.

This function takes parameter representing a list of atomic numbers and retrieves the symbols matching each atomic number in order to concatenate them to form a word which is then returned.

How to implement it

You need to use a temporary variable to hold a string of MAX_GENERATED_WORD_LENGTH characters which you will use to store the string representing the word you are building. When this function returns, the temporary variable should not be stored anymore in memory.

You will then iterate over the list of symbols provided to your function. This list is implemented in an array named symbols of size nbSymbols. Each element of this array is an int representing the atomic number of the element which symbol we want to use to spell a word. The atomic numbers are to be used as parameter to the getElementSymbol function which will return the string representing this element's symbol. These strings need to be concatenated to your temporary string in order to build the word represented by the series of atomic numbers in the parameter symbols.

If one of the symbol is not valid, as determined by getElementSymbol, you need to return NULL from the elementsBuildWord function. Dispose of anything which was dynamically allocated up to this point, in elementsBuildWord itself or any of the functions you used in its implementation, since you are pretty much aborting.

When you are done building the word out of the symbols, return a strdup of your temporary string.

You may use strcpy, strcat and strdup to implement this step. The latter has documentation at https://linux.die.net/man/3/strdup.

Make sure you understand that strdup takes a string, allocate memory for a copy of it using malloc, then returns the address of the new copy. As such, any function using elementsBuildWord is getting a newly allocated string which will have to be freed before the program ends. This explains why test_elementsBuildWord function in tests.c uses free to dispose of the string after making sure they match the expected result.

Step #4 - Refactoring the data loading for words

Objectives

The data loading as it is implemented in function wordsInitialize works just fine. Except that we are really wasting memory and not taking advantage of the runtime memory allocation techniques introduced in module [203].

We are going to refactor the existing wordsInitialize function to allow the strings in the arrays they populate to be sized to the data being processed rather than arbitrarily set to a large size.

How to implement it
It's time we take a closer look at the wordsInitialize function. While we'll ignore the parts which read data from the text file, we may note that, inside the loop reading every line from the file, we make a copy of the string we just read into words[nbWords].

The latter is defined earlier in this file as being a two dimensional array of fixed size. We have MAX_NB_WORDS elements which each hold an array of MAX_WORD_LENGTH characters.

This data structure involves a huge waste of memory. The larger these two values are, the more room we block in our memory to accommodate what might be just a few, very short, words.

For now, we will accept the idea of having the first dimension of the array arbitrarily large; this pretty much sets a maximum to how many words our program will read from the text file to load into RAM. However, we want to stop wasting so much memory to store strings. Two main sources of waste are obvious;

- If we have less than MAX_NB_WORDS words to read from the file, then the remaining slots each waste MAX_WORD_LENGHT characters

- Even if we were to use all the slots, each word will not be MAX_WORD_LENGTH characters in length. Every character not used past the ‘\0' of the word is also wasted

The idea behind this step is therefore to turn words from a fixed-size two-dimensional array into a fixed size 1-dimensional. In addition, each element of this array will hold pointers on strings instead of fixed-size arrays of characters themselves. If our MAX_NB_WORDS is 1000, we will therefore have to store 1000 pointers on strings rather than 1000 arrays of MAX_WORD_LENGTH characters.

We expect all these pointers to be initialized to NULL to start off with. Only when we read a string into the variable tmpWord inside the loop, we will then allocate memory to store a copy of the string and assign the address of this copy to our array. You are allowed to use strdup to allocate a copy of a string.

When you are done, make sure to also implement the wordsTearDown function which will free all the memory you allocated dynamically. This function is used from runAllTests.