cs50 Speller does not handle most words and case is not insensitive

Question

I have tried everything I know how to do to resolve this issue. I have tried adjusting the strcompcase() function to reflect the integer it returns, but I may not know the correct way to do that, and I tried converting all text to a lower case before hashing and using just strcmp (). Not only does that not fix the problem, but then I have memory issues.

I'm assuming it's an issue with my check function, but it might not be. I could really use the advice of people who actually know what they're doing, as I definitely do not.

Thank you in advance.

// Implements a dictionary's functionality

#include <stdbool.h>
#include <ctype.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;

// Number of buckets in hash table
const unsigned int N = 200000;

// Hash table
node *table[N];

unsigned int dict_size = 0;

// Returns true if word is in dictionary else false
bool check(const char *word) {
    // getting hash value of word
    int index = hash(word);

    // declare travel point to navigate table
    node *trav = table[index];

    while (trav != NULL) {

        // comparison to find if word is present in table
        if (strcasecmp (trav->word, word) == 0) {
            return true;
        } else {
            trav = trav->next;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word) {
    // hash function found https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/
    unsigned int index = 0;
    for (int i = 0, n=strlen(word); i < n; i++) {
        index = (index << 2) ^ word[i];
    }
    return index % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary) {

    // declaring buffer array
    char dict_word [LENGTH + 1];

    // opening dictionary file
    FILE *dict = fopen(dictionary, "r");

    // double checking if file opened correctly
    if (dict == NULL) {
        printf("Dictionary did not open.\n");
        return false;
    }

    // looping through until end of file
    while (fscanf (dict, "%s\n", dict_word) != EOF) {

        // hashing word to check
        int index = hash(dict_word);
        node *new_node = malloc (sizeof(node));

        // making sure malloc worked
        if (new_node == NULL) return false;

        // checks if index is empty
        if (table [index] == NULL) {
            // points index to new node
            table [index] = new_node;

            // points next field to NULL
            new_node->next = NULL;

        // if not empty
        } else {
            // insert new node at front of list
            new_node->next = table [index];

            // makes new node head of list
            table [index] = new_node;
        }

        // insert word into new node
        strcpy(new_node->word, dict_word);
        dict_size ++;

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void) {
    for (int i = 0; i < N; i++) {

        // creates new travel pointer
        node *cursor = table [i];

        while (cursor != NULL) {
            // creates temporary pointer, synch with cursor
            node *tmp = cursor;

            cursor = cursor->next;

            // free what tmp is pointing at
            free(tmp);
        }
    }
    return true;
}

Consider using the lower case value of each letter in the hash function. — DinoCoderSaurus

Nicolas F Nicolas F · Accepted Answer · 2020-07-11T23:02:30

I had the same issue while doing this... You hashed the word BEFORE converting it to lower case. Here is your check function:

// Returns true if word is in dictionary else false
bool check(const char *word) {
    //Just converting the word to lowercase
    char* lower_word = strcmp(word)
    // getting hash value of word
    int index = hash(lower_word);

    // declare travel point to navigate table
    node *trav = table[index];

    while (trav != NULL) {

        // comparison to find if word is present in table
        if (strcasecmp (trav->word, word) == 0) {
            return true;
        } else {
            trav = trav->next;
        }
    }
    return false;
}

What I cahnged is I convert the work to lowercase, so the ASCII value calculates your word with lower-case letters I hope this works!

cs50 Speller does not handle most words and case is not insensitive

1 Answers