-wordgame: wordgame.o
- $(CC) $(CFLAGS) $(LDFLAGS) -lreadline -lm -o $@ $^
+WGCFLAGS=-Wall -Wextra -Wno-unused-parameter
+
+PROGRAMS=grid
+
+LIBRARY=dict.o
+
+all: $(PROGRAMS)
+
+%.o: %.c
+ $(CC) $(CFLAGS) $(WGCFLAGS) -c -o $@ $^
+
+%.c: dict.h
+
+grid: grid.o $(LIBRARY)
+ $(CC) $(CFLAGS) $(WGCFLAGS) $(LDFLAGS) -lreadline -lm -o $@ $^
+
+clean:
+ rm -f $(PROGRAMS) *.o
--- /dev/null
+/*
+ * Copyright © 2006 Carl Worth
+ *
+ * This program is free software; you can redistribute it and\/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
+ */
+
+/* Portably, schmortability. I want ease of programming. */
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+#include <ctype.h>
+
+#include "dict.h"
+
+void *
+xmalloc (size_t size)
+{
+ void *res;
+
+ res = malloc (size);
+ if (res == NULL) {
+ fprintf (stderr, "Error: out of memory\n");
+ exit (1);
+ }
+
+ return res;
+}
+
+void *
+xrealloc (void *ptr, size_t size)
+{
+ void *res;
+
+ res = realloc (ptr, size);
+ if (res == NULL) {
+ fprintf (stderr, "Error: out of memory\n");
+ exit (1);
+ }
+
+ return res;
+}
+
+void
+chomp (char *s)
+{
+ int len = strlen (s);
+ if (s[len - 1] == '\n')
+ s[len - 1] = '\0';
+}
+
+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->flags = 0;
+ for (i = 0; i < 26; i++)
+ trie->next[i] = NULL;
+}
+
+trie_t *
+trie_create (void)
+{
+ trie_t *trie;
+
+ trie = xmalloc (sizeof (trie_t));
+
+ trie_init (trie);
+
+ return trie;
+}
+
+void
+trie_destroy (trie_t *trie)
+{
+ int i;
+
+ for (i = 0; i < 26; i++)
+ if (trie->next[i])
+ trie_destroy (trie->next[i]);
+
+ free (trie);
+}
+
+void
+trie_add (trie_t *trie,
+ const char *word_chunk)
+{
+ char c = word_chunk[0];
+ int i;
+
+ if (c == '\0') {
+ trie->flags |= TRIE_FLAGS_IS_WORD;
+ return;
+ }
+
+ i = TRIE_CHAR_TO_INDEX (c);
+ if (trie->next[i] == NULL)
+ trie->next[i] = trie_create ();
+
+ trie_add (trie->next[i], word_chunk + 1);
+}
+
+trie_t *
+trie_find (trie_t *trie,
+ const char *word_chunk)
+{
+ const char *s = word_chunk;
+
+ while (trie && *s)
+ trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
+
+ return trie;
+}
+
+int
+trie_print (trie_t *trie,
+ string_t *string,
+ trie_predicate_t predicate)
+{
+ char c;
+ int i;
+ int count = 0;
+
+ 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++) {
+ if (trie->next[i] == NULL)
+ continue;
+
+ c = TRIE_INDEX_TO_CHAR (i);
+
+ string_append_char (string, c);
+ 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);
+}
+
+void
+dict_init (dict_t *dict,
+ const char *filename)
+{
+ FILE *file;
+ char *line = NULL;
+ size_t line_size = 0;
+ ssize_t bytes_read;
+
+ file = fopen (filename, "r");
+ if (file == NULL) {
+ fprintf (stderr, "Error: failed to open %s: %s\n",
+ filename, strerror (errno));
+ exit (1);
+ }
+
+ dict->trie = trie_create ();
+
+ while (1) {
+ bytes_read = getline (&line, &line_size, file);
+ if (bytes_read == -1)
+ break;
+ chomp (line);
+ trie_add (dict->trie, line);
+ }
+ if (line)
+ free (line);
+
+ fclose (file);
+}
+
+void
+dict_fini (dict_t *dict)
+{
+ trie_destroy (dict->trie);
+}
+
+void
+dict_print (dict_t *dict)
+{
+ string_t string;
+
+ string_init (&string);
+
+ trie_print (dict->trie, &string, NULL);
+
+ string_fini (&string);
+}
--- /dev/null
+/*
+ * Copyright © 2006 Carl Worth
+ *
+ * This program is free software; you can redistribute it and\/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
+ */
+
+#ifndef _DICT_H_
+#define _DICT_H_
+
+#include <stdint.h>
+
+#ifndef FALSE
+# define FALSE 0
+#endif
+
+#ifndef TRUE
+# define TRUE 1
+#endif
+
+typedef int bool_t;
+
+typedef struct _string {
+ size_t size;
+ char *s;
+ size_t len;
+} string_t;
+
+void
+string_init (string_t *string);
+
+void
+string_fini (string_t *string);
+
+void
+string_append_char (string_t *string, char c);
+
+void
+string_chop (string_t *string);
+
+void
+chomp (char *s);
+
+#define TRIE_FLAGS_IS_WORD (1<<0)
+#define TRIE_FLAGS_SEEN (1<<1)
+
+typedef struct _trie {
+ uint32_t flags;
+ struct _trie *next[26];
+} trie_t;
+
+typedef bool_t
+(*trie_predicate_t) (trie_t *trie);
+
+#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
+#define TRIE_INDEX_TO_CHAR(i) (i + 'a')
+
+trie_t *
+trie_create (void);
+
+void
+trie_add (trie_t *trie,
+ const char *word_chunk);
+
+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);
+
+typedef struct _dict {
+ trie_t *trie;
+} dict_t;
+
+void
+dict_init (dict_t *dict,
+ const char *filename);
+
+void
+dict_fini (dict_t *dict);
+
+#endif /* _DICT_H_ */
--- /dev/null
+/*
+ * Copyright © 2006 Carl Worth
+ *
+ * This program is free software; you can redistribute it and\/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <sys/time.h>
+#include <time.h>
+#include <math.h>
+
+#include <readline/readline.h>
+#include <readline/history.h>
+
+#include "dict.h"
+
+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");
+ 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;
+}
+++ /dev/null
-/*
- * Copyright © 2006 Carl Worth
- *
- * This program is free software; you can redistribute it and\/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2, or (at your option)
- * any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
- */
-
-/* Portably, schmortability. I want ease of programming. */
-#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
-
-#ifndef TRUE
-# define TRUE 1
-#endif
-
-typedef int bool_t;
-
-#define TRIE_FLAGS_IS_WORD (1<<0)
-#define TRIE_FLAGS_SEEN (1<<1)
-
-typedef struct _trie {
- uint32_t flags;
- struct _trie *next[26];
-} trie_t;
-
-typedef bool_t
-(*trie_predicate_t) (trie_t *trie);
-
-void *
-xmalloc (size_t size)
-{
- void *res;
-
- res = malloc (size);
- if (res == NULL) {
- fprintf (stderr, "Error: out of memory\n");
- exit (1);
- }
-
- return res;
-}
-
-void *
-xrealloc (void *ptr, size_t size)
-{
- void *res;
-
- res = realloc (ptr, size);
- if (res == NULL) {
- fprintf (stderr, "Error: out of memory\n");
- exit (1);
- }
-
- 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->flags = 0;
- for (i = 0; i < 26; i++)
- trie->next[i] = NULL;
-}
-
-trie_t *
-trie_create (void)
-{
- trie_t *trie;
-
- trie = xmalloc (sizeof (trie_t));
-
- trie_init (trie);
-
- return trie;
-}
-
-void
-trie_destroy (trie_t *trie)
-{
- int i;
-
- for (i = 0; i < 26; i++)
- if (trie->next[i])
- trie_destroy (trie->next[i]);
-
- free (trie);
-}
-
-#define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
-#define TRIE_INDEX_TO_CHAR(i) (i + 'a')
-void
-trie_add (trie_t *trie,
- const char *word_chunk)
-{
- char c = word_chunk[0];
- int i;
-
- if (c == '\0') {
- trie->flags |= TRIE_FLAGS_IS_WORD;
- return;
- }
-
- i = TRIE_CHAR_TO_INDEX (c);
- if (trie->next[i] == NULL)
- trie->next[i] = trie_create ();
-
- trie_add (trie->next[i], word_chunk + 1);
-}
-
-trie_t *
-trie_find (trie_t *trie,
- const char *word_chunk)
-{
- const char *s = word_chunk;
-
- while (trie && *s)
- trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
-
- return trie;
-}
-
-int
-trie_print (trie_t *trie,
- string_t *string,
- trie_predicate_t predicate)
-{
- char c;
- int i;
- int count = 0;
-
- 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++) {
- if (trie->next[i] == NULL)
- continue;
-
- c = TRIE_INDEX_TO_CHAR (i);
-
- string_append_char (string, c);
- 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 {
- trie_t *trie;
-} dict_t;
-
-void
-dict_init (dict_t *dict,
- const char *filename)
-{
- FILE *file;
- char *line = NULL;
- size_t line_size = 0;
- ssize_t bytes_read;
-
- file = fopen (filename, "r");
- if (file == NULL) {
- fprintf (stderr, "Error: failed to open %s: %s\n",
- filename, strerror (errno));
- exit (1);
- }
-
- dict->trie = trie_create ();
-
- while (1) {
- bytes_read = getline (&line, &line_size, file);
- if (bytes_read == -1)
- break;
- chomp (line);
- trie_add (dict->trie, line);
- }
- if (line)
- free (line);
-
- fclose (file);
-}
-
-void
-dict_fini (dict_t *dict)
-{
- trie_destroy (dict->trie);
-}
-
-void
-dict_print (dict_t *dict)
-{
- string_t string;
-
- string_init (&string);
-
- trie_print (dict->trie, &string, NULL);
-
- 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");
- 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;
-}