2

I've been stuck on speller for weeks and decided to move forward to other Problem Sets... and only recently decided to try again... I managed to get it to work and it is getting the same results as the staff solution. However, it does not pass check50 :(

When i execute check50, this shows up:

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

I tried to run debug50 and looked at more details for the check50, but I am unable to find the error... at this point I feel like the question I should be asking is whether I'm able to pass the CS50 course without submitting Speller :(

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 6000

// Represents a node in a hash table
// "defining" a hashtable data structure here, so you can use it later to malloc
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Represents a hash table
// N represents the number of "pockets"
node *hashTable[N];
// dictionary size, keep track of the number of words loaded in the hashtable
int loadedWords = 0;


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

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

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        printf("Could not open dictionary");
        return false;
    }


    // Insert words into hash table
    while (fscanf(file, "%s\n", dictionaryWord) != EOF)
    {
        int index2 = hashValue(dictionaryWord);
        // First, create a node using malloc so that you can insert the word into the hash table
        node *newNode = malloc(sizeof(node));
        // Check to make sure the pointer does not return null... i.e. make sure it succeed
        if (newNode == NULL)
        {
            return false;
        }

        //if the linked list is empty
        if (hashTable[index2] == NULL)
        {
            //make the element point to a new node
            hashTable[index2] = newNode;
            //assign NULL to the new pointer
            newNode->next = NULL;

        }
        //if you need to insert into an existing linked list...
        else
        {
            // inserting a new node at the start of the linked list
            newNode->next  = hashTable[index2];
            // make new node the head of the linked list
            hashTable[index2] = newNode;
        }
        // insert the dictionary word into the new node
        strcpy(newNode -> word, dictionaryWord);
        loadedWords++;
    }
    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

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

// Returns true if word is in dictionary else false

// Check if word is in dictionary, if it is, return true
bool check(const char *word)
{
    //convert all words to lowercase to simplify ASCII values process
    //first, create a new int so you can modify the input words... because const means you are using constant reference to the original input words and hence cannot modify it
    int length = strlen(word);
    char *newWord = malloc(length * sizeof(char));

    //copy the newWord and make them lowercase
    for (int i = 0; i < length; i++)
    {
        newWord[i] = tolower(word[i]);
    }
    //Run data through hash function
    int x = hashValue(newWord);
    //Check hashtable for node x, set to head of linked list
    node *index = hashTable[x];

    while (index != NULL)
    {
        // compare the two strings
        if (strcmp(index->word, newWord) == 0)
            return true;
        //move to the next element
        index = index->next;
    }
    return false;
} //closes bool check

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node* cursor = hashTable[i];
        while (cursor != NULL)
        {
            node* temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}

Edit: here is the link to the check50 results https://cs50.me/checks/3798b5309c6c04227b6b73b5daaa544a76827285

4
  • Can you add the link to check50 results in the question? – DinoCoderSaurus Mar 21 '19 at 10:02
  • @DinoCoderSaurus hi, i've added in the link for the check50 results. Thank you! – freshwound Mar 21 '19 at 10:04
  • Hmmm. Your output stops at "MISSPELLED WORDS" (and doesn't list the words). That's what was happening in your code in a prior question. I ran a repro of this code and all the "word" tests passed. Spoiler: memory leak :(. Do you have two speller directories? Are you submitting from the right one? Make sure this is the code being submitted. – DinoCoderSaurus Mar 21 '19 at 10:19
  • @DinoCoderSaurus hi, thank you for your reply. I only have one speller directory so I believe this is the right code being submitted... What do you mean by all the "word" tests passed? – freshwound Mar 22 '19 at 5:37
1

A string of strlen(word) characters requires strlen(word)+1 bytes. Don't forget to put a null terminator behind your characters to make it a C-style string.

It's still working if the next byte happens to be zero, that might have happened when you tested locally.

And as @DinoCoderSaurus mentioned, memory leak by malloc without a matching free. Maybe use an array on the stack instead of mallocing that particular thing on the heap.

3
  • Hi! Thank you for replying. I followed your comment and managed to solve speller. However, I don't think I quite understand... do you mind elaborating more? This is my original code: int length = strlen(word); char *newWord = malloc(length * sizeof(char)); and this is what I changed it to: int length = strlen(word); char newWord[length + 1]; newWord[length] = '\0'; – freshwound Mar 23 '19 at 4:05
  • In the C world, a string is a pointer to a first character, and the string continues until we hit the null terminator. strcmp and other string functions rely on that one to know where to stop. Instead of char newWord[length + 1]; you could have used char *newWord = malloc((length + 1) * sizeof(char));, but the newWord[length] = '\0'; is critical, and so is having the space for this null terminator (the +1). And in your code, you forgot to free(newWord); before returning, that's the memory leak, which is trivially fixed by using an array instead of malloc. – Blauelf Mar 23 '19 at 13:50
  • thank you so much for your explanation!!! :) – freshwound Mar 25 '19 at 6:22

You must log in to answer this question.

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