1

My speller program (part of pset5) works well and the output exactly matches that of the staff's solution. However, when I run my program through check50, I still get several errors per their script:

:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:) handles most basic words properly
:( handles min length (1-char) words
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( handles max length (45-char) words
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( handles words with apostrophes properly
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( spell-checking is case-insensitive
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) handles substrings properly
:) program is free of memory errors

Link: https://submit.cs50.io/check50/721776e0e89e2336ee7ac371f4b7fe01f48daf77

These errors are strange. My program definitely recognizes one-character words such as "a" and "i," takes apostrophes correctly, etc. I know this since I ran the staff's solution next to mine and programmatically compared the misspelled words in Excel: They all matched.

Here is my code. I can't find what makes check50 trip. Thanks to any brave soul who answers!

// Implements a dictionary's functionality

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <strings.h>
#include <string.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 = 26;

// Hash table
node *table[N]; // This looks like just the beginning of the list

// Variable added by me: A counter for each word added into the dictionary
int wordLoadedCount = 0;


// Returns true if word is in dictionary else false
// This is where the actual dictionary is put to work. 
// check will only be passed words that contain letters and possibly apostrophes
bool check(const char *word)
{
    // CASE INSENSITIVE

    // 0. Remove apostrophes from the word [???]


    // 1. Hash word to obtain a hash value
    int index = hash(word);

    // 2. Access linked list at the index in the hash table
    //Pointer to the first node: table[index]
    // 3. Traverse linked list, looking for the word.

    // CODE FROM WEEK 5 LECTURE
    // Print List / Loop Through Linked List
    for (node *tmp = table[index]; tmp != NULL; tmp = tmp->next)
    {
        if (strcasecmp(word, tmp->word) == 0)
        {
            return true;
        }
    }


    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //Objective: Return a number from 0 to 25 given the first letter of the word.

    //Initialize index variable
    int index = 26; 

    //Check the first letter of the word and convert it to an index from 0 to 25:

    // Convert the first number to its ASCII-equivalent int
    int firstLetter = (int)word[0];

    // Case: Uppercase letters 
    if (firstLetter >= 65 && firstLetter <= 90)
    {
        // We want index = 0 when ASCII value = 65
        index = firstLetter - 65;
    }
    // Case: /Lowercase letters
    else if (firstLetter >= 97 && firstLetter <= 122)
    {
        //We want index = 0 when ASCII value = 97
        index = firstLetter - 97;
    }

    //Check to make sure the return value is actually between 0 and 25 (that the value
    //was actually changed
    if (index == 26)
    {
        printf("We could not hash %s.\n", word);
        return -1;
    }

    //Return index as intended
    return index;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // 1. Open dictionary file
    FILE *file = fopen(dictionary, "r");
    // Intermediate check to see if the file opened
    if (file == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        unload();
        return false;
    }

    //Initialize a buffer variable where we are storing each word
    char storedWord[LENGTH + 1]; 

    // 2. Read strings from the file one at the time
    while(fscanf(file, "%s", storedWord) != EOF)
    {
        //3. Create a new node for each word
        node *newNode = malloc(sizeof(node));
        //Check if malloc() returns NULL
        if (newNode == NULL)
        {
            printf("You program ran out of memory\n");
            return false;
        }
        //Copy the word into the newly created node using strcpy()
        strcpy(newNode->word, storedWord);
        newNode->next = NULL;

        // Update "word loaded" count.
        wordLoadedCount++;

        // 4. Hash word to obtain hash value / index
        int index = hash(storedWord);

        //5. Insert node into the hash table at that location

        // If this bucket of the hash table is empty (not pointing at anything yet)
        // I'm not sure if this step is necessary
        if (table[index] == NULL)
        {   
            table[index] = newNode;
            newNode->next = NULL;
        }

        // If it is not empty:
        else if (table[index] != NULL)
        {

            //a. Point new node to the existing first node
            newNode->next = table[index];

            //b. Point the list head to the new node
            table[index] = newNode;

        }


    }

    //Close the file to release memory
    fclose(file);

    return true;
}

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

    // If the dictionary was loaded...
    if (wordLoadedCount > 1)
    {
        // Go through hash stucture created in load() and count the words stored
        // I will do this inside the load function itself
        return wordLoadedCount;
    }

    // Return 0 if the dictionary not loaded
    return 0;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Loop through each bucket in the hash table
    for (int i = 0; i < N; i++)
    {
        // COPIED FROM WEEK 5 LECTURE CODE
        // "Free list
        // Since we're freeing each node as we go along, we'll use a while loop
        // and follow each node's next pointer before freeing it, but we'll see
        // this in more detail in Problem Set 5."
        while (table[i] != NULL)
        {
        node *tmp = table[i]->next;
        free(table[i]);
        table[i] = tmp;
        }


        //Check to see if we did in fact clear the memory allocated to the hash table.
        if (table[i] != NULL)
        {
            printf("Something went wrong while freeing memory in unload() function.\n");
            return false;
        }
    }

    //Return true if sucessful
    return true;

}

Apologies as I first posted this on stackoverflow.com before discovering there was a CS50-specific StackExchange page.

0

Answered by a brilliant guy here: https://stackoverflow.com/questions/62013392/cs50-speller-pset5-produces-output-that-is-exactly-the-same-as-the-staffs-so

In the size() function, I was setting this condition: if (wordLoadedCount > 1) to check when the program did not load a dictionary successfully. If the dictionary was of exactly one word, as the dictionary tried by check50, the whole size function would not return anything.

I changed it to if (wordLoadedCount > 0) and it passed all the check50 checks.

You must log in to answer this question.

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