0

So I have been at this problem for some time. I’m glad I have gotten as far as I have. I believe I just have a small step to go before I finish the problem set. (or maybe not). My trie seems to be working fine and the check function too. This I know after comparing my solution to the staffs'.

Where does the problem come from then? When I run check50, I’m finding that the program is finding a hard time handling a min length (1-char) words and handling max length (45-char) words. So I have made a dictionary with one word and a text with the same word to investigate further where the problem is coming from. I have found out that the program sometimes returns 1 less “WORDS IN TEXT” when I run it. In case its 1 word in the text, “WORDS IN TEXT” is returned as 0. This only happens when the last word doesn’t have an extra character at the end. If I added a full-stop at the end for example, “WORD IN TEXT” is returned as 1 as expected.

I am kind of stuck at this spot because “WORDS IN TEXT”, is both calculated and returned in speller.c. We were given instructions that “You may not alter speller.c”. Feel like I am lost for choices. Could someone help me find out why I am getting this errors and what I can do within dictionary.c or elsewhere to get passed it? Thanks Below is my code within dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"
#include "tree.h"

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int Cl_pos;// Check letter position
    char* letters = calloc(strlen(word)+1, sizeof(char));// Making memory space for a pointer to letters

    // Loop to iterate through the word to checke the corresponding letter in the trie
    for (int i = 0, n = strlen(word)-1; i <= n; i++)
    {
        letters[i] = word[i]; //  Equating characters of word to letters since it is a constant
        if(isupper(letters[i]))
        {
            letters[i] = tolower(letters[i]);
        }
        Cl_pos = letter_position(letters[i]);// Getting the letter position
        // Conditional statement to check the first letter
        if ((i == 0 && parent->children[Cl_pos] == NULL) || (i > 0 && trave->children[Cl_pos] == NULL))
        {
            free(letters);
            return false;
        }
        // Traversing the trie if corresponding letter position is found in trie
        else
        {
            if (i == 0 && parent->children[Cl_pos] != NULL)
                trave = parent->children[Cl_pos];
            else if (i > 0 && trave->children[Cl_pos] != NULL)
                trave = trave->children[Cl_pos];

        }
        // Checking if trave is_word is true at the end of the word
        if (i == n && trave->is_word == false)
        {
            free(letters);
            return false;
        }
    }
    free(letters);
    return true;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    file = fopen(dictionary, "r");// Opens the dictionary as a file
    if (file == NULL)
    {
        return false;
    }

    // Getting dictionary size
    fseek(file, sizeof(char), SEEK_END);
    dict_size = ftell(file);
    fseek(file, -1*dict_size, SEEK_CUR);

    trie_stack = (node**)calloc(dict_size, sizeof(node));// Setting aside space for the trie stack

    int c, j = 0;

    int Ll_pos;// Load letter position
    parent = r_decl();
    memset(parent, 0, sizeof(node));// Initialise all children of parent to NULL

    // Loop to construct the trie
    for (c = fgetc(file); c != EOF; c = fgetc(file))
    {

        while (c != '\n')
        {
            j++;

            Ll_pos = letter_position(c);

            // Dynamic memory allocation for the first character
            if (j == 1 && parent->children[Ll_pos] == NULL)
            {
                parent->children[Ll_pos] = (node*)malloc(sizeof(node));

                trave = parent->children[Ll_pos];
                trie_stack[++top] = parent->children[Ll_pos];// Feeling the tire stack
                memset(trave, 0, sizeof(node));// Initialising children of trave to NULL
                dict_words++;// Counting words in the dictionary
            }

            // checking if the first character is in memory
            else if (j == 1 && parent->children[Ll_pos] != NULL)
            {
                trave = parent->children[Ll_pos];
                dict_words++;
            }

            // Dynamic memory allocation for the following characters
            if (j > 1 && trave->children[Ll_pos] == NULL)
            {
                trave->children[Ll_pos] = (node*)malloc(sizeof(node));
                trave = trave->children[Ll_pos];
                memset(trave, 0, sizeof(node));// Initialising the children of trave to NULL

                trie_stack[++top] = trave;
            }
            // Checking if the following character is in memory
            else if (j> 1 && trave->children[Ll_pos] != NULL)
            {
                trave = trave->children[Ll_pos];

            }

            // A break to stop the loop at the end of the file
            if ((c = fgetc(file)) == EOF)
            {
                break;
            }
        }
        // Recognition of the presence of a word in the dictionary
        if (c == '\n' || (c = fgetc(file)) == EOF)
        {
            trave->is_word = true;
        }
        j = 0;
    }
    index = top;
    return true;
}

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

    return dict_words;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Conditional statement to free 10 pointers from the trie stack at a time
    if (top > 0)
    {
        for (int i = 0; i <= 10 && top > -1; i++)
        {
            free(trie_stack[top]);
            trie_stack[top] = NULL;
            --top;
        }
    }
    // Breaking the recursion7
    if (top == -1)
    {
        free(trie_stack);
        trie_stack = NULL;
        free(parent);
        parent = NULL;
        fclose(file);
        return true;
    }
    unload();
    return true;
}

And tree.h

typedef struct node
{
    bool is_word;
    struct node* children[28];
}
node;

struct node* r_decl()
{
    node* f_root = malloc(sizeof(node));
    return f_root;

}

// Function to convert alphabetic characters and '\'' character into letter positions
int letter_position(char a)
{
    int l_pos = 0;
    if ((int)a >= 97 && (int)a <= 122)
    {
        l_pos = (int)a - 97;
    }
    else if ((int)a == 39)
    {
        l_pos = (int)a - 12;
    }
    return l_pos;
}

node* parent = NULL;
node* trave = NULL;
node** trie_stack;

long int dict_size = 0;
long int top = -1;
long int index = 0;
int dict_words = 0;

FILE *file;
9
  • The problem you are facing with "WORDS IN DICTIONARY" is because of the test file. All words must be terminated with a '\n'. It's alluded to in the spec dictionary is assumed to be a file containing a list of lowercase words, one per line, ie the "one per line" part. The one word dictionary is the perfect approach to the problem. Make sure your dictionary is in the proper format so it doesn't distract you from the problem at hand. Mar 18 '19 at 11:26
  • Actually "WORDS IN DICTIONARY" is returning the right number of words. It is "WORDS IN TEXT" T that is returning the wrong number of words
    – alanana
    Mar 18 '19 at 11:51
  • Sorry for my mistake. The same rule applies to the text file. Actually, you can use one file for both the dictionary and the text, simply supply the same file name for both speller arguments. Mar 18 '19 at 11:59
  • Well, thanks. This partly solves my problem. I thought the reason I was getting errors with check50 was that it was not reading the last word. I tried again with one character ending with '\n' and I am getting a segmentation fault. I presume it is the same with a word having 45, the maximum characters.
    – alanana
    Mar 18 '19 at 12:44
  • Ok. If speller shows "MISSPELLED WORDS" before seg fault, the problem is in check. If not, the problem is in load. Your one-word dictionary and debug50 are your go-too tools at this point. Mar 18 '19 at 12:51
1

When creating one-word text to mimic the behaviour of check50, it is important to add the '\n' at the end of the text. Indeed this is the same case even if the text being created was more than one word. The program 'speller.c' will not read the last word in the text if the last character in the last word is a letter.

However, the issue with the code I posted was in unload. In trying to copy the behaviour of check50, I had missed that both the text and the dictionary should have had one word and the word would have to be one character. When I created these as a basis for my debugging, I found out that in the first condition within my unload function I wasn't checking for a possibility of freeing a 0 indexed pointer in my slack. So I added that to the condition and holla! the code passed by check50.

Other issues such as not adding code in '.h' files have been pointed out and it is important to break that habit before one gets used to it.

You must log in to answer this question.

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