X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=wordgame.c;h=a9c18d6e7e5e38f7a86f38ec0fde34bd801544fe;hb=05c0bcdad4097a150b169f1a4fa2bae84d45f4b6;hp=3b4cbd36332fe5aa108c567b2ac51220fe0dabdf;hpb=146a6b2ed7b4efa0040a2d781445a3fe81050275;p=wordgame

diff --git a/wordgame.c b/wordgame.c
index 3b4cbd3..a9c18d6 100644
--- a/wordgame.c
+++ b/wordgame.c
@@ -20,9 +20,16 @@
 #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
@@ -33,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)
 {
@@ -67,11 +80,70 @@ 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;
+    size_t len;
+} string_t;
+
+void
+string_init (string_t *string)
+{
+    string->size = 0;
+    string->s = NULL;
+    string->len = 0;
+}
+
+void
+string_fini (string_t *string)
+{
+    string->size = 0;
+    if (string->s)
+	free (string->s);
+    string->len = 0;
+}
+
+void
+string_append_char (string_t *string, char c)
+{
+    if (string->size == 0) {
+	string->size = 8;
+	string->s = xmalloc (string->size);
+	string->s[0] = '\0';
+	string->len = 0;
+    }
+
+    if (string->len + 1 == string->size) {
+	string->size *= 2;
+	string->s = xrealloc (string->s, string->size);
+    }
+
+    string->s[string->len++] = c;
+    string->s[string->len] = '\0';
+}
+
+void
+string_chop (string_t *string)
+{
+    if (string->len == 0)
+	return;
+
+    string->s[--string->len] = '\0';
+}
+
 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;
 }
@@ -110,7 +182,7 @@ trie_add (trie_t	*trie,
     int i;
 
     if (c == '\0') {
-	trie->is_word = TRUE;
+	trie->flags |= TRIE_FLAGS_IS_WORD;
 	return;
     }
 
@@ -121,51 +193,34 @@ 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;
+    while (trie && *s)
+	trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
 
-    i = TRIE_CHAR_TO_INDEX (c);
-    if (trie->next[i] == NULL)
-	return FALSE;
-
-    return trie_contains (trie->next[i], word_chunk + 1);
+    return trie;
 }
 
-void
-trie_print (trie_t	*trie,
-	    char	**str,
-	    size_t	*str_size)
+int
+trie_print (trie_t		*trie,
+	    string_t		*string,
+	    trie_predicate_t	 predicate)
 {
     char c;
     int i;
-    size_t str_len;
-
-    if (trie->is_word && *str)
-	printf ("%s\n", *str);
-
-    /* Make room for the extra character. */
-    if (*str == NULL) {
-	*str_size = 8;
-	*str = xmalloc (*str_size);
-	(*str)[0] = '\0';
-    }
-    
-    str_len = strlen (*str);
+    int count = 0;
 
-    if (str_len + 1 == *str_size) {
-	*str_size *= 2;
-	*str = xrealloc (*str, *str_size);
+    if (trie->flags & TRIE_FLAGS_IS_WORD
+	&& (predicate == NULL || predicate (trie)))
+    {
+	count = 1;
+	printf ("%s ", string->s);
     }
 
-    (*str)[str_len + 1] = '\0';
-
     /* Loop over each element, appending the character and recursing. */
     for (i = 0; i < 26; i++) {
 	if (trie->next[i] == NULL)
@@ -173,18 +228,36 @@ trie_print (trie_t	*trie,
 
 	c = TRIE_INDEX_TO_CHAR (i);
 
-	(*str)[str_len] = c;
-	trie_print (trie->next[i], str, str_size);
+	string_append_char (string, c);
+	count += trie_print (trie->next[i], string, predicate);
+	string_chop (string);
     }
 
-    (*str)[str_len] = '\0';
+    return count;
 }
 
-void
-chomp (char *str)
+bool_t
+trie_seen_predicate (trie_t *trie)
+{
+    return (trie->flags & TRIE_FLAGS_SEEN);
+}
+
+int
+trie_print_seen (trie_t *trie, string_t *word)
 {
-    if (str[strlen (str) - 1] == '\n')
-	str[strlen (str) - 1] = '\0';
+    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 {
@@ -218,27 +291,236 @@ dict_init (dict_t 	*dict,
     }
     if (line)
 	free (line);
+
+    fclose (file);
+}
+
+void
+dict_fini (dict_t *dict)
+{
+    trie_destroy (dict->trie);
 }
 
 void
 dict_print (dict_t *dict)
 {
-    char *str = NULL;
-    size_t str_size = 0;
+    string_t string;
+
+    string_init (&string);
+
+    trie_print (dict->trie, &string, NULL);
 
-    trie_print (dict->trie, &str, &str_size);
-    if (str)
-	free (str);
+    string_fini (&string);
 }
 
+char *cube_faces[16] = {
+    "aaeeng", "abbjoo", "achops", "affkps",
+    "aoottw", "cimotu", "deilrx", "delrvy",
+    "distty", "eeghnw", "eeinsu", "ehrtvw",
+    "eiosst", "elrtty", "himnqu", "hlnnrz"
+};
+
+typedef struct _board {
+    char letters[4][4];
+
+    /* Private, transient state used by enumerate */
+    trie_t *result_trie;
+} board_t;
+
+int
+rand_within (int num_values)
+{
+    return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
+}
+
+void
+shuffle (int *array, int length)
+{
+    int i, r, tmp;
+
+    for (i = 0; i < length; i++)
+    {
+	r = i + rand_within (length - i);
+	tmp = array[i];
+	array[i] = array[r];
+	array[r] = tmp;
+    }
+}
+
+void
+board_init (board_t *board)
+{
+    int i;
+    int cubes[16];
+
+    for (i = 0; i < 16; i++)
+	cubes[i] = i;
+    shuffle (cubes, 16);
+ 
+    for (i = 0; i < 16; i++)
+	board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
+}
+
+void
+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];
+	    printf (" %c%s", toupper (c),
+		    c == 'q' ? "u" : " ");
+	}
+	printf ("\n");
+    }
+    printf ("\n");
+}
+
+#define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
+void
+board_enumerate (board_t	*board,
+		 int		 x,
+		 int		 y,
+		 int16_t	 seen,
+		 string_t	*word,
+		 trie_t		*dict_trie)
+{
+    char c;
+    int dx, dy;
+
+    if (x < 0 || x >= 4 ||
+	y < 0 || y >= 4 ||
+	seen & SEEN_BIT (x, y))
+    {
+	return;
+    }
+
+    seen |= SEEN_BIT (x, y);
+
+    c = board->letters[y][x];
+    string_append_char (word, c);
+    dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
+    if (dict_trie == NULL)
+	goto BAIL0;
+
+    if (c == 'q') {
+	string_append_char (word, 'u');
+	dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
+	if (dict_trie == NULL)
+	    goto BAIL1;
+    }
+
+    if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
+	trie_add (board->result_trie, word->s);
+
+    for (dy = -1; dy <= 1; dy++)
+	for (dx = -1; dx <= 1; dx++)
+	    board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
+
+  BAIL1:
+    if (c == 'q')
+	string_chop (word);
+  BAIL0:
+    string_chop (word);
+}
+
+void
+board_solve (board_t *board, dict_t *dict, trie_t *solution)
+{
+    int x, y;
+    int16_t seen = 0;
+    string_t word;
+
+    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);
+
+    string_fini (&word);
+}
+
+#define GAME_LENGTH (3 * 60)
 int
 main (void)
 {
     dict_t dict;
+    board_t board;
+    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");
-    dict_print (&dict);
+    board_init (&board);
+
+    solution = trie_create ();
+    board_solve (&board, &dict, solution);
+
+    board_print (&board);
+
+    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");
+
+    printf ("\nYou found %d of %d words (%.2f%%)\n",
+	    found, found + missed,
+	    100 * (double) found / (found + missed));
+
+    dict_fini (&dict);
 
     return 0;
 }
-