// Arup Guha
// 4/26/2019
// Solution to questions 1-10 for the 2019 Spring COP 3502H Final Exam

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

typedef struct word {
    char* str;
    int len;
    int score;
} word;

#define MAX 100
#define ALPHASIZE 26

// Easier to maintain this globally due to how we read in the dictionary of words.
int numWords;

void printResults(char* rack, word** list);
word** getWordList(FILE* ifp);
void sort(word** words, int length);
int cmp(const word* w1, const word* w2);
int contains(const char* letters, const word* item);
void setScore(word* item);
int* getFreq(const char* letters);
void print(const word* item);
char* rndLetters(int n);
void freeWordList(word** list, int len);

int main(void) {

    // Get the file name.
    char filename[MAX];
    printf("Enter the file with your dictionary of valid words.\n");
    scanf("%s", filename);

    // Load in the words.
    FILE* ifp = fopen(filename, "r");
    word** mywords = getWordList(ifp);
    fclose(ifp);

    // Sort the words in the order specified.
    sort(mywords, numWords);

    int i, numLet;
    printf("How many letters do you want for the game?\n");
    scanf("%d", &numLet);

    char* rack = rndLetters(numLet);
    printf("The letters you got this round are %s.\n", rack);
    printResults(rack, mywords);
    free(rack);
    freeWordList(mywords, numWords);
    return 0;
}

// Prints the sorted results that can be formed with the letters in rack out of the words
// in the list pointed to by list. Results are sorted by score (greatest to least) and then
// ties are broken in alphabetical order. The pre-condition is that list must already be sorted
// in this manner.
void printResults(char* rack, word** list) {
    int listNo = 1, i;

    // Just go through the word list in order.
    for (i=0; i<numWords; i++) {

        // See if we can make this word.
        if (contains(rack, list[i])) {

            // Print the ranklist number.
            printf("%d. ", listNo);

            // Then the item itself.
            print(list[i]);

            // Update the ranklist number for next time.
            listNo++;
        }
    }
}

// Reads the word list from ifp and returns an pointer to an array
// of pointers to words.
word** getWordList(FILE* ifp) {

    // Get the number of words.
    int i;
    fscanf(ifp, "%d", &numWords);

    // Allocate space for the array of pointers.
    word** list = malloc(numWords*sizeof(word*));

    // Go through each word.
    for (i=0; i<numWords; i++) {

        // Allocate space for this word.
        list[i] = malloc(sizeof(word));

        // Read it in.
        char tmp[MAX];
        fscanf(ifp, "%s", tmp);

        // Update the length and allocate the correct size of space for the string.
        list[i]->len = strlen(tmp);
        list[i]->str = malloc((list[i]->len+1)*sizeof(char));

        // copy in the string and set up its score.
        strcpy(list[i]->str, tmp);
        setScore(list[i]);
    }

    // Return the pointer to the array.
    return list;
}

// bubble sorts the array words of length length according to the problem specification.
void sort(word** words, int length) {
    int i, j;

    // i represents how far this pass goes.
    for (i=length-1; i>=0; i--) {

        // we go forward through successive elements in words.
        for (j=0; j<i; j++) {

            // See if these two consecutive items are out of order, if so, swap.
            if (cmp(words[j], words[j+1]) > 0) {
                word* tmp = words[j];
                words[j] = words[j+1];
                words[j+1] = tmp;
            }
        }
    }
}

// Returns a negative integer if the struct pointed to by w1 comes before the
// struct pointed to by w2, 0 if they are 0, and positive integer otherwise.
int cmp(const word* w1, const word* w2) {

    // Score matters most, if they aren't equal, sort most to least score.
    if (w1->score != w2->score)
        return w2->score - w1->score;

    // For equal scores, we sort in ascending alphabetical order.
    return strcmp(w1->str, w2->str);
}

// Set the score field of the struct pointed to by item.
void setScore(word* item) {
    int i;

    // First set the score to 0.
    item->score = 0;

    // Go through each character, applying the formula given.
    for (i=0; i<item->len; i++)
        item->score += (abs(i-(item->str[i]-'a')));
}

// Returns true iff letters can form all the letters in item.
int contains(const char* letters, const word* item) {

    // First get frequency arrays for both the word we are trying to form pointed to by item
    // and our rack of tiles (letters).
    int* fLetters = getFreq(letters);
    int* iLetters = getFreq(item->str);

    int i, retval = 1;

    // Now, if we ever don't have enough of a letter, we can't form the word. Just note this.
    for (i=0; i<ALPHASIZE; i++)
        if (fLetters[i] < iLetters[i])
            retval = 0;

    // Must free these arrays before returning!!!
    free(fLetters);
    free(iLetters);

    // Now it's safe to return.
    return retval;
}

// Returns the frequency array of the letters in letters.
int* getFreq(const char* letters) {

    // Allocate memory for frequency array and set to 0.
    int* freq = calloc(ALPHASIZE, sizeof(int));
    int i, len = strlen(letters);

    // Go through each letter in letters and update the frequency array.
    for (i=0; i<len; i++)
        freq[letters[i]-'a']++;

    // Return the frequency array.
    return freq;
}

// Prints the word and score for the struct pointed to by item.
void print(const word* item) {
    printf("%s: %d\n", item->str, item->score);
}

// Returns a string of n lowercase random letters.
char* rndLetters(int n) {

    // Allocate space for n letters and the null character.
    char* res = malloc((n+1)*sizeof(char));
    int i;

    // Fill in random letters.
    for (i=0; i<n; i++)
        res[i] = (char)(rand()%26+'a');

    // Then the null character and return!
    res[n] = '\0';
    return res;
}

// Frees add data pointed to by list, which is of length len.
void freeWordList(word** list, int len) {
    int i;

    // First free each individual string.
    for (i=0; i<len; i++) {
        free(list[i]->str);
        free(list[i]);
    }
    // Now free the array.
    free(list);
}