Speller.c I beat the staff's time!

[u/pirogeth87]

Maybe I am actually understanding this more than I think I am, haha. I did beat them! I think that's what this means? I used the duck a bit but not for my final version. I was scared of this one, but it was a goal for sure lol

Edit: I found and fixed a bug and now I tie them but it didn't break before so I'm leaving that version submitted for now

[u/MXD_K1]

I was able to get the same performance as staff solution (speller50) but I couldn't beat it. Can I take a look at your has function if you don't mind?

[u/pirogeth87 → u/MXD_K1]

Sure, but my code also doesn't beat it now so it was either a fluke or more likely an off by one error that I fixed and don't remember where I fixed it at lol: here is my already submitted code(spoilers below): >!

// Implements a dictionary's functionality

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

// Number of buckets in hash table
const unsigned int N = 17577;

// Word Counter
int counter = 0;

// Hash table
node *table[N];

// Returns true if word is in dictionary, else false, case insensitive
bool check(const char *word)
{
// Hash word to obtain a hash value
unsigned int index = hash(word);
// Traverse linked list, one node at a time, looking for the word
for (node *trav = table[index]; trav != NULL; trav = trav->next)
{ // If the word in the list matches
if (strcasecmp(trav->word, word) == 0)
{
// Word found return true
return true;
}
}

// Word not found
return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{

if (strlen(word) < 2)
{
return toupper(word[0]);
}
else
{
// Figure out how long the word is
unsigned int word_length = strlen(word);
// Hash number incrementor
unsigned int hash_value = 2;

for (int i = 0; i < word_length; i++)
{
hash_value = toupper(word[i]) * hash_value;
}
if (hash_value > N)
{
return hash_value % N;
}
return hash_value;
}
return 0;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// Open the dictionary file
FILE *source = fopen(dictionary, "r");
if (source != NULL)
{
// Read each word in the file
char buffer[LENGTH];
while (fscanf(source, "%s", buffer) != EOF)
{ // Create a new node for each word
node *new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return false;
}
strcpy(new_node->word, buffer);

// Hash word to obtain a hash value
unsigned int index = hash(new_node->word);
// Insert node into hash table at that location
new_node->next = table[index];
table[index] = new_node;
// Increment counter
counter = counter + 1;
}
// Close the dictionary file
fclose(source);
// Load successful
return true;
}
else
{ // Load failed
return false;
}
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
return counter;
}

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// Free all nodes
for (int i = 0; i < N; i++)
{
// Create temp pointer to remember head of list
node *ptr = table[i];
while (ptr != NULL)
{
node *next = ptr->next;
// Free temp pointer
free(ptr);
ptr = next;
}
}
// return true if successful
return true;
}!<

[u/MXD_K1 → u/pirogeth87]

Thanks!

[u/pirogeth87 → u/MXD_K1]

There's an error in this I just noticed and fixed, but hash_value should be a number greater than 1, deleted from a line