#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",
char letters[4][4];
/* Private, transient state used by enumerate */
- dict_t *result_trie;
+ dict_t *results;
} board_t;
-int
+static int
rand_within (int num_values)
{
return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
}
-void
+static void
shuffle (int *array, int length)
{
int i, r, tmp;
}
}
-void
+static void
board_init (board_t *board)
{
int i;
board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
}
-void
+static void
board_print (board_t *board)
{
int x, y;
}
#define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
-void
+static void
board_enumerate (board_t *board,
int x,
int y,
int16_t seen,
- string_t *word,
- trie_t *dict_trie)
+ char *word,
+ dict_cursor_t dict_cursor)
{
char c;
int dx, dy;
+ if (dict_cursor == DICT_CURSOR_NIL)
+ return;
+
if (x < 0 || x >= 4 ||
y < 0 || y >= 4 ||
seen & SEEN_BIT (x, y))
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;
+ word[strlen (word)] = c;
+ dict_cursor = dict_cursor_next (dict_cursor, c);
if (c == 'q') {
- string_append_char (word, 'u');
- dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
- if (dict_trie == NULL)
- goto BAIL1;
+ word[strlen (word)] = 'u';
+ dict_cursor = dict_cursor_next (dict_cursor, 'u');
}
- if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
- trie_add (board->result_trie, word->s);
+ if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
+ dict_add_word (board->results, word);
for (dy = -1; dy <= 1; dy++)
for (dx = -1; dx <= 1; dx++)
- board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
+ board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor);
- BAIL1:
if (c == 'q')
- string_chop (word);
- BAIL0:
- string_chop (word);
+ word [strlen (word) - 1] = '\0';
+ word [strlen (word) - 1] = '\0';
}
-void
-board_solve (board_t *board, dict_t *dict, trie_t *solution)
+static void
+board_solve (board_t *board, dict_t *dict, dict_t *solution)
{
int x, y;
int16_t seen = 0;
- string_t word;
+ char word[18];
- board->result_trie = solution;
+ board->results = solution;
- string_init (&word);
+ memset (word, '\0', 18);
for (y = 0; y < 4; y++)
for (x = 0; x < 4; x++)
- board_enumerate (board, x, y, seen, &word, dict);
+ board_enumerate (board, x, y, seen, word, dict_root (dict));
+}
+
+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);
+}
+
+static void
+_count_possible (dict_cursor_t cursor,
+ int depth,
+ int possible[17])
+{
+ char c;
+
+ if (cursor == DICT_CURSOR_NIL)
+ return;
+
+ if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (cursor)))
+ possible[depth]++;
- string_fini (&word);
+ for (c = 'a'; c <= 'z'; c++)
+ _count_possible (dict_cursor_next (cursor, c), depth + 1, possible);
}
#define GAME_LENGTH (3 * 60)
int
main (void)
{
- dict_t dict;
+ int i;
+ dict_t dict, solution;
board_t board;
- trie_t *solution;
struct timeval tv, tv_stop;
int remaining, minutes, seconds;
- int found, missed;
+ /* 16 tiles + Qu on one tile = max 17 letters in one word. */
+ int found[17], possible[17];
+ int found_total, possible_total;
char prompt[7], *response;
- string_t word;
+ bool_t just_saw_board;
gettimeofday (&tv, NULL);
srand (tv.tv_sec ^ tv.tv_usec);
dict_add_words_from_file (&dict, "words.txt");
board_init (&board);
- solution = trie_create ();
- board_solve (&board, &dict, solution);
+ dict_init (&solution);
+ board_solve (&board, &dict, &solution);
+
+ for (i=0; i < 17; i++) {
+ found[i] = 0;
+ possible[i] = 0;
+ }
+ _count_possible (dict_root (&solution), 0, possible);
+ found_total = 0;
+ possible_total = 0;
+ for (i=0; i < 17; i++)
+ possible_total += possible[i];
board_print (&board);
+ just_saw_board = TRUE;
gettimeofday (&tv, NULL);
tv_stop = tv;
sprintf (prompt, "%02d:%02d ", minutes, seconds);
response = readline (prompt);
add_history (response);
- chomp (response);
if (strlen (response) == 0) {
- board_print (&board);
+ if (! just_saw_board) {
+ board_print (&board);
+ just_saw_board = TRUE;
+ } else {
+ for (i = 2; i <= 17; i++)
+ if (possible[i])
+ printf ("%d: (%d/%d) ", i, found[i], possible[i]);
+ printf ("total: (%d/%d = %.2f%%)\n",
+ found_total, possible_total,
+ 100 * (double) found_total / possible_total);
+ }
} else {
- trie_t *t;
- t = trie_find (solution, response);
- if (t && (t->flags & TRIE_FLAGS_IS_WORD)) {
- if (t->flags & TRIE_FLAGS_SEEN)
+ dict_entry_t *entry;
+ just_saw_board = FALSE;
+ if (response[strlen (response) - 1] == '\n')
+ response[strlen (response) - 1] = '\0';
+ entry = dict_lookup (&solution, response);
+ if (DICT_ENTRY_IS_WORD (entry)) {
+ if (*entry & GRID_WORD_SEEN) {
printf ("(repeat)\n");
- else
- t->flags |= TRIE_FLAGS_SEEN;
+ } else {
+ *entry |= GRID_WORD_SEEN;
+ found [strlen (response)]++;
+ found_total++;
+ }
} else {
- t = trie_find (&dict, response);
- if (t && (t->flags & TRIE_FLAGS_IS_WORD))
+ entry = dict_lookup (&dict, response);
+ if (DICT_ENTRY_IS_WORD (entry))
printf ("(a good word, but it's not in the puzzle)\n");
else
printf ("*** %s is not a word\n", response);
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");
+ board_print (&board);
+
+ printf ("Words you found:\n");
+ 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);
+ dict_print_by_length_if (&solution, unseen_predicate);
printf ("\n");
- printf ("\nYou found %d of %d words (%.2f%%)\n",
- found, found + missed,
- 100 * (double) found / (found + missed));
+ printf ("You found %d of %d words (%.2f%%)\n",
+ found_total, possible_total,
+ 100 * (double) found_total / possible_total);
dict_fini (&dict);