pset5 - possessives and substrings

Question

I have posted this questions a few days ago, but none of us were getting anywhere. I thought maybe including my code for load as well as check might yield some new revelations. Anyway, here is the issue:

Check50 is saying my code fails on possessives and substrings, but I'm not quite sure why. First of all, here is the check50 output.

Next, here is my code for load:

bool load(const char* dictionary)
{
    //load dictionary and check if it failed
    FILE* dictptr = fopen(dictionary, "r");
    if(dictptr == NULL)
    {
        return false;
    }

    //node initializations
    root = calloc(1, sizeof(node));

    //load first character from dictionary
    int letter = fgetc(dictptr);

    //position integer for later
    int pos;

    prevnode = root;

    //start loading loop
    while(letter != EOF)
    {
        //if at the end of a word
        if(letter == '\n' && prevnode != NULL)
        {
            prevnode->is_word = true;
            prevnode = root;
            wordcount++;
        }

        else if(letter != '\n')
        {

            //if letter is apostrophe
            if(letter == '\'')
            {
                //if need new node
                if(prevnode->children[26] == NULL)
                {
                    prevnode->children[26] = calloc(1, sizeof(node));
                }
                //if don't need new node
                prevnode = prevnode->children[26];
            }

            //if letter is a letter
            else if(isalpha(letter))
            {
                //determine indexing position
                pos = toupper(letter) - 'A';

                //if need new node
                if(prevnode->children[pos] == NULL)
                {
                    prevnode->children[pos] = calloc(1, sizeof(node));
                }
                //if don't need new node
                prevnode = prevnode->children[pos];
            }
        }
        letter = fgetc(dictptr);
    }
    fclose(dictptr);
    return true;
}

And here is my code for check:

bool check(const char* word)
{
    //position integer for later
    int wpos;
    //present letter in the tested word
    int wletter;

    //reset prevnode
    prevnode = root;

    //iterate over word
    for(int i = 0, n = strlen(word); i < n; i++)
    {
        //load in [i]th letter of word to be checked
        wletter = word[i];

        //if checking letter
        if(isalpha(wletter))
        {
            //ignore case
            wpos = toupper(wletter) - 'A';

            //if misspelled
            if(prevnode->children[wpos] == NULL)
            {
                return false;
                break;
            }
            //letter present in trie, move on
            else if(prevnode->children[wpos] != NULL)
            {
                prevnode = prevnode->children[wpos];
            }   
        }
        //if checking apostrophe
        else if(wletter == '\'')
        {
            //if misspelled
            if(prevnode->children[26] == NULL)
            {
                return false;
                break;
            }
            //apostrophe present in trie, move on
            else if(prevnode->children[26] != NULL)
            {
                prevnode = prevnode->children[26];
            }
        }
        //if end of checked word
        else if(wletter == '\0')
        {
            //correctly spelled
            if(prevnode->is_word == true)
            {
                return true;
                break;
            }
            //incorrectly spelled
            else if(prevnode->is_word != true)
            {
                return false;
                break;
            }
        }
    }
    return true;
}

Variables like root and prevnode are declared at the top of dictionary.c.

Any insight is GREATLY appreciated. This "seems" to be my last issue. Once this is solved, I can finally put this pset to bed.

Thanks in advance!

Answer 1

Actually, your problem is a lot more severe than it appears. You are getting a massive number of false positives. I say that they're false because you're not actually checking the words correctly. So let's start with that.

But first, some good news. Load is working correctly.

At the bottom of your search function, you have a catch-all statement, return true. This return is supposed to deal with anything that drops through all of the other code. Unfortunately, it should be return false, not true. The only time a true should be returned is when is_word == true. Once I changed this and ran the program against holmes.txt, it gave well over 100,000 misspelled words - the vast majority of words in the text to be checked. That revealed that there was a significant problem somewhere. Now, the challenge was to try and duplicate the problem while stepping through the program.

I used a small dictionary and a test file. Both had the word eBooks as the first word. I stepped through check() and noticed that it would check every letter in the word. The next step in the process is to check for the expected end of string marker \0. The code never executed this step. At this point, it would always drop through and execute the return true at the end.

As a side note, I think the only time a correct false would be returned would be when a word being checked wasn't in the dictionary, but the beginning of the word was, such as caterpillar(not in dictionary) / cat (in dictionary).

In most programming tasks, when manipulating or comparing a word, we use strlen(word) as the length and ignore the end of string marker in the processing. Unfortunately, this code and technique critically depends on processing the end of string marker as a signal to check if a word is in the dictionary. Your code never gets to it because of one very easy, very small oversight. Look at your for loop statement:

for(int i = 0, n = strlen(word); i < n; i++)

If the word is cat, then the code processed word[0] through word[2]. But \0 is stored in word[3] and when i=3, the loop exits, so the \0 is never processed.

I made one very small change, and everything works perfectly. ;-)

for(int i = 0, n = strlen(word); i <= n; i++)

This is an excellent example of how a small error can have a massive impact and how one error can both create false correct results and mask other issues.

If this answers your question, please click on the check to accept. Let's keep up on forum housekeeping. ;-)