CS50 Speller Solution

dictionary.c

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <math.h>

#include "dictionary.h"

// make count_words a global variable
// it may be called in size();
unsigned int count_words = 0;

// Prototypes
unsigned int size(void);

// 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
// N = 26 this is A to Z
const unsigned int N = 20000;

// Hash table
// a hash table is an array of linked lists
node *table[N]; // * points to the first address

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // TODO
    // traverse the linked list searching for a matching word
    // word index position
    int word_index = hash(word);

    // initialize cursor to first node in the linked list
    // note cursor->word is current word
    // note cursor->next is a pointer to the next node address
    node *cursor = table[word_index];

    // while loop to iterate until NULL
    // NULL is the one with no pointer
    while (cursor != NULL)
    {
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true; // word is found
        }
        // set the cursor to the next node in the linked list
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO: Improve this hash function
    // consider a function on each character in a word to insurace uniqueness however will output fit in N-1?
    // to fit N do module % N
    // output is the address in the linked list
    //return toupper(word[0]) - 'A';

    // new hash function
    // loop over each character in the string
    // square the uppe case ASCII number, sum each squared ASCII number and mod N
    // mid word perform another function
    unsigned int roll_sum = 0;
    unsigned int squared = 0;
    for (int i = 0; i < strlen(word); i++)
    {
        squared = pow(toupper(word[i]), 2);
        if (i == round(strlen(word) / 2))
        {
            roll_sum = roll_sum + round(sqrt(roll_sum)) + 17;
        }
        roll_sum = squared + roll_sum + 47;
    }
    return roll_sum % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // TODO
    // add a method to sum the words as loading into dictionary
    // Open the dictionary file
    FILE *dict_open = fopen(dictionary, "r"); // pointer to the memory address of the input file
    //printf("pointer to memory address of the memory card %p \n", input_memory_card);
    if (dict_open == NULL)
    {
        printf("Could not open the dictionary file.\n");
        return false;
    }
    else if (dict_open != NULL)
    {
        char buffer[LENGTH + 1];
        int hash_index = 0;
        while (fscanf(dict_open, "%s", buffer) != EOF)
        {
            //printf("yee %s \n",buffer);

            // Create a new node for the word the size of the node
            // enough bytes for the word itselt and the address
            node *n = malloc(sizeof(node));
            // check that the memory initialized ok
            if (n == NULL)
            {
                return false;
                break;
            }
            else if (n != NULL)
            {
                // copy the word into the word portion of the node
                strcpy(n->word, buffer);
                // set address to NULL
                n->next = NULL;

                // testing the hash function
                //printf("testing hash function %i \n", hash(buffer));

                // get the hash number
                hash_index = hash(buffer);

                // case 1 - the first entry
                // if nothing is there equal the first entry to the new node
                if (table[hash_index] == NULL)
                {
                    table[hash_index] = n;
                }
                // case 2 - an entry already exists
                // inserts at the front of the linked list each time
                else if (table[hash_index] != NULL)
                {
                    // set the new node address to the first element index position
                    n->next = table[hash_index];
                    // set the head of the linked list to the previously inserted node
                    table[hash_index] = n;
                }

                // count words
                count_words++;
            }
        } // end while loop
        fclose(dict_open);
        return true;
    }
    else
    {
        return false;
    }
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    // TODO
    // tmp and curosr method move cursor->cursor->next. free temp.. cursor->next...NULL
    // loop along the index positions
    for (int i = 0; i < N; i++)
    {
        // set temp and cursor to first index position
        node *temp = table[i];
        node *cursor = table[i];
        
        // at each index position
        // traverse the linked list at that index position and free - use temp/cursor
        // while loop until NULL
        // at that point next i will begin
        while (temp != NULL)
        {
            // set cursor to next
            cursor = cursor->next; // i+1
            free(temp);
            temp = cursor;
        }
    }
    return true;
}

This is a trivial problem. Framed to make you think. One mistakes in above code is: unnecessary toupper() conversions in the hot path, namely function hash(). Instead convert tolower() once and only where needed. Make sure all calls to hash() are lowercase.

In load() conversions are not necessary because the specification guarantees lowercase.

If you convert the input to check() to lowercase before you call check() no other case conversions need to be done.

if you cannot modify the input to check(), the make sure that inside check() before the call to hash() the input is lowercase.

Hope this helps.

regards Bran