Spaces:
Sleeping
Sleeping
Download training_programs/128_trie_autocomplete.c from HideIron/compiler-env: direct link, hf CLI and curl.
- Browser
- Download file 4.95 kB
-
https://huggingface.co/spaces/HideIron/compiler-env/resolve/main/training_programs/128_trie_autocomplete.c
- Command line
-
hf download hf://spaces/HideIron/compiler-env/training_programs/128_trie_autocomplete.c
-
curl -L -o 128_trie_autocomplete.c https://huggingface.co/spaces/HideIron/compiler-env/resolve/main/training_programs/128_trie_autocomplete.c
4.95 kB
| // Trie with autocomplete functionality | |
| // Efficient prefix-based word search and suggestion | |
| typedef struct TrieNode { | |
| struct TrieNode *children[ALPHABET_SIZE]; | |
| int is_end_of_word; | |
| int word_count; // Number of words with this prefix | |
| } TrieNode; | |
| TrieNode* create_node() { | |
| TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode)); | |
| node->is_end_of_word = 0; | |
| node->word_count = 0; | |
| for (int i = 0; i < ALPHABET_SIZE; i++) { | |
| node->children[i] = NULL; | |
| } | |
| return node; | |
| } | |
| void insert_word(TrieNode *root, const char *word) { | |
| TrieNode *curr = root; | |
| for (int i = 0; word[i] != '\0'; i++) { | |
| int index = word[i] - 'a'; | |
| if (index < 0 || index >= ALPHABET_SIZE) continue; | |
| if (!curr->children[index]) { | |
| curr->children[index] = create_node(); | |
| } | |
| curr = curr->children[index]; | |
| curr->word_count++; | |
| } | |
| curr->is_end_of_word = 1; | |
| } | |
| int search_word(TrieNode *root, const char *word) { | |
| TrieNode *curr = root; | |
| for (int i = 0; word[i] != '\0'; i++) { | |
| int index = word[i] - 'a'; | |
| if (index < 0 || index >= ALPHABET_SIZE || !curr->children[index]) { | |
| return 0; | |
| } | |
| curr = curr->children[index]; | |
| } | |
| return curr->is_end_of_word; | |
| } | |
| int count_words_with_prefix(TrieNode *root, const char *prefix) { | |
| TrieNode *curr = root; | |
| for (int i = 0; prefix[i] != '\0'; i++) { | |
| int index = prefix[i] - 'a'; | |
| if (index < 0 || index >= ALPHABET_SIZE || !curr->children[index]) { | |
| return 0; | |
| } | |
| curr = curr->children[index]; | |
| } | |
| return curr->word_count; | |
| } | |
| void collect_words(TrieNode *node, char *prefix, int depth, char results[][MAX_WORD_LEN], int *count, int max_results) { | |
| if (*count >= max_results) return; | |
| if (node->is_end_of_word) { | |
| prefix[depth] = '\0'; | |
| strcpy(results[*count], prefix); | |
| (*count)++; | |
| } | |
| for (int i = 0; i < ALPHABET_SIZE; i++) { | |
| if (node->children[i]) { | |
| prefix[depth] = 'a' + i; | |
| collect_words(node->children[i], prefix, depth + 1, results, count, max_results); | |
| } | |
| } | |
| } | |
| int autocomplete(TrieNode *root, const char *prefix, char results[][MAX_WORD_LEN], int max_results) { | |
| TrieNode *curr = root; | |
| // Navigate to prefix node | |
| for (int i = 0; prefix[i] != '\0'; i++) { | |
| int index = prefix[i] - 'a'; | |
| if (index < 0 || index >= ALPHABET_SIZE || !curr->children[index]) { | |
| return 0; | |
| } | |
| curr = curr->children[index]; | |
| } | |
| // Collect words | |
| char word_buffer[MAX_WORD_LEN]; | |
| strcpy(word_buffer, prefix); | |
| int count = 0; | |
| collect_words(curr, word_buffer, strlen(prefix), results, &count, max_results); | |
| return count; | |
| } | |
| void free_trie(TrieNode *node) { | |
| if (!node) return; | |
| for (int i = 0; i < ALPHABET_SIZE; i++) { | |
| if (node->children[i]) { | |
| free_trie(node->children[i]); | |
| } | |
| } | |
| free(node); | |
| } | |
| void generate_word(char *word, int len) { | |
| static unsigned int seed = 42; | |
| for (int i = 0; i < len - 1; i++) { | |
| seed = seed * 1103515245 + 12345; | |
| word[i] = 'a' + (seed % 26); | |
| } | |
| word[len - 1] = '\0'; | |
| } | |
| int main() { | |
| TrieNode *root = create_node(); | |
| // Generate and insert words | |
| char **words = (char**)malloc(NUM_WORDS * sizeof(char*)); | |
| for (int i = 0; i < NUM_WORDS; i++) { | |
| words[i] = (char*)malloc(MAX_WORD_LEN); | |
| int len = 3 + (i % 10); | |
| generate_word(words[i], len); | |
| insert_word(root, words[i]); | |
| } | |
| clock_t start = clock(); | |
| int total_suggestions = 0; | |
| char results[10][MAX_WORD_LEN]; | |
| for (int q = 0; q < NUM_QUERIES; q++) { | |
| // Random prefix query | |
| int word_idx = q % NUM_WORDS; | |
| int prefix_len = 1 + (q % 4); | |
| char prefix[MAX_WORD_LEN]; | |
| strncpy(prefix, words[word_idx], prefix_len); | |
| prefix[prefix_len] = '\0'; | |
| int count = autocomplete(root, prefix, results, 10); | |
| total_suggestions += count; | |
| } | |
| clock_t end = clock(); | |
| double time_spent = (double)(end - start) / CLOCKS_PER_SEC; | |
| printf("Trie autocomplete: %d words, %d queries, %.6f seconds\n", | |
| NUM_WORDS, NUM_QUERIES, time_spent); | |
| printf("Average suggestions per query: %.2f\n", total_suggestions / (double)NUM_QUERIES); | |
| for (int i = 0; i < NUM_WORDS; i++) { | |
| free(words[i]); | |
| } | |
| free(words); | |
| free_trie(root); | |
| return 0; | |
| } | |