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

How did you come to think about it? I find myself struggling to come up with a complete solution on my own, and I'm starting to wonder if perhaps programming is not the right path for me. Or could it be that I am just overreacting and exaggerating the situation? It's hard to tell sometimes if I'm just facing a temporary block or if this is a sign that I'm not cut out for it.

How did you come to think about it? I find myself struggling to come up with a complete solution on my own, and I'm starting to wonder if perhaps programming is not the right path for me. Or could it be that I am just overreacting and exaggerating the situation? It's hard to tell sometimes if I'm just facing a temporary block or if this is a sign that I'm not cut out for it.

@guyzilberblum I feel where you're coming from.
My friends were telling me to get into it since I took Cisco in high school but I can't seem to follow the process on some of these problems... ;{

the more problems you work on the easier it all gets, what you learn from each problem can be applied to future problems. I am reasonable at programming because of all the hours i spent stuck, writing out solutions etc etc.. it does help writing things down. If you enjoy it, stick at it. No one was born to do any of this, its all learned. you can do it my friend.

…

On Sat, Nov 2, 2024 at 2:40 PM Donovan S ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ How did you come to think about it? I find myself struggling to come up with a complete solution on my own, and I'm starting to wonder if perhaps programming is not the right path for me. Or could it be that I am just overreacting and exaggerating the situation? It's hard to tell sometimes if I'm just facing a temporary block or if this is a sign that I'm not cut out for it. @guyzilberblum <https://github.com/guyzilberblum> I feel where you're coming from. My friends were telling me to get into it since I took Sysco in high school but I can't seem to follow the process on some of these problems... ;{ — Reply to this email directly, view it on GitHub <https://gist.github.com/flare9x/a9b582970932d0323732819fc04dfc93#gistcomment-5264464> or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFTEOPHHTA7ZVCLRZCZ2S2TZ6UTBJBFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDUOJ2WLJDOMFWWLO3UNBZGKYLEL5YGC4TUNFRWS4DBNZ2F6YLDORUXM2LUPGBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFVEYTCNRRGYZTENBXU52HE2LHM5SXFJTDOJSWC5DF> . You are receiving this email because you authored the thread. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub> .

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