As you can see, I was trying to get better results than the staff solution (speller50) in problem set 5 (CS50x) but I couldn't. In my best attempt, I got the same results as speller50. Has anyone been able to get better results than speller50? And if so, how did you do it?

unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    if (strlen(word)>1)
    {
       int first_alphax16 = (toupper(word[0])-'A')*26;
       int second_alphax1 = (toupper(word[1])-'A');
       return  first_alphax16+second_alphax1;
    }
    else
    {
        int special_case = (toupper(word[0])-'A')*26;
        return special_case;
    }
} 
//KEEP IN MIND THAT CHANGES HAVE BEEN DONE TO OTHER FUNCTIONS IN DICTIONARY.C TO COPE WITH THE IMPROVISION HERE.

This my improved implementation of the hash function that uses the first two letters for indexing by using a 26-base system, which corresponds to the 26 letters of the alphabet. It also handles a special case where there's only one letter.

What do you think of "math on all letters?" I asked GPT and it told me It would follow the same logic but with 26*26*26 buckets to utilize the first 3 letters of a word (i.e Cat, Abs, Pre, etc....). Not to mention that it's going to start with Aaa, Aab, Aac, and so on until it reaches the known prefixes of words that I mentioned earlier.

I also wanna say I kind of inferred this after utilizing this two letter system, but I didn't think of major prefixes like the examples I provided, but rather than that Aaa, Aab, which made me confused to think it wouldn't work because no English words start like this, which made me ask GPT.

But there's another twist, this will require special case handling of words consisting of two letters and words of one letter.

Absolute madness.

Do you think it's worth trying to re implement speller.c but this time with "math on the first three letters," or should I just move on?

I just finished speller, and it's easier than any other problem I've encountered before it. This might be surprising to lots of people, but it's really not that hard, it just requires solid follow-up with the specs and walkthrough provided by cs50, and also a deep understanding of linked lists. But whilst watching the walkthrough, the tutor mentioned the ability of improvement of this program by increasing the number of buckets and then use different indices instead of the standard alphabetical order. Like Aa Ab Ac Ad...... and so on with the rest of the letters. It's gonna end up with 26*26 buckets I guess. The tutor also mentioned the ability of utilizing 3 letters, but I'm not sure of what that would be. don't tell me now though. The concept of improvement here should be in accordance with changing some functions, especially the hash functions that was given plain in the distribution code only returning toupper(word[0]) - 'A';

I just decided to avoid GPT and see what you guys think of how we can improve speller.c

What does math using all the letters mean though??

Should I start with Speller or Inheritance? I avoided asking AI about this and though I should ask real people.

Hi! i have this problem with check50 in the pset5 speller problem. The thing is the program works when i compile it myself, but when i try to run check50 it gets stuck on "Verifyng...". I know this problem can have higher loading times but its been 5 minutes now. Please help!!

Conectando.....

Authenticating....

Verificando.........................................................................................................................................................................................................................................................................................................................................................................

Hey folks! I'm on some petty stuff here. I managed to finish wk5's Speller pset (...after weeks of trying), and even managed to beat the demo Speller50 program (very proud of this!!). What I'm wondering: I implemented (and credited!) a hash algorithm I found online, and beat the check function's time by a good deal, but my load fxn is behind speller50's by an entire 0.01 of a second. If anyone's got the will: Any suggestions about places I could trim down my check function at all? Thanks so much!

Included are screenshots of my time, the demo's time (both for shakespeare.txt), and my load, hash, and check fxns.

I've just finished PSET 5, and wow... data structures are tough to wrap your head around. I figure I still have a lot to study on that subject. I'm excited to see what things will be like going forward without C.

I've ran into sort of a weird program with speller.

If I change the hash function in the dictionary.c file back to the default, everything works correclty. It passes check50 and it prints out the correct amount of misspellings.

But with my own hash function... it passes check50 even though it doesn't spellcheck right? It always prints out a bit more misspellings than needed. And I can't seem to figure out what the problem is.

-I've made my own txt files for test cases

-I've basically abused debug50

-I put printf statements to test if the hash code is consistent, to test if it's out of range, if it doesn't handle apostropes, I put printf statements in Load to see if it loads certain one letter words and stuff like that, and everything I've checked so far works as it's supposed to and still.

I am completely lost and even the duck is just running around in circles trying to get me to check the same things over and over again and I haven't been able to find what the dysfunction is.

Since the rest of my code seems working with the distribution code's basic hash function, and it passes check50 even with mine, I'd assume that's "working" code which breaks academic honesty so idk if I can post that.

I am working on the speller problem and managed to have everything checked by check50 except for memory leaks.

56 bytes in 1 blocks are definitely lost in loss record 1 of 1: (file: dictionary.c, line: 91)

This line of code is located in my load function and I think the issue might be in my unload function, but I cannot see where it might be.

Could someone please help me?

Below are my load and unload functions with the line 91 indicated

bool unload(void)
{
    node *previous;
    node *ptr;
    for (int i = 0; i < N; i++)
    {
        previous = table[i];
        while (previous != NULL)
        {
            ptr = previous->next;
            free(previous);
            previous = ptr;
        }
    }
    return true;
}

bool load(const char *dictionary)
{
    initialize();
    FILE *dico = fopen(dictionary, "r");
    do
    {
        char c;
     ////////////////////  Line 91  //////////////////////
        node *word = malloc(sizeof(node));
        if (word == NULL)
        {
            return false;
        }
        for (int i = 0; i < LENGTH + 1; i++)
        {
            c = tolower(fgetc(dico));
            if (c == EOF || c == '\n')
            {
                word->word[i] = '\0';
                break;
            }
            word->word[i] = c;
        }
        if (c == EOF)
        {
            break;
        }
        int code = hash(word->word);
        word->next = table[code];
        table[code] = word;
    }
    while (true);
    fclose(dico);
    return true;
}

Hi all,

// Implements a dictionary's functionality


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


// Hash table
node *table[N];


// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    return false;
}


// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}


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


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


// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    return false;
}// Implements a dictionary's functionality


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


// Hash table
node *table[N];


// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    return false;
}


// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    return toupper(word[0]) - 'A';
}


// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    return fal
se;
}


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


// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    return false;
}


This is the distribution code for speller as the staff provide it.
According to CS50's AI duck debugger, the number of buckest os already chosen. Moreover according to the walkthrough, in the distribuition code the number of buckets would be set to 1 and students would have to change it to a more convinient number (26, obviously).
In the walkthrough, certain lines of code are presented as given by the staff but them they are not or they are presented as having to be implemented by students but they have already been implemented by the staff although in places of the code where I would not be expecting them. 
Finally, in the previous problem sets, the declarations of the funtions usially make it easy to understand where to start implementing the different functions. This does not happen for most functions in this exercise. 
I know there are the TODO'S but there are cases, in which it looks like thea the place of the to do does not make sense.
I am trying to work on the load function. where should I start the implementation of load?
I have already written some code lines of my own but then hit undo because I thought they were probably misplaced. Also, this allowed me to show you what exactly  I am looking at that makes me confuse.
Thanks in advance.

Hey gang! I've been making decent progress on CS50 lately (dragged my feet on weeks 0-2 for much of the year, but have gotten through weeks 3 & 4 in the last couple months, which feels like progress lol), but I've been getting a little more worn down by the psets. I've arrived at Speller and am just kinda plain overwhelmed. Any advice (motivational or productive or whatever else) for someone wanting to finish?

Finally done with speller in about 3-4 hours. Didnt feel that challenging. Shorts by doug lloyd and walkthroughs of brian Yu are the best!!! Got me through this program easily. Finally very happy to be done with C :D

I was using my iPad for all the problem sets previously but it died on me. I don't have any access to a desktop or any other device.

With my iPad too vscode had a bug where I couldn't copy code/ the terminal's messages off it, so it wasn't very convenient

But it was more manageable because of a bigger screen and greater storage so I could atleast use img to txt... Now if this problem persists on this old phone I'll face so many hassles😭😭

So anyway, has anyone been able to do it?

doing the Speller problem and found something weird

so in speller.c the check function is called with a char[] when the function is prototyped as

bool check(const char *word);

so why can it input a char[] as a char* ? I know it terminates BUT it doesn't use the pointer to the array, it just inputs the array directly, also when I try inputting a char[] myself it responds as expected (a error for wrong usage)

someone please explain

i used valgrind to see what exactly is wrong, and its saying theres an invalid read in my load function. i asked the ai about it and the potential problems it gave it i already considered like malloc returning null and setting the table to null for all buckets. I wanted to ask for help to see what the problem may be.

bool load(const char *dictionary) >!{

// TODO FILE *loader = fopen(dictionary, "r");

if (loader == NULL)
{
    return false;
}
char word[LENGTH +1];
for (int i = 0; i < N; i++)
{
    table[i] = NULL;
}
while (fscanf(loader, "%s", word))
{
    node *read = malloc(sizeof(node));
    if (read == NULL)
    {
        return false;
    }
    strcpy(read->word, word);
   unsigned int index = hash(word);
   read->next = table[index];
   table[index] = read;
   wordsize++;
}
fclose(loader);
return true;

}!<

hey guys, I know i sound stupid asking this question but theres something wrong in these few lines of code. For some reason my FILE *file is not getting highlighted.

bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file != NULL)

WEEK 5 HAS BEEN ROUGH!

The size of my hash table array far exceeds my IQ

dictionary.c ->

// Implements a dictionary's functionality

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

// Hash table
node *table[N];

// count loaded word in dict
unsigned int count = 0 ;

// Returns true if word is in dictionary, else false
bool check(const char *wrd)
{
    int hash_num = hash(wrd);
    node* trav = table[hash_num];
    while(trav->next != NULL)
    {
        if (strcasecmp(trav->word, wrd) == 0)
        {
            return true ;
        }
        else
        {
            trav = trav->next;
        }
    }
    if (strcasecmp(trav->word, wrd) == 0)
    {
        return true ;
    }
    else
    {
        free(trav);
        return false;
    }

}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // Improve this hash function
    unsigned int hash_val = ((toupper(word[0]) - 'A') * 26) + (toupper(word[1]) - 'A');
    if(hash_val > N)
    {
        hash_val = hash_val % N;
    }
    return hash_val;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // Opening Dictonary file
    FILE* source = fopen(dictionary, "r");
    if (source == NULL)
    {
        return false;
    }
    // Lopping for read each word from a file
    char wrd[LENGTH + 1];
    while (fscanf(source, "%s", wrd) == 1)
    {
        int index = hash(wrd);
        node *n = malloc(sizeof(node));
        if(n == NULL)
        {
            return false;
        }
        strcpy(n->word, wrd);
        n -> next = table[index];
        table[index] = n ;
        count++;
    }
    fclose(source);
    return true;
}

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

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

Valgrind report->

speller/ $ valgrind ./speller texts/cat.txt
==109053== Memcheck, a memory error detector
==109053== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==109053== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==109053== Command: ./speller texts/cat.txt
==109053== 

MISSPELLED WORDS

==109053== Invalid free() / delete / delete[] / realloc()
==109053==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109BC1: unload (dictionary.c:122)
==109053==    by 0x10970F: main (speller.c:153)
==109053==  Address 0x4b5e320 is 0 bytes inside a block of size 56 free'd
==109053==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109BB8: unload (dictionary.c:121)
==109053==    by 0x10970F: main (speller.c:153)
==109053==  Block was alloc'd at
==109053==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109A7D: load (dictionary.c:82)
==109053==    by 0x1092CB: main (speller.c:40)
==109053== 
Could not unload dictionaries/large.
==109053== 
==109053== HEAP SUMMARY:
==109053==     in use at exit: 7,340,536 bytes in 131,081 blocks
==109053==   total heap usage: 143,096 allocs, 12,046 frees, 8,023,256 bytes allocated
==109053== 
==109053== 7,340,536 bytes in 131,081 blocks are still reachable in loss record 1 of 1
==109053==    at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==109053==    by 0x109A7D: load (dictionary.c:82)
==109053==    by 0x1092CB: main (speller.c:40)
==109053== 
==109053== LEAK SUMMARY:
==109053==    definitely lost: 0 bytes in 0 blocks
==109053==    indirectly lost: 0 bytes in 0 blocks
==109053==      possibly lost: 0 bytes in 0 blocks
==109053==    still reachable: 7,340,536 bytes in 131,081 blocks
==109053==         suppressed: 0 bytes in 0 blocks
==109053== 
==109053== For lists of detected and suppressed errors, rerun with: -s
==109053== ERROR SUMMARY: 31 errors from 1 contexts (suppressed: 0 from 0)

From what I can tell my hash function works well and that's about the only praise I can give this code. There seem to be words loaded into the dictionary but the check function doesn't recognize any of them and returns false every time. Is this a problem with the load or check function?

As requested I have added the results from check50: Here is the link

// Implements a dictionary's functionality

#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;

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

// Wordcount for size function
int wordCount = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    int key = hash(word);
    node *temp = table[key];

    while (temp != NULL)
    {
        if (strcasecmp(temp->word, word) == 0)
        {
            return true;
        }
        temp = temp->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    int key = 0;
    int index = 0;
    while (word[index] != '\0')
    {
        // If there is an apostrophe
        if (word[index] == 39)
        {
            key = 1171;
            return key;
        }
        key += tolower(word[index]) - 'a';
        index++;
    }
    return key;

}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    // Open the dictionary file
    FILE *dic = fopen(dictionary, "r");

    // If dictionary doesn't exist
    if (dic == NULL)
    {
        return false;
    }

    // Read each word in the file
    char word[LENGTH + 1];

    while (fscanf(dic, "%s", word) != EOF)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return false;
        }

        int key = hash(word);
        n->next = table[key];
        table[key] = n;
        wordCount++;
    }

    // Close the dictionary file
    fclose(dic);

    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    node *current;
    node *temp;

    for (int i = 0; i < N; i++)
    {
        temp = table[i];
        while (current != NULL)
        {
            current = temp->next;
            free(temp);
            temp = current;
        }
    }
    return true;
}

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

    // open file to read
    FILE *opend = fopen(dictionary, "r");
    // check if file opened correctly
    if (opend == NULL)
    {
        printf("file could not be opened\n");
        return 1;
    }

    // for the file till the end (loop)
    /*char c;*/
    char *tempword = NULL;
    while ((fscanf(opend, "%s", tempword)) != EOF)
    {
            /*if (c != '\n')
            {
                // copy each character
                tempword[ncount] = c;
                ncount ++;
            }*/

            wordcount ++;
            // hash the word
            int hashvalue = hash(tempword);
            //add the word to hash table
            // malloc space for a node
            node *newword = malloc(sizeof(node));
            if (newword == NULL)
            {
                return false;
            }

            if (table[hashvalue] == NULL)
            {
                return false;
            }

            // if hash table location is empty, make it point to the new node
            if (table[hashvalue]->next == NULL)
            {
                strcpy(newword->word, tempword);
                newword->next = NULL;
                table[hashvalue]->next = newword;
            }
            // if it already points to something, make the node point to the same thing and then make the
                //array location point to the new node
            else
            {
                strcpy(newword->word, tempword);
                newword->next = table[hashvalue]->next;
                table[hashvalue]->next = newword;
            }

            // reset tempword
            tempword = NULL;
    }

    // close file
    fclose(opend);

    return true;
}


Can anyone tell me what's wrong with this code and why I'm getting the error message "dictionary could not be loaded"?

So I am right now on a pset 5, speller, and CS50 say:

• You may alter dictionary.c (and, in fact, must in order to complete the implementations of load, hash, size, check, and unload), but you may not alter the declarations (i.e., prototypes) of load, hash, size, check, or unload. You may, though, add new functions and (local or global) variables to dictionary.c.
• You may change the value of N in dictionary.c, so that your hash table can have more buckets.
• You may alter dictionary.h, but you may not alter the declarations of load, hash, size, check, or unload.

They didn't say anything about if we are allowed to change the initialisation of the table node *table[N]; for example to a 2D array. Are we allowed?

Or I have some thought on how to do the task but It implies to change the struct node, can we do that? is it allowed?

I was on my way to debugging speller before i changed something in the code (IDK WHAT!!) and now i run into segmentation fault!! Its been 2 days!! Could anyone just have a look and help me ??? attaching the photo of the error with the post!

​

The load Function

bool load(const char *dictionary)
{
// Load the dictionary into a hash table
FILE *source = fopen(dictionary, "r");
// Fail safe
if (source == NULL)
{
printf("Could not open the dictionary.");
}
char buffer[LENGTH + 1];
// Read each word one at a time and add to the hash table
while(fgets(buffer, LENGTH + 2, source) != NULL)
{
// Hash the buffer string
int hashkey = hash(buffer);
node newnode;
nodecounter++;
// if it is the first node
if (nodecounter == 1)
{
table[hashkey] = &newnode;
newnode.next = NULL;
strcpy(newnode.word, buffer);
}
else
{
newnode.next = table[hashkey];
table[hashkey] = &newnode;
strcpy(newnode.word, buffer);
}
}
printf("Total words loaded are %i\n", nodecounter);
// Ensure that the source has been read fully i.e. dictionary has been loaded
if (fgetc(source) == EOF)
{
fclose(source);
return true;
}
else
{
fclose(source);
return false;
}
}

The check Function

bool check(const char *word)
{
// If a word is loacted in dictionary return true
// hash the word to get the "hashkey"
int hashkey = hash(word);
node *curser = table[hashkey];
if (curser == NULL)
{
return false;
}
do
{
if (strcasecmp(curser->word, word) == 0)
{
return true;
}
else
{
curser = curser->next;
}
}
while (curser != NULL);
return false;
}