2 * Copyright © 2006 Carl Worth
4 * This program is free software; you can redistribute it and\/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2, or (at your option)
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
19 /* Portably, schmortability. I want ease of programming. */
31 #include <readline/readline.h>
32 #include <readline/history.h>
44 #define TRIE_FLAGS_IS_WORD (1<<0)
45 #define TRIE_FLAGS_SEEN (1<<1)
47 typedef struct _trie {
49 struct _trie *next[26];
53 (*trie_predicate_t) (trie_t *trie);
62 fprintf (stderr, "Error: out of memory\n");
70 xrealloc (void *ptr, size_t size)
74 res = realloc (ptr, size);
76 fprintf (stderr, "Error: out of memory\n");
87 if (s[len - 1] == '\n')
91 typedef struct _string {
98 string_init (string_t *string)
106 string_fini (string_t *string)
115 string_append_char (string_t *string, char c)
117 if (string->size == 0) {
119 string->s = xmalloc (string->size);
124 if (string->len + 1 == string->size) {
126 string->s = xrealloc (string->s, string->size);
129 string->s[string->len++] = c;
130 string->s[string->len] = '\0';
134 string_chop (string_t *string)
136 if (string->len == 0)
139 string->s[--string->len] = '\0';
143 trie_init (trie_t *trie)
147 for (i = 0; i < 26; i++)
148 trie->next[i] = NULL;
156 trie = xmalloc (sizeof (trie_t));
164 trie_destroy (trie_t *trie)
168 for (i = 0; i < 26; i++)
170 trie_destroy (trie->next[i]);
175 #define TRIE_CHAR_TO_INDEX(c) (tolower (c) - 'a')
176 #define TRIE_INDEX_TO_CHAR(i) (i + 'a')
178 trie_add (trie_t *trie,
179 const char *word_chunk)
181 char c = word_chunk[0];
185 trie->flags |= TRIE_FLAGS_IS_WORD;
189 i = TRIE_CHAR_TO_INDEX (c);
190 if (trie->next[i] == NULL)
191 trie->next[i] = trie_create ();
193 trie_add (trie->next[i], word_chunk + 1);
197 trie_find (trie_t *trie,
198 const char *word_chunk)
200 const char *s = word_chunk;
203 trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
209 trie_print (trie_t *trie,
211 trie_predicate_t predicate)
217 if (trie->flags & TRIE_FLAGS_IS_WORD
218 && (predicate == NULL || predicate (trie)))
221 printf ("%s ", string->s);
224 /* Loop over each element, appending the character and recursing. */
225 for (i = 0; i < 26; i++) {
226 if (trie->next[i] == NULL)
229 c = TRIE_INDEX_TO_CHAR (i);
231 string_append_char (string, c);
232 count += trie_print (trie->next[i], string, predicate);
233 string_chop (string);
240 trie_seen_predicate (trie_t *trie)
242 return (trie->flags & TRIE_FLAGS_SEEN);
246 trie_print_seen (trie_t *trie, string_t *word)
248 return trie_print (trie, word, trie_seen_predicate);
252 trie_unseen_predicate (trie_t *trie)
254 return (! trie_seen_predicate (trie));
258 trie_print_unseen (trie_t *trie, string_t *word)
260 return trie_print (trie, word, trie_unseen_predicate);
263 typedef struct _dict {
268 dict_init (dict_t *dict,
269 const char *filename)
273 size_t line_size = 0;
276 file = fopen (filename, "r");
278 fprintf (stderr, "Error: failed to open %s: %s\n",
279 filename, strerror (errno));
283 dict->trie = trie_create ();
286 bytes_read = getline (&line, &line_size, file);
287 if (bytes_read == -1)
290 trie_add (dict->trie, line);
299 dict_fini (dict_t *dict)
301 trie_destroy (dict->trie);
305 dict_print (dict_t *dict)
309 string_init (&string);
311 trie_print (dict->trie, &string, NULL);
313 string_fini (&string);
316 char *cube_faces[16] = {
317 "aaeeng", "abbjoo", "achops", "affkps",
318 "aoottw", "cimotu", "deilrx", "delrvy",
319 "distty", "eeghnw", "eeinsu", "ehrtvw",
320 "eiosst", "elrtty", "himnqu", "hlnnrz"
323 typedef struct _board {
326 /* Private, transient state used by enumerate */
331 rand_within (int num_values)
333 return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
337 shuffle (int *array, int length)
341 for (i = 0; i < length; i++)
343 r = i + rand_within (length - i);
351 board_init (board_t *board)
356 for (i = 0; i < 16; i++)
360 for (i = 0; i < 16; i++)
361 board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
365 board_print (board_t *board)
371 for (y = 0; y < 4; y++) {
372 for (x = 0; x < 4; x++) {
373 c = board->letters[y][x];
374 printf (" %c%s", toupper (c),
375 c == 'q' ? "u" : " ");
382 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
384 board_enumerate (board_t *board,
394 if (x < 0 || x >= 4 ||
396 seen & SEEN_BIT (x, y))
401 seen |= SEEN_BIT (x, y);
403 c = board->letters[y][x];
404 string_append_char (word, c);
405 dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
406 if (dict_trie == NULL)
410 string_append_char (word, 'u');
411 dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
412 if (dict_trie == NULL)
416 if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
417 trie_add (board->result_trie, word->s);
419 for (dy = -1; dy <= 1; dy++)
420 for (dx = -1; dx <= 1; dx++)
421 board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
431 board_solve (board_t *board, dict_t *dict, trie_t *solution)
437 board->result_trie = solution;
441 for (y = 0; y < 4; y++)
442 for (x = 0; x < 4; x++)
443 board_enumerate (board, x, y, seen, &word, dict->trie);
448 #define GAME_LENGTH (3 * 60)
455 struct timeval tv, tv_stop;
456 int remaining, minutes, seconds;
458 char prompt[7], *response;
461 gettimeofday (&tv, NULL);
462 srand (tv.tv_sec ^ tv.tv_usec);
464 dict_init (&dict, "words.txt");
467 solution = trie_create ();
468 board_solve (&board, &dict, solution);
470 board_print (&board);
472 gettimeofday (&tv, NULL);
474 tv_stop.tv_sec += GAME_LENGTH;
475 remaining = GAME_LENGTH;
477 minutes = remaining / 60;
478 seconds = remaining % 60;
479 sprintf (prompt, "%02d:%02d ", minutes, seconds);
480 response = readline (prompt);
481 add_history (response);
483 if (strlen (response) == 0) {
484 board_print (&board);
487 t = trie_find (solution, response);
488 if (t && (t->flags & TRIE_FLAGS_IS_WORD)) {
489 if (t->flags & TRIE_FLAGS_SEEN)
490 printf ("(repeat)\n");
492 t->flags |= TRIE_FLAGS_SEEN;
494 t = trie_find (dict.trie, response);
495 if (t && (t->flags & TRIE_FLAGS_IS_WORD))
496 printf ("(a good word, but it's not in the puzzle)\n");
498 printf ("*** %s is not a word\n", response);
502 gettimeofday (&tv, NULL);
503 remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
504 minutes = remaining / 60;
505 } while (remaining > 0);
507 printf ("\nWords you found:\n");
509 found = trie_print_seen (solution, &word);
513 printf ("\nWords you missed:\n");
515 missed = trie_print_unseen (solution, &word);
519 printf ("\nYou found %d of %d words (%.2f%%)\n",
520 found, found + missed,
521 100 * (double) found / (found + missed));