Specification:
Essentially, the goal is to see if a word is in a dictionary in the fastest possible real-world time. When actually tested for speed, my program finished in 10th place out of 700 Harvard students; 20th if you count the teaching fellows' submissions.
My Solution:
/****************************************************************************
* dictionary.c
*
* Victor Porras
* Computer Science 50
* Problem Set 5
*
* Implements a dictionary's functionality. * This is not the fastest version of this program, but it is the most
* extensible and elegant. I hardcoded several parts of this to make the
* BigBoard version faster, at the expense of readability and robust design.
*
* Some distribution code is necessary to compile and run this. See spec.
***************************************************************************/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include "dictionary.h"
#define LEVELS 4
// LEVEL dependent
int dict[28][28][28][28][2];
char* raw;
char** words;
char w[46];
unsigned int sz = 0;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
if (sz == 0)
return false;
// preprocessing
// since I need to mess around with the characters in word, w is a non-const copy
// char* w = (char *) malloc(sizeof(char) * (LENGTH + 1));
// preparing the word size for later
int wsz;
// this makes EvRytHing lowercase
for (wsz = 0; word[wsz] != '\0'; wsz++)
w[wsz] = tolower(word[wsz]);
// gotta null terminate!
w[wsz] = '\0';
// the first LEVELS values of w must be sequential, ie a-z then z+1 z+2, so they can be used to access arrays
bool finished = false;
for (int x = 0; x < LEVELS; x++)
{
// check for corner cases
if (w[x] == '\'')
w[x] = 'z' + 1;
if (w[x] == '\0' || finished)
{
w[x] = 'z' + 2;
finished = true;
}
w[x] -= 'a';
}
if (finished)
w[LEVELS] = '\0';
// LEVEL dependent
// time for binary search
int bottom = dict[(int) w[0]][(int) w[1]][(int) w[2]][(int) w[3]][0];
int top = dict[(int) w[0]][(int) w[1]][(int) w[2]][(int) w[3]][1];
int result = 0;
// top is -1 when dict[...] has no pointer
while (top >= bottom)
{
result = strcmp(&(w[LEVELS]), words[(top + bottom)/2]);
if (result == 0)
return true;
if (result > 0)
bottom = (top + bottom)/2 + 1;
else
top = (top + bottom)/2 - 1;
}
return false;
}
/**
* Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char* dictionary)
{
FILE* f = fopen(dictionary, "r");
if (f == NULL)
return false;
// LEVEL dependent
// sets up all the tops with -1
for (int i = 0; i < 28; i++)
for (int j = 0; j < 28; j++)
for (int k = 0; k < 28; k++)
for (int l = 0; l < 28; l++)
dict[i][j][k][l][1] = -1;
// gets the file size then allocates memory for it
struct stat st;
stat(dictionary, &st);
unsigned long fsz = st.st_size;
raw = (char*) malloc(fsz);
// it's much faster to read the data in one huge block than in many separate pieces
fread(raw, sizeof(char), fsz, f);
// sets up the data structures to hold the words themselves
int capacity = 262144;
words = malloc(sizeof(char*) * capacity);
// breaks the raw data into words
char* word = strtok(raw, "\n");
// LEVEL dependent
// This will store the first LEVELS letters of the previous word so the indices can be quickly found for similar words
char old[LEVELS*2] = {27, 27, 27, 27};
// makes sure the file is not over
while (word != NULL)
{
// check if words[] is too big
// this runs in amortized linear time
if (sz == capacity)
{
capacity *= 2;
words = realloc(words, sizeof(char*) * capacity);
}
if (strncmp(word, old, LEVELS))
{
strncpy(old, word, LEVELS);
bool finished = false;
for (int x = 0; x < LEVELS; x++)
{
// check for corner cases
if (word[x] == '\0' || finished)
{
old[LEVELS + x] = 27;
finished = true;
}
else if (word[x] == '\'')
old[LEVELS + x] = 26;
else
// put the indices in old
old[LEVELS + x] = word[x] - 'a';
}
// set the bottom of the binary search range
dict[(int) old[LEVELS]][(int) old[LEVELS+1]][(int) old[LEVELS+2]][(int) old[LEVELS+3]][0] = sz;
}
// truncate the word to the part after the indices
int wsz = strlen(word) - LEVELS;
if (wsz <= 0)
*word = '\0';
else
word = &(word[LEVELS]);
// put word into the master array
words[sz] = word;
// set the top of the binary search range
dict[(int) old[LEVELS]][(int) old[LEVELS+1]][(int) old[LEVELS+2]][(int) old[LEVELS+3]][1] = sz;
sz++;
// get the next word
word = strtok(NULL, "\n");
}
fclose(f);
return true;
}
/**
* Returns number of words in dictionary if loaded else 0 if not yet loaded.
*/
unsigned int size(void)
{
return sz;
}
/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
// makes sure that the memory has been malloc'd
if (raw == NULL)
return false;
// frees the big arrays that actually hold the values
free(words);
free(raw);
return true;
}
