From 2d604d8b8a380f7f3028c234282bfdcf12f95dad Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Thu, 21 Sep 2006 01:48:46 -0700 Subject: [PATCH] Add printing to dict interface. Breakup grid prints by letter count. --- dict-impl.h | 7 --- dict.c | 142 +++++++++++++++++++++++++++++++++++++++++----------- dict.h | 19 +++++++ grid.c | 32 ++++++++---- 4 files changed, 152 insertions(+), 48 deletions(-) diff --git a/dict-impl.h b/dict-impl.h index 030df6f..78aab1c 100644 --- a/dict-impl.h +++ b/dict-impl.h @@ -53,7 +53,6 @@ void chomp (char *s); #define TRIE_FLAGS_IS_WORD (1<<0) -#define TRIE_FLAGS_SEEN (1<<1) typedef struct _trie { uint32_t flags; @@ -77,10 +76,4 @@ trie_t * trie_find (trie_t *trie, const char *word_chunk); -int -trie_print_seen (trie_t *trie, string_t *word); - -int -trie_print_unseen (trie_t *trie, string_t *word); - #endif /* _DICT_IMPL_H_ */ diff --git a/dict.c b/dict.c index 715e48f..c364cb8 100644 --- a/dict.c +++ b/dict.c @@ -180,22 +180,47 @@ trie_find (trie_t *trie, return trie; } +int +trie_count (trie_t *trie, + trie_predicate_t predicate) +{ + int i; + int count = 0; + + if ((predicate) (trie)) + count = 1; + + for (i = 0; i < 26; i++) { + if (trie->next[i] == NULL) + continue; + + count += trie_count (trie->next[i], predicate); + } + + return count; +} + int trie_print (trie_t *trie, string_t *string, - trie_predicate_t predicate) + trie_predicate_t predicate, + int length, + int min_length, + int max_length) { char c; int i; int count = 0; - if (trie->flags & TRIE_FLAGS_IS_WORD - && (predicate == NULL || predicate (trie))) + if (length >= min_length && (predicate) (trie)) { count = 1; printf ("%s ", string->s); } + if (length == max_length) + return count; + /* Loop over each element, appending the character and recursing. */ for (i = 0; i < 26; i++) { if (trie->next[i] == NULL) @@ -204,37 +229,14 @@ trie_print (trie_t *trie, c = TRIE_INDEX_TO_CHAR (i); string_append_char (string, c); - count += trie_print (trie->next[i], string, predicate); + count += trie_print (trie->next[i], string, predicate, + length + 1, min_length, max_length); string_chop (string); } return count; } -bool_t -trie_seen_predicate (trie_t *trie) -{ - return (trie->flags & TRIE_FLAGS_SEEN); -} - -int -trie_print_seen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_seen_predicate); -} - -bool_t -trie_unseen_predicate (trie_t *trie) -{ - return (! trie_seen_predicate (trie)); -} - -int -trie_print_unseen (trie_t *trie, string_t *word) -{ - return trie_print (trie, word, trie_unseen_predicate); -} - void dict_init (dict_t *dict) { @@ -329,14 +331,94 @@ dict_cursor_resolve (dict_cursor_t cursor) return &trie->flags; } -void +/* XXX: This static function pointer is really nasty and definitely + * un-thread safe. What I really want it a lambda so I can construct a + * composite predicate on the fly. Oh well... */ +static dict_entry_predicate_t dict_entry_predicate = NULL; + +static bool_t +dict_predicate (trie_t *trie) +{ + dict_entry_t *entry; + + entry = dict_cursor_resolve (trie); + if (! DICT_ENTRY_IS_WORD (entry)) + return FALSE; + + if (dict_entry_predicate) + return (dict_entry_predicate) (*entry); + + return TRUE; +} + +int +dict_count (dict_t *dict, + dict_entry_predicate_t predicate) +{ + dict_entry_predicate = predicate; + return trie_count (dict, dict_predicate); +} + +int dict_print (dict_t *dict) { + int count; + string_t string; + + string_init (&string); + + dict_entry_predicate = NULL; + count = trie_print (dict, &string, dict_predicate, + 0, 0, -1); + + string_fini (&string); + + return count; +} + +int +dict_print_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + int count; + string_t string; + + string_init (&string); + + dict_entry_predicate = predicate; + count = trie_print (dict, &string, dict_predicate, + 0, 0, -1); + + string_fini (&string); + + return count; +} + +int +dict_print_by_length_if (dict_t *dict, + dict_entry_predicate_t predicate) +{ + int length, total, words, count = 0; string_t string; string_init (&string); - trie_print (dict, &string, NULL); + dict_entry_predicate = predicate; + + total = trie_count (dict, dict_predicate); + + length = 1; + do { + words = trie_print (dict, &string, dict_predicate, + 0, length, length); + if (words) { + printf ("\n"); + count += words; + } + length++; + } while (count < total); string_fini (&string); + + return count; } diff --git a/dict.h b/dict.h index d87e765..ccc0c0b 100644 --- a/dict.h +++ b/dict.h @@ -46,11 +46,30 @@ dict_entry_t * dict_lookup (dict_t *dict, const char *word); +typedef bool_t +(*dict_entry_predicate_t) (dict_entry_t entry); + +int +dict_count (dict_t *dict, + dict_entry_predicate_t predicate); + /* Querying a dictionary entry. The dict interface uses 1 bit. * All of the remaining bits are available for application use. */ #define DICT_ENTRY_IS_WORD(entry) ((entry) && ((*entry) & 0x01)) +/* Printing the dictionary */ +int +dict_print (dict_t *dict); + +int +dict_print_if (dict_t *dict, + dict_entry_predicate_t predicate); + +int +dict_print_by_length_if (dict_t *dict, + dict_entry_predicate_t predicate); + /* Character-by-character perusal of the dictionary */ dict_cursor_t dict_root (dict_t *dict); diff --git a/grid.c b/grid.c index 44ffa9d..d796cab 100644 --- a/grid.c +++ b/grid.c @@ -28,6 +28,9 @@ #include "dict.h" +/* Remember that dict reserves the 0th bit for IS_WORD */ +#define GRID_WORD_SEEN (1<<1) + char *cube_faces[16] = { "aaeeng", "abbjoo", "achops", "affkps", "aoottw", "cimotu", "deilrx", "delrvy", @@ -139,7 +142,7 @@ board_enumerate (board_t *board, string_chop (word); } -void +static void board_solve (board_t *board, dict_t *dict, dict_t *solution) { int x, y; @@ -157,6 +160,18 @@ board_solve (board_t *board, dict_t *dict, dict_t *solution) string_fini (&word); } +static bool_t +seen_predicate (dict_entry_t entry) +{ + return entry & GRID_WORD_SEEN; +} + +static bool_t +unseen_predicate (dict_entry_t entry) +{ + return ! seen_predicate (entry); +} + #define GAME_LENGTH (3 * 60) int main (void) @@ -198,10 +213,10 @@ main (void) dict_entry_t *entry; entry = dict_lookup (&solution, response); if (DICT_ENTRY_IS_WORD (entry)) { - if (*entry & TRIE_FLAGS_SEEN) + if (*entry & GRID_WORD_SEEN) printf ("(repeat)\n"); else - *entry |= TRIE_FLAGS_SEEN; + *entry |= GRID_WORD_SEEN; } else { entry = dict_lookup (&dict, response); if (DICT_ENTRY_IS_WORD (entry)) @@ -217,18 +232,13 @@ main (void) } while (remaining > 0); printf ("\nWords you found:\n"); - string_init (&word); - found = trie_print_seen (&solution, &word); - string_fini (&word); - printf ("\n"); + found = dict_print_by_length_if (&solution, seen_predicate); printf ("\nWords you missed:\n"); - string_init (&word); - missed = trie_print_unseen (&solution, &word); - string_fini (&word); + missed = dict_print_by_length_if (&solution, unseen_predicate); printf ("\n"); - printf ("\nYou found %d of %d words (%.2f%%)\n", + printf ("You found %d of %d words (%.2f%%)\n", found, found + missed, 100 * (double) found / (found + missed)); -- 2.43.0