1

Right now, I have been stuck for a while on the speller problem of pset7, due to some erratic behavior of my code.

On some versions of it, many words appeared to be misspelled, but not all of them; however, most of them were two- or three-letter words. There was no pattern that I could see at that point. I found and corrected some mistakes, and got to the other extreme of the outcomes: there's no misspelling whatsoever!

I tried multiple times to check lalaland.txt and no misspellings were found. I tried to make sure it handles words longer than 45 characters and those with '. So far my efforts have proven unsuccessful.

There's also some issues exposed with valgrind; I tried to see if I could correct them, but there's nothing on line 105 (help50 told me to look closer to this line) that I can deem wrong!

The code, at this point, is as follows:

dictionary.h

// Declares a dictionary's functionality

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

// Prototypes
bool check(const char *word);
bool load(const char *dictionary);
unsigned int size(void);
bool unload(void);

#endif // DICTIONARY_H

// Student-created header lines

#ifndef STUDENT_DICTIONARY_H
#define STUDENT_DICTIONARY_H

// Trie datastructure
typedef struct trie
{
    bool isWord;
    struct trie *children[27];
} trie;

// Prototypes
void freeTrieTree (trie *node);

#endif //STUDENT_DICTIONARY_H

dictionary.c

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "dictionary.h"

// word counter
int wordCounter = 0;

// cursor node
trie *cursor = NULL;

// root of the trie tree
trie *root;


// returns true if word is in dictionary; else, false
bool check(const char *word)
{
    // DONE
    // set cursor to root of the trie tree
    cursor = root;

    // loop through each letter in word, making sure it is all lowercase
    for (int l = 0; word[l] != '\0'; l++)
    {
        char lNum = tolower(word[l]) - 'a';
        // if the character is an apostrophe, act accordingly
        if (word[l] == '\'')
        {
            lNum = 26;
        }

        // now, check if the path exists
        if (cursor -> children[atoi(&lNum)] != NULL)
        {
            cursor = cursor -> children[atoi(&lNum)];
            l++;
        }
        else
        {
            return false;
        }
    }

    // finally, check if it is a word indeed
    if (cursor -> isWord == true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // DONE
    char word[LENGTH+1];

    // allocate memory for root; terminate program if non-successful
    root = (trie*) malloc(sizeof(trie));
    if (root == NULL)
    {
        // unload dictionary and exit
        unload();
        return false;
    }

    // open dictionary file; exit program if non-successful
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        // printf("Unable to open dictionary file! Exiting...\n");
        return false;
    }

    // begin loop to scan dictionary word by word and load them into memory
    while (fscanf(file, "%s", word) != EOF)
    {
        cursor = root;
        // if word exceeds stipulated length, continue
        if (strlen(word) > LENGTH)
        {
            continue;
        }

        // begin loop to scan word letter by letter and load them into memory
        for (int l = 0; word[l] != '\0'; l++)
        {
            char lNum = word[l] - 'a';
            // if apostrophe, then store in last slot
            if (word[l] == '\'')
            {
                lNum = 'z' - 'a' + 1;
            }

            int num = atoi(&lNum);

            // if the char is not in trie, create one
            if (cursor -> children[num] == NULL)
            {
                cursor -> children[num] = (trie*) malloc(sizeof(trie));
                cursor = cursor -> children[num];
            }
            // otherwise, get to address in children
            else
            {
                cursor = cursor -> children[num];
            }
        }
        // we have a word
        cursor -> isWord = true;

        // increment word number
        wordCounter++;
    }
    // close file
    fclose(file);

    // return true
    return true;
}


// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // DONE
    return wordCounter;
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // DONE
    freeTrieTree(root);
    return true;
}

// Frees every node of the trie tree
void freeTrieTree(trie *node)
{
    // iterate throughout length of struct's children
    for (int l = 0; l < 27; l++)
    {
        // if children pointer not NULL
        if (node -> children[l] != NULL)
        {
            // make use of recursion to go to edge of the node
            freeTrieTree(node -> children[l]);
        }
    }
    // free edge
    free(node);
    // go back
    return;
}

It is worth mentioned that I even inserted a letter into an otherwise correct word, in order to make it wrong, but the code still did not work. On some times I tested my code with ava.txt multiple times in a row, on some attempts the outcome was 0; on others, it was different.

What am I missing? I suppose it is nothing big, but intricate enough to make me look at it for hours with no success.

2

The main problem lies in your check function. The for loop setup increments l on each pass. Unfortunately, the code is also incrementing l inside the loop, so every other letter in a word is skipped, pretty much guaranteeing that every word is misspelled.

There are some other issues to be fixed. First, the use of atoi() is wrong. It shouldn't be used at all. The atoi() function takes a char string, not a single char, and converts it to an int. Without the end of string marker, it doesn't work, or the results are unpredictable.

Next, when the trie nodes are allocated with malloc, they are left uninitialized. That's going to cause problems when checking for null pointers, among other things. All memory should be initialized when allocated, either with explicit assignments or the use of calloc() instead.

Finally, there's this:

    // if word exceeds stipulated length, continue
    if (strlen(word) > LENGTH)
    {
        continue;
    }

This code serves no purpose. Think about what it does. If a word is too long, it executes the continue statement and moves on to the next line inside the loop. If the word is not too long, it moves on to the next line inside the loop. This is called do-nothing code. If you really wanted to catch a long word and error out, then just return false; and exit. If you wanted to skip to the next word, maybe a break instead of a continue? But I'll let you work that out for yourself. It's all moot anyways, because the spec says that words will be less than LENGTH at all times. Also, take a look at the speller.c source code on this. ;-)

There may or may not be more issues, but this'll get you going again.

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

5
  • Yesss! You wrote everything I have been stumbling around to solve ever since I posted this question! I saw on Internet many programmers using calloc to deal with the assignment problem on valgrind. I looked at the mess I made with the atoi() functions (it was my desperate attempt of trying to find what was going on with the misspellings) and finally saw the double incrementation of the variable. I was trying to see which kind of loop would fit best, a while or a for, and while in transition I forgot to adapt the code properly. [CONTINUES] – Igor Matheus Moreira Aug 6 '18 at 23:10
  • The word length check was unnecessary too, as I came to see after a more careful look at speller.c. As the speller documentation says, "Odds are, you didn’t spend enough time looking over speller.c. Go back one square and walk yourself through it again!" On the bad side, I only managed to see this after rewriting the entire solution on another file. On the bright side, I managed to make some optimizations that further decreased the execution time! It is not the lowest, unfortunately, but I am very happy to manage everything by my own. [CONTINUES] – Igor Matheus Moreira Aug 6 '18 at 23:13
  • Finally, thank you for the clarifications! If I was still stuck, it would indeed get me going. On top of that, they confirmed and complemented my discoveries. I hope it helps someone else as well, since I did not see that many implementations of this nature with this exercise. – Igor Matheus Moreira Aug 6 '18 at 23:17
  • Reiterating, thank you for the helping hand! It was much appreciated. – Igor Matheus Moreira Aug 6 '18 at 23:18
  • So.... what you're saying is that you found all the problems, but didn't trust yourself enough??? Happens a lot to new programmers! The important thing is that you had a sense that they were all causing issues and you had a sense to chase them. That's good! Now, you just need to learn to trust your instincts more, and to make fewer careless errors. (That one, we all do, all the time!) Happy coding! – Cliff B Aug 6 '18 at 23:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .