// Arup Guha
// 5/8/2019
// Solution to May 2019 Foundation Exam Section 1 B Question 3

/***
    Slightly Edited on May 24, 2019
    for Programming Team Learning Modules on Tries.
***/

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

typedef struct TrieNode {
    struct TrieNode *children[26];
    int numWords;
    int flag; // 1 if the string is in the trie, 0 otherwise
} TrieNode;

int countWords(TrieNode* root, int freq[]);
int printWords(TrieNode* root, int freq[], char* cur, int k);
TrieNode* init();
void insert(TrieNode* tree, char word[], int k);
int numPrefix(TrieNode* tree, char word[]);
void freeTree(TrieNode* tree);

// Frees the tree pointed to by tree.
void freeTree(TrieNode* tree) {
    int i;
    for (i=0; i<26; i++)
        if (tree->children[i] != NULL)
            freeTree(tree->children[i]);
    free(tree);
}

int countWords(TrieNode* root, int freq[]) {

    // We can always do the root.
    int res = root->flag;

    int i;

    // Try placing each tile next.
    for (i=0; i<26; i++) {

        // Either we don't have a tile, or no real word starts with this letter.
        if (freq[i] == 0 || root->children[i] == NULL)
            continue;

        // Play it.
        freq[i]--;

        // Recursively solve from the appropriate child node.
        res += countWords(root->children[i], freq);

        // Pick the tile back up.
        freq[i]++;
    }

    // Ta da!
    return res;
}

int printWords(TrieNode* root, int freq[], char* str, int k) {

    // To be safe.
    if (root == NULL) return 0;

    // We can always do the root.
    int res = root->flag;

    if (root->flag) printf("%s\n", str);

    int i;

    // Try placing each tile next.
    for (i=0; i<26; i++) {

        // Either we don't have a tile, or no real word starts with this letter.
        if (freq[i] == 0 || root->children[i] == NULL)
            continue;

        // Play it.
        freq[i]--;
        str[k] = (char)('a'+i);
        str[k+1] = '\0';

        // Recursively solve from the appropriate child node.
        res += printWords(root->children[i], freq, str, k+1);

        // Pick the tile back up.
        freq[i]++;
        str[k] = '\0';
    }

    // Ta da!
    return res;
}

TrieNode* init() {

    // Create the struct, not a word.
    TrieNode* myTree = malloc(sizeof(TrieNode));
    myTree->flag = 0;
    myTree->numWords = 0;

    // Set each pointer to NULLL.
    int i;
    for (i=0; i<26; i++)
        myTree->children[i] = NULL;

    // Return a pointer to the new root.
    return myTree;
}

int numPrefix(TrieNode* tree, char word[]) {
    if (tree == NULL) return 0;
    int i;
    for (i=0; i<strlen(word); i++) {
        if (tree->children[word[i]-'a'] == NULL) return 0;
        tree = tree->children[word[i]-'a'];
    }
    return tree->numWords;
}

void insert(TrieNode* tree, char word[], int k) {

    // Adding word to the trie at this node.
    tree->numWords++;

    // Down to the end, insert the word.
    if (k == strlen(word)) {
        tree->flag = 1;
        return;
    }

    // See if the next place to go exists, if not, create it.
    int nextIndex = word[k] - 'a';
    if (tree->children[nextIndex] == NULL)
        tree->children[nextIndex] = init();

    insert(tree->children[nextIndex], word, k+1);
}

int main() {

    FILE* ifp = fopen("dictionary.txt","r");
    int n, i;
    fscanf(ifp, "%d", &n);
    TrieNode* root = init();
    for (i=0; i<n; i++) {
        char word[100];
        fscanf(ifp,"%s", word);
        insert(root, word, 0);
    }

    // Testing out letters c, e, e, k, m, a, r
    int freq[26];
    for (i=0; i<26; i++) freq[i] = 0;
    freq[2] = 1;
    freq[4] = 2;
    freq[10] = 1;
    freq[12] = 1;
    freq[0] = 1;
    freq[17] = 1;
    char word[100];
    word[0] = '\0';
    printf("We can form %d words.\n", printWords(root, freq, word,0));

    // Test prefix code.
    printf("What prefix do you want to check?\n");
    scanf("%s", word);
    printf("There are %d words that start with %s.\n", numPrefix(root, word), word);

    freeTree(root);
    return 0;
}