From 05c0bcdad4097a150b169f1a4fa2bae84d45f4b6 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Sun, 17 Sep 2006 02:01:17 -0700 Subject: [PATCH] Add input, verification, and scoring. I think the game is basically complete at this point. --- Makefile | 3 +- wordgame.c | 172 +++++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 136 insertions(+), 39 deletions(-) diff --git a/Makefile b/Makefile index fc58ee8..5d15674 100644 --- a/Makefile +++ b/Makefile @@ -1 +1,2 @@ -wordgame: wordgame.c +wordgame: wordgame.o + $(CC) $(CFLAGS) $(LDFLAGS) -lreadline -lm -o $@ $^ diff --git a/wordgame.c b/wordgame.c index b3df64f..a9c18d6 100644 --- a/wordgame.c +++ b/wordgame.c @@ -20,11 +20,16 @@ #define _GNU_SOURCE #include #include +#include #include #include #include #include #include +#include + +#include +#include #ifndef FALSE # define FALSE 0 @@ -35,12 +40,18 @@ #endif typedef int bool_t; - + +#define TRIE_FLAGS_IS_WORD (1<<0) +#define TRIE_FLAGS_SEEN (1<<1) + typedef struct _trie { - bool_t is_word; + uint32_t flags; struct _trie *next[26]; } trie_t; +typedef bool_t +(*trie_predicate_t) (trie_t *trie); + void * xmalloc (size_t size) { @@ -69,6 +80,14 @@ xrealloc (void *ptr, size_t size) return res; } +void +chomp (char *s) +{ + int len = strlen (s); + if (s[len - 1] == '\n') + s[len - 1] = '\0'; +} + typedef struct _string { size_t size; char *s; @@ -124,7 +143,7 @@ static void trie_init (trie_t *trie) { int i; - trie->is_word = FALSE; + trie->flags = 0; for (i = 0; i < 26; i++) trie->next[i] = NULL; } @@ -163,7 +182,7 @@ trie_add (trie_t *trie, int i; if (c == '\0') { - trie->is_word = TRUE; + trie->flags |= TRIE_FLAGS_IS_WORD; return; } @@ -174,32 +193,33 @@ trie_add (trie_t *trie, trie_add (trie->next[i], word_chunk + 1); } -bool_t -trie_contains (trie_t *trie, - const char *word_chunk) +trie_t * +trie_find (trie_t *trie, + const char *word_chunk) { - char c = word_chunk[0]; - int i; + const char *s = word_chunk; - if (c == '\0') - return trie->is_word; - - i = TRIE_CHAR_TO_INDEX (c); - if (trie->next[i] == NULL) - return FALSE; + while (trie && *s) + trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)]; - return trie_contains (trie->next[i], word_chunk + 1); + return trie; } -void -trie_print (trie_t *trie, - string_t *string) +int +trie_print (trie_t *trie, + string_t *string, + trie_predicate_t predicate) { char c; int i; + int count = 0; - if (trie->is_word && string->s) + if (trie->flags & TRIE_FLAGS_IS_WORD + && (predicate == NULL || predicate (trie))) + { + count = 1; printf ("%s ", string->s); + } /* Loop over each element, appending the character and recursing. */ for (i = 0; i < 26; i++) { @@ -209,9 +229,35 @@ trie_print (trie_t *trie, c = TRIE_INDEX_TO_CHAR (i); string_append_char (string, c); - trie_print (trie->next[i], string); + count += trie_print (trie->next[i], string, predicate); 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); } typedef struct _dict { @@ -240,8 +286,7 @@ dict_init (dict_t *dict, bytes_read = getline (&line, &line_size, file); if (bytes_read == -1) break; - if (line[strlen (line) - 1] == '\n') - line[strlen (line) - 1] = '\0'; + chomp (line); trie_add (dict->trie, line); } if (line) @@ -263,7 +308,7 @@ dict_print (dict_t *dict) string_init (&string); - trie_print (dict->trie, &string); + trie_print (dict->trie, &string, NULL); string_fini (&string); } @@ -322,6 +367,7 @@ board_print (board_t *board) int x, y; char c; + printf ("\n"); for (y = 0; y < 4; y++) { for (x = 0; x < 4; x++) { c = board->letters[y][x]; @@ -330,6 +376,7 @@ board_print (board_t *board) } printf ("\n"); } + printf ("\n"); } #define SEEN_BIT(x, y) (1 << (4*(y)+(x))) @@ -366,7 +413,7 @@ board_enumerate (board_t *board, goto BAIL1; } - if (dict_trie->is_word) + if (dict_trie->flags & TRIE_FLAGS_IS_WORD) trie_add (board->result_trie, word->s); for (dy = -1; dy <= 1; dy++) @@ -381,48 +428,97 @@ board_enumerate (board_t *board, } void -board_solve (board_t *board, dict_t *dict) +board_solve (board_t *board, dict_t *dict, trie_t *solution) { int x, y; int16_t seen = 0; string_t word; - board->result_trie = trie_create (); + board->result_trie = solution; string_init (&word); for (y = 0; y < 4; y++) for (x = 0; x < 4; x++) board_enumerate (board, x, y, seen, &word, dict->trie); - printf ("\n"); string_fini (&word); - - string_init (&word); - trie_print (board->result_trie, &word); - printf ("\n"); - string_fini (&word); - - trie_destroy (board->result_trie); } +#define GAME_LENGTH (3 * 60) int main (void) { dict_t dict; board_t board; - struct timeval tv; + trie_t *solution; + struct timeval tv, tv_stop; + int remaining, minutes, seconds; + int found, missed; + char prompt[7], *response; + string_t word; gettimeofday (&tv, NULL); srand (tv.tv_sec ^ tv.tv_usec); dict_init (&dict, "words.txt"); board_init (&board); + + solution = trie_create (); + board_solve (&board, &dict, solution); + board_print (&board); -/* sleep (3 * 60); */ + gettimeofday (&tv, NULL); + tv_stop = tv; + tv_stop.tv_sec += GAME_LENGTH; + remaining = GAME_LENGTH; + do { + minutes = remaining / 60; + seconds = remaining % 60; + sprintf (prompt, "%02d:%02d ", minutes, seconds); + response = readline (prompt); + add_history (response); + chomp (response); + if (strlen (response) == 0) { + board_print (&board); + } else { + trie_t *t; + t = trie_find (solution, response); + if (t && (t->flags & TRIE_FLAGS_IS_WORD)) { + if (t->flags & TRIE_FLAGS_SEEN) + printf ("(repeat)\n"); + else + t->flags |= TRIE_FLAGS_SEEN; + } else { + t = trie_find (dict.trie, response); + if (t && (t->flags & TRIE_FLAGS_IS_WORD)) + printf ("(a good word, but it's not in the puzzle)\n"); + else + printf ("*** %s is not a word\n", response); + } + } + free (response); + gettimeofday (&tv, NULL); + remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0); + minutes = remaining / 60; + } while (remaining > 0); + + printf ("\nWords you found:\n"); + string_init (&word); + found = trie_print_seen (solution, &word); + string_fini (&word); + printf ("\n"); + + printf ("\nWords you missed:\n"); + string_init (&word); + missed = trie_print_unseen (solution, &word); + string_fini (&word); + printf ("\n"); - board_solve (&board, &dict); + printf ("\nYou found %d of %d words (%.2f%%)\n", + found, found + missed, + 100 * (double) found / (found + missed)); dict_fini (&dict); -- 2.43.0