1

I'm stuck on Speller... the code compiles and provides the same output as the staff solution when the output is redirected to a file, as instructed, to:

$ ./speller texts/lalaland.txt > student.txt
$ ~cs50/2019/fall/pset5/speller texts/lalaland.txt > staff.txt

However, when the output is not redirected and displayed in the terminal window (i.e. if I run $ ./speller texts/lalaland.txt), the number of words misspelled is different. How is this possible?

For example, when I run it on La La Land, in the terminal it will show

WORDS MISSPELLED:     1032
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756
TIME IN load:         0.05
TIME IN check:        0.01
TIME IN size:         0.00
TIME IN unload:       0.01
TIME IN TOTAL:        0.08

but the file output shows

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

It is also unable to get past check50

:) 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
:( 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
    expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:| program is free of memory errors
    can't check until a frown turns upside down

From check50, it looks like the program is recognizing some words as misspelled even when they shouldn't be, e.g.

**Expected Output:**
MISSPELLED WORDS

WORDS MISSPELLED:     0
WORDS IN DICTIONARY:  8
WORDS IN TEXT:        9

**Actual Output:**
MISSPELLED WORDS

The
quick
brown
fox
jumps
over
the
lazy
dog

WORDS MISSPELLED:     9
WORDS IN DICTIONARY:  8
WORDS IN TEXT:        9

Here is my code:

// Implements a dictionary's functionality
/**
 *Source of Hash function: djb2 from http://www.cse.yorku.ca/~oz/hash.html
*/

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

// Hash table
node *table[N];

// Words loaded into dictionary
int wordsLoaded = 0;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    //take word and hash to obtain a hash value
    int hashIndex = hash(word);

    //access linked list at that index in the hash table
    //set cursor pointer to head of linked list
    node *cursor = table[hashIndex];

    //traverse linked list, looking for the word (strcasecmp)

    while (cursor != NULL)
    {
        //return true if in dictionary
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }

        cursor = cursor->next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    char *lowercase = malloc((strlen(word) + 1) * sizeof(char));
    // TODO
    for (int n = 0; n < (strlen(word)); n++)
    {
       lowercase[n] = tolower(word[n]);
    }


    unsigned int hash = 5381;
    int c;

    while ((c = *lowercase++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    hash = hash % N;
    return hash;
}

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

    //check if return value is NULL, return false if unable to open
    if(input == NULL)
    {
        printf("Could not load dictionary\n");
        return false;
    }

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

    //Read strings from file one at a time

    //tmp string for current word being read
    char tmp[LENGTH + 1];

    while(fscanf(input, "%s", tmp) != EOF)
    {

        //Create a new node for each word
        node* newWordnode = malloc(sizeof(node));
        if (newWordnode == NULL)
        {
            free(newWordnode);
            return false;
        }

        strcpy(newWordnode->word, tmp);
        newWordnode->next = NULL;

         //Hash word to obtain a hash value
         int hashIndex = hash(tmp);

        //Insert node into hash table at that location
        //if no linked list at index location yet
        if (table[hashIndex] == NULL)
        {
            table[hashIndex] = newWordnode;
        }

        //if there is already a linked list, append to beginning
        else
        {
            newWordnode->next = table[hashIndex];
            table[hashIndex] = newWordnode;
        }

        //increment words loaded
        wordsLoaded++;

    }
    fclose(input);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    //iterate over hash table - iterate over each linked list
    for (int n = 0; n < N; n++)
    {
        //set cursor to first node
        node *cursor = table[n];
        node *tmp = NULL;

        //repeat for all nodes in list until cursor == NULL
        while (cursor != NULL)
        {
            tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

Apologies for the very long explanation, and any help would be greatly appreciated!

1

This is an example of how a logic error can lead to totally unpredictable behavior.

The problem lies in the hash function. Surprised? ;-)

Here's the issue. The hash function copies the word, letter by letter, to lowercase. The problem is that the code doesn't add an end of string marker, \0, to the end of lowercase. That means that the hash function continues to process the physical memory following the word until it finds random data that it interprets as the EOS marker (aka, 0x00).

Why does it happen when output to text and not to file? My best guess is that by changing the target of the output affects how memory is allocated. Redirecting to a file may be placing 0x00 after the allocated memory for lowercase, or be putting lowercase somewhere that the memory following is never used and stays as 0x00.

There's also a valgrind issue, but it's easily found and resolved. ;-)

And don't apologize for detailed analysis! It's far more useful to help diagnose an issue. I wish everyone were this thorough! :-D This is the template of how to do it!!!!! You gave an excellent, precise description, examples of commands executed and their output from those commands and from check50, and the required code! You gave everyone all the available data needed to analyze the problem!!! WELL DONE!!!!

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

3
  • That was amazingly helpful, thank you!! This is such a great community. The code worked after I fixed the loop, but I encountered a new issue after trying to resolve the valgrind issue by adding "free(lowercase);" just before return hash... I'm getting the error free(): invalid pointer Aborted (core dumped) without being able to run the code. Any thoughts...? And thank you again! – blancei Jan 13 at 4:14
  • Sure. I know exactly the problem. ;-) Hint: What is happening in your hash function to the address stored in lowercase after it's allocated but before it is freed? Do you need to maybe save something before that happens, so you can use it later? – Cliff B Jan 13 at 5:10
  • It works!!! Thank you thank you! – blancei Jan 14 at 15:49

You must log in to answer this question.

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