pset5 speller cannot read number of word in dictionary

Question

thank you for clicking. Being concise, I have the right solution for the pset, as evidenced down below by comparing my solution to the staff's, but check50 insists that no words have been loaded into the dictionary.

Commands from pset5 testing section:

./speller texts/lalaland.txt > student.txt
./speller50 texts/lalaland.txt > staff.txt
diff -y student.txt staff.txt

When these are run, it shows me the differences between the outputs of both programs with an '|' or '>' character in the beginning of the line.

2023/week5/prob/speller/ $ ./speller texts/lalaland.txt > student.txt
2023/week5/prob/speller/ $ ./speller50 texts/lalaland.txt > student.txt
2023/week5/prob/speller/ $ diff -y student.txt staff.txt

MISSPELLED WORDS                                                MISSPELLED WORDS

Chazelle                                                        Chazelle
L                                                               L
TECHNO                                                          TECHNO
L                                                               L
Thelonious                                                      Thelonious
Prius                                                           Prius

... for the sake of brevity (there are a lot of words mispelled).

Mia                                                             Mia
Mia                                                             Mia
Sebastian's                                                     Sebastian's
L                                                               L

WORDS MISSPELLED:     955                                       WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091                                    WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756                                     WORDS IN TEXT:        17756
TIME IN load:         0.02                                      TIME IN load:         0.02
TIME IN check:        0.01                                      TIME IN check:        0.01
TIME IN size:         0.00                                      TIME IN size:         0.00
TIME IN unload:       0.01                                      TIME IN unload:       0.01
TIME IN TOTAL:        0.04                                    | TIME IN TOTAL:        0.03

As we both can observe, the only difference between my code and the staff is the running time. Therefore, I have reason to believe that my code is correct. Here is what check50 has to say about that.

2023/week5/prob/speller/ $ check50 cs50/problems/2023/x/speller
Results for cs50/problems/2023/x/speller generated by check50 v3.3.8
:) dictionary.c exists
:) speller compiles
:( handles most basic words properly
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( 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

I have tested my code with different dictionaries, different texts, fed those same parameters to the staff's solution and again, apart from running time, the number of words mispelled and such are the same.

Take a look at this check50 prompt.

There is one word in the text. The program is supposed to take a look at the word in the text, and see if it appears in the dictionary. If it doesn't, that means the word is MISPELLED: it is printed out to the screen under MISSPELLED WORDS and the respective count rises by one. Else, if it does appear, then that means the word is not MISPELLED, therefore the word isn't printed out and the counter isn't updated.

In the "expected output", there is one word in the dictionary, which happens to be the one word in the text. Therefore, no words are mispelled: the mispelled words counter stay at zero.

In the "actual output", there are NO words in the dictionary, and one word in the text. Therefore, since the one word in the text isn't in the dictionary, because there are no words in the dictionary, the one word of the text is MISPELLED and printed out to the screen.

Except, that isn't the case. The word is checked correctly. I feel like that is... impossible. You can probably see the gap of logic there.

As I keep looking at the check50 log's, I see that the outputs of the "expected output" and my "actual output" are the same, EXCEPT for the number of WORDS IN DICTIONARY. It is always zero.

I chucked it up to "Oh well, I did something wrong. Better move stuff around and see what sticks."

That was 4 hours ago. I have tried a lot: moving the unload function around, editing speller.c (it is up to date, the problem is not there), checking if the load function recieves the correct dictionary and not the default one, messing with the size funcion, etc...

Debugging, for me, is just a matter of time, patience and concentration. I don't watch the shorts. I have never looked at the hints section except for practice problems. I have never watched a walkthrough. I always took the bare minimum and thought, or researched, from there because I felt more accomplished with getting perfect check50 scored with as little help as possible.

This one, however, I am truly stuck. I have done all of the above and more for this one.

Pset5 has cut too much into my time allocated for week6, for something that I feel that is outside my control. I would greatly and truly appreciate for you to shed light on this issue.

Sincerely, a confused CS50x student.

My code for dictionary.c is below.

// Implements a dictionary's functionality

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

// TODO: Choose number of buckets in hash table
const unsigned int N = 50492;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    int j = strlen(word);
    char nword[j];
    nword[j] = '\0';
    for (int i = 0; i < j; i++)
    {
        nword[i] = tolower(word[i]);
    }
    for (node *ptr = table[hash(word)]; ptr != NULL; ptr = ptr->next)
    {
        if (strcmp(nword, ptr->word) == 0)
        {
            return true;
        }
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    int hashArr[LENGTH + 1] = {139, 137, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 31, 29,
                               23,  19,  13,  7,   3,   2,   1,   1,   1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1};
    int num = 0;
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (word[i] == '\'')
        {
            continue;
        }
        num += hashArr[i] * (tolower(word[i]) - 'a');
    }
    return num;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }
    node *ptr = NULL;
    char c;
    int idx = 0, h_idx = 0;
    char nword[LENGTH + 1];
    while (fread(&c, 1, 1, dict))
    {
        // end of line
        if (c == '\n')
        {
            nword[idx] = '\0';
            idx = 0;
            ptr = malloc(sizeof(node));
            if (ptr == NULL)
            {
                return false;
            }
            h_idx = hash(nword);
            ptr->word[0] = nword[0];
            for (int i = 1; nword[i - 1] != '\0'; i++)
            {
                ptr->word[i] = nword[i];
            }
            ptr->next = table[h_idx];
            table[h_idx] = ptr;
        }
        // else append char into word buffer
        else if (isalpha(c) || c == '\'')
        {
            nword[idx] = c;
            idx++;
        }
    }
    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // if cat hash not accessed, then dict not loaded
    if (table[hash("cat")] == NULL)
    {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        for (node *ptr = table[i]; ptr != NULL; ptr = ptr->next)
        {
            count++;
        }
    }
    return count;
}

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

Answer 1

Your size function is fundamentally broken as pointed out by @DinoCoderSaurus, you are making a completely invalid assumption. That your code sometimes outputs the same answer as the staff solution does not mean your code is right or correct. That it fails the tests is more telling. If you don't understand the concepts involved and are just completing the assignments its unclear what you are gaining from this course in the first place. There is more to computer science then just getting your code to pass a test. There is understanding. It's one thing if you've programmed before and are just learning the C language. But that doesn't seem like the case here or you wouldnt have spent 4 hours on this.

That aside it doesnt sound like you have done any effective debugging. What did you even try to debug? It sounds like all you did was try moving functions around, which if you understand anything you've learned wont make any impact on the behavior of the code. The first thing I would have done to debug your case is to drop into the debugger and see WHY it is outputting that the size of your dictionary is 0 if it's always reporting 0, if you had done that the error would be glaringly obvious that you have an error in your size function. Alternatively adding some printouts to your size function would also have revealed a problem. The first thing I would have done is make sure my dictionary is correct by printing it out and diffing that against the input dictionary. The next thing I'd have checked is that size worked and that unload worked properly without leaking memory.

More specifically why is the existence of a node for 'cat' remotely significant as to whether or not the dictionary is empty or not? You have no code that force inserts 'cat' into the hash tables

Additionally you have another error, you don't zero initialize the elements of table and keep the uninitialized memory of the original node in your list, so it is also possible for you to enter into an infinite loop while checking or while counting the size.

Solution to both of these problems is to

1. initialize all table entries to NULL at the start of load.

for (int i = 0; i < N; i++)
{
    table[i] = NULL;
}

or you could use memset to do this.

2. when you are in size you check for each table entry if it is non null and then add the size of it. but a better solution as pointed out by Dino is again to count the words as you insert them so you don't spend the time here. for completeness:

int count = 0;
for (int i = 0; i < N; i++)
{
    if ( table[i] != NULL )
    {
         node *cur = table[i];
         while (cur != NULL)
         {
             count++;
             cur = cur->next;
         }
    }
    return count;
}

Note however that key this is alteration of your load function:

ptr->next = table[h_idx];
table[h_idx] = ptr;

should become

ptr->next = NULL
if ( table[h_idx != NULL ) {
    ptr->next = table[h_idx];
}
table[h_idx] = ptr;

There is still a LOT of room for improvement here. Reading a letter at a time is very slow, Disk I/O is slow in general. see if you can read a line at a time or a word at a time. And you haven't explained your hashing logic at all which is generally a good idea to do.

I noticed that when you check you convert words to lower case first, which I think is a smart idea so you dont have to use strcasecmp, but given that why not convert dictionary words to lower case also and then you can remove the tolower call from the hash function and speed up the hash function?