0

I am able to pass all of check50 except "handles most basic words properly"

https://cs50.me/checks/32244a2a71079c81f6b1dc1275aaf305b3f0149f

When I run ./speller texts/lalaland.txt in the terminal window to compare my solution with the staff's solution, I get an abnormal amount of misspelled words!

Staff solution

WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         0.24
TIME IN check:        0.01
TIME IN size:         0.00
TIME IN unload:       0.02
TIME IN TOTAL:        0.27

My solution

WORDS MISSPELLED:     17187
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         5.59
TIME IN check:        0.43
TIME IN size:         0.00
TIME IN unload:       15.96
TIME IN TOTAL:        21.98

My trie program

// Implements a dictionary's functionality

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

#include "dictionary.h"

typedef struct trie
{
    // Store current char in dictionary
    bool is_word;
    // 27 Pointers to the struct
    struct trie *paths[27];
}
trie;

// Function prototypes
trie *createNode(void);
void freeNode(trie *temp);

// Global variables
// Declare global variable for root and trav of trie data structure and loaded bool for keeping track of dict
trie *root = NULL;
trie *trav = NULL;
int wordCounter = 0;
bool loaded = false;


// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Make a new copy of word for changing word to lowercase
    char wordCpy[strlen(word)];
    strcpy(wordCpy, word);

    // Set trav to point to root
    trav = root;

    // Set up index for each char in word
    int trieIndex;

    // Loop over each char in word given, moving through trie
    for (int h = 0; h < strlen(wordCpy); h++)
    {
        // Make word given case-insensitive, using tolower function
        wordCpy[h] = tolower(wordCpy[h]);

        // Use trav pointer to move through respective index
        if (wordCpy[h] == '\'')
        {
            trieIndex = 26;
        }
        else
        {
            trieIndex = wordCpy[h] - 'a';
        }

        // If trav pointer's next path location is NULL, word does not exist in trie
        if (trav -> paths[trieIndex] == NULL)
        {
            return false;
        }

        // Move to next trie struct
        trav = trav -> paths[trieIndex];

        // For last char in word
        if (trav -> is_word == true && h == strlen(wordCpy) - 1)
        {
            return true;
        }
    }
    return false;
}


// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Create root node for trie
    root = createNode();
    if (root == NULL)
    {
        return false;
    }
    // Create trie index for inserting char from words found in dictionary
    int trieIndex;
    // Create traversal pointer
    trav = root;
    // Open the dictionary file given
    FILE *dictionaryPtr = fopen(dictionary, "r");
    // Check if dictionary file could be opened
    if (dictionaryPtr == NULL)
    {
        return false;
    }
    // Declare character to store each character of dictionary
    char c;
    // Declare an char array in order to store words found, LENGTH + 1 elements
    char word[46];
    memset(&word[0], 0, sizeof(word));
    // Declare a char variable used in the process of adding word to trie
    char charAdd;
    // Declare an index for words found in dictionary
    int index = 0;
    // Loop over words in dictionary, add them to trie
    for (c = fgetc(dictionaryPtr); c != EOF; c = fgetc(dictionaryPtr))
    {
        // If c contains newline character, indicates that new word is on next line
        if (c == '\n')
        {
            // Add word into trie by looping over word
            for (int i = 0; i < strlen(word); i++)
            {
                // Store each char of word into charAdd
                charAdd = word[i];
                // Get number to be added to root array path based on character
                if (charAdd == '\'')
                {
                    // If charAdd is an ', make trieIndex become last element in trie path index
                    trieIndex = 26;
                    // Add charAdd into trie, if charAdd exists, move trav pointer
                    if (trav -> paths[trieIndex] == NULL)
                    {
                        // Create new trie node at that index
                        trav -> paths[trieIndex] = createNode();
                        // If createNode() returned NULL, it has failed
                        if (trav -> paths[trieIndex] == NULL)
                        {
                            return false;
                        }
                        // Move trav pointer to new node
                        trav = trav -> paths[trieIndex];
                    }
                    else
                    {
                        // Move trav to next path
                        trav = trav -> paths[trieIndex];
                    }
                }
                else
                {
                    // Get index value of char based on http://www.asciichart.com/
                    trieIndex = charAdd - 'a';
                    // Add charAdd into trie, if charAdd exists, move trav pointer
                    if (trav -> paths[trieIndex] == NULL)
                    {
                        trav -> paths[trieIndex] = createNode();
                        // If createNode() returned NULL, it has failed
                        if (trav -> paths[trieIndex] == NULL)
                        {
                            return false;
                        }
                        // Move trav pointer to correct index
                        trav = trav -> paths[trieIndex];
                    }
                    else
                    {
                        trav = trav -> paths[trieIndex];
                    }
                }
            }
            // Set index back to 0 for the next word
            index = 0;
            // Set is_word bool in current node to true
            trav -> is_word = true;
            // Increment wordCounter by 1
            wordCounter++;
            // Set trav back to root for next word
            trav = root;
        }
        else
        {
            // Add char c into word array and increment index by 1
            word[index] = c;
            index++;
        }
    }
    // Close dictionary pointer
    fclose(dictionaryPtr);
    loaded = true;
    // Return true if loading is successful
    return true;
}


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

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

// Function used to create a new node for trie data structure
trie *createNode(void)
{
    trie *node = malloc(sizeof(trie));
    if (node == NULL)
    {
        return NULL;
    }
    // Loop over node trie struct and allocate all pointers in trie to NULL
    for (int x = 0; x < 27; x++)
    {
        node -> paths[x] = NULL;
    }
    // Set is_word in node to false
    node -> is_word = false;

    return node;
}

void freeNode(trie *temp)
{
    // Use of recursion to free up nodes
    // If all of paths[27] are NULL, free node
    for (int x = 0; x < 27; x++)
    {
        if (temp -> paths[x] != NULL)
        {
            freeNode(temp -> paths[x]);
        }
    }
    free(temp);
}

Any help on how to solve this problem will be greatly appreciated! Thank You!

1

Main problem:

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

is the wrong one. Use i < index, as strlen searches for the null terminator, but you never placed one there, so it might find it anywhere, maybe even behind your array.

Possible secondary problem:

char wordCpy[strlen(word)];
strcpy(wordCpy, word);

Please use char wordCpy[strlen(word) + 1]; with enough space for a null terminator. Otherwise you overwrite the next byte, whatever it contains. Or use a simple char for just the character currently processed.

This kind of mistake often results in errors occuring only on word lengths divisible by 8, as otherwise the overwritten byte would have been unused (many variable types are padded in memory to start at addresses divisible by 4 or 8, which sometimes leaves those unused bytes before). valgrind might complain, but I'm not sure.

My thoughts:

Could be a lot shorter if you removed redundancies, and moved common parts out of an if/else.

And checking whether you are at the last iteration is usually not the best way to do it, I'd move that to after the loop (where the last iteration has been completed). But it doesn't seem to break anything.

1
  • Thank you so much for the help! Will try to shorten my code! – Jeremy May 20 '18 at 15:23

You must log in to answer this question.

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