#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
+#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <ctype.h>
#include <sys/time.h>
#include <time.h>
+#include <math.h>
+
+#include <readline/readline.h>
+#include <readline/history.h>
#ifndef FALSE
# define FALSE 0
#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)
{
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;
trie_init (trie_t *trie)
{
int i;
- trie->is_word = FALSE;
+ trie->flags = 0;
for (i = 0; i < 26; i++)
trie->next[i] = NULL;
}
int i;
if (c == '\0') {
- trie->is_word = TRUE;
+ trie->flags |= TRIE_FLAGS_IS_WORD;
return;
}
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++) {
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 {
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)
string_init (&string);
- trie_print (dict->trie, &string);
+ trie_print (dict->trie, &string, NULL);
string_fini (&string);
}
int x, y;
char c;
+ printf ("\n");
for (y = 0; y < 4; y++) {
for (x = 0; x < 4; x++) {
c = board->letters[y][x];
}
printf ("\n");
}
+ printf ("\n");
}
#define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
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++)
}
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);
projects / wordgame / commitdiff