CS50 pset5 SPELLER - most basic words & substrings issues

Question

I have been stuck in pset5 for a while now. No matter from which angle I look to my code I cannot fin out what is wrong with it. I set my number of buckets randomly to 1000. Can someone find out the problem?

Below is the reply I get from check50 :) dictionary.c, dictionary.h, and Makefile exist :) speller compiles :( handles most basic words properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..." :) handles min length (1-char) words :) handles max length (45-char) words :) handles words with apostrophes properly :) spell-checking is case-insensitive :( handles substrings properly expected "MISSPELLED WOR...", not "MISSPELLED WOR..." :| program is free of memory errors can't check until a frown turns upside down

these is what I've done:

const unsigned int N = 1000;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //convert *word to lowercase so that the hash function is case-insensitive
    int length = strlen(word);
    char copy[length + 1];
    for (int i = 0; i < length; i++)
    {
        copy[i] = tolower(word[i]);
    }

    // create a variable to return hashed value of word
    int index_check = hash(copy);

    //create cursor to traverse the linked list
    node *cursor = table[index_check];

    //check if word is in the linked list
    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }

    //return false if cursor->next = NULL has been reached
    return false;
}

// Hashes word into a number
unsigned int hash(const char *word)
{
    // Source of hash function: stackoverflow.com/questions/14409466/simple-hash-functions
    unsigned int count;
    unsigned int hashValue = 0;
    for(count = 0; word[count] != '\0'; count++)
    {
        hashValue = word[count] + (hashValue << 6) + (hashValue << 16) - hashValue;
    }
    return (hashValue % N);
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // open dictionary file
    FILE *f = fopen(dictionary, "r");
    if (f == NULL)
    {
        printf("Dictionary could not be opened\n");
        return false;
    }

    //initialize string as a buffer, to be used in next function, fscanf
    char buffer[LENGTH + 1];

    //loop to check whether end of file has been reached
    while (fscanf(f, "%s", buffer) != EOF)
    {
        //read words from file into buffer
        fscanf(f, "%s", buffer);

        //allocate memory for a node and check if NULL
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            printf("Could not allocate memmory (malloc *n)\n");
            return false;
        }

        //copy "buffer" into the node created
        strcpy(n->word, buffer);

        //call hash function
        int index = hash(buffer);

        //check if it's the first word being inserted into that bucket
        if (table[index] == NULL)
        {
            table[index] = n;
        }
        else
        {
            n->next = table[index];
            table[index] = n;
        }
    size_dictionary++;
    }
    fclose(f);
    return true;
}
  
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
   node *cursor;
   node *tmp;

    // run thru all buckets
    for(int i = 0; i < N; i++)
    {
        //check if bucket isn't NULL
        if(table[i] != NULL)
        {
            cursor = table[i];
            tmp = cursor;
            while (tmp != NULL)
            {
                cursor = cursor->next;
                free(tmp);
                tmp = cursor;
            }
        }
    }
    return true;
}

Answer 1

tiagoK, I think I'm having the same issue here and been stuck with this exercice for days. What did you mean by " the loop should have been done with lenght + 1", where did you declare this string ? I've tried it on the strcasecmp field and the hash one but it doesn't change anything. Do you remember ?

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

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Choose number of buckets in hash table
const unsigned int N = 17576;

// Hash table
node *table[N];

// Initialize new variables used in the program
unsigned int numberofwords;
unsigned int hashvalue;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // Hash the word to determine its hash value
    hashvalue = hash(word);

    // Set cursor to the head of the linked list of the word
    node* cursor = table[hashvalue];

    // Traverse into the linked list comparing the word to find a correspondance while the cursor isn't pointing to null
    while (cursor != NULL)
    {
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
            cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Inittialize a variable to keep track of the total of ASCII values
     unsigned int sum = 0;

    // Loop in all the letters in the word
    for (int i = 0 ; i < strlen(word) ; i++)
    {
        // Ignore digits
        if (isdigit(word[i]))
        {
            continue;
        }
        else if (isalpha(word[i]) || word[i] == ('\''))
        {
            // Check the first three character in the word while setting them lower letters in order to get they ASCII value
            sum += tolower(word[0] - 'a');
            sum += tolower(word[1] - 'a');
            sum += tolower(word[2] - 'a');
        }

    }
    // Divide the total of the three letters by the number of buckets
    hashvalue = sum % N;
    return hashvalue;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // Open the file
    FILE* file = fopen(dictionary, "r");
    char word[LENGTH + 1];
    {
 if (file != NULL)
        {
            // While dictionary doesn't return EOF, read strings from the file, one at the time
            while (fscanf(file, "%s", word) != EOF)
            {
                // Create a new node for the word and copy it in the node
                node *n = malloc(sizeof(node));
                if (n == NULL)
                    {
                        return 1;
                    }
                strcpy (n->word, "%s");

                // Hash word to obtain a hash value
                hashvalue = hash(word);

                // Insert word into hash table depending if it's the first word or not
                if (table[hashvalue] != NULL)
                {
                    n->next = table[hashvalue];
                }
                else
                {
                    n->next = NULL;
                }
                table[hashvalue] = n;

                // Add one to the counter
                numberofwords++;
            }
            fclose(file);
        }
         else
        {
            fclose(file);
            perror("Loading error");
            return 1;
        }

    }
    // Return true
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // Return the number of words we're keeping track of while loading the dictionary
    return numberofwords;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // Check all the head of the hash table
    for(int i = 0; i < N; i++)
    {
        // Create a temporary node to not lose the rest of the linked list
        node* cursor = table[i];

        // Set the cursor to the next node while the temporary value remains at the inital location, then free it before to move to cursor
        while(cursor != NULL)
        {
            node* tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

Answer 2

The clue is in WORDS IN DICTIONARY. Only half the words in dictionary are loaded. That is because of the back-to-back fscanf in load.