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."
26 #include <readline/readline.h>
27 #include <readline/history.h>
31 char *cube_faces[16] = {
32 "aaeeng", "abbjoo", "achops", "affkps",
33 "aoottw", "cimotu", "deilrx", "delrvy",
34 "distty", "eeghnw", "eeinsu", "ehrtvw",
35 "eiosst", "elrtty", "himnqu", "hlnnrz"
38 typedef struct _board {
41 /* Private, transient state used by enumerate */
46 rand_within (int num_values)
48 return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
52 shuffle (int *array, int length)
56 for (i = 0; i < length; i++)
58 r = i + rand_within (length - i);
66 board_init (board_t *board)
71 for (i = 0; i < 16; i++)
75 for (i = 0; i < 16; i++)
76 board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
80 board_print (board_t *board)
86 for (y = 0; y < 4; y++) {
87 for (x = 0; x < 4; x++) {
88 c = board->letters[y][x];
89 printf (" %c%s", toupper (c),
90 c == 'q' ? "u" : " ");
97 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
99 board_enumerate (board_t *board,
109 if (x < 0 || x >= 4 ||
111 seen & SEEN_BIT (x, y))
116 seen |= SEEN_BIT (x, y);
118 c = board->letters[y][x];
119 string_append_char (word, c);
120 dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
121 if (dict_trie == NULL)
125 string_append_char (word, 'u');
126 dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
127 if (dict_trie == NULL)
131 if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
132 trie_add (board->result_trie, word->s);
134 for (dy = -1; dy <= 1; dy++)
135 for (dx = -1; dx <= 1; dx++)
136 board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
146 board_solve (board_t *board, dict_t *dict, trie_t *solution)
152 board->result_trie = solution;
156 for (y = 0; y < 4; y++)
157 for (x = 0; x < 4; x++)
158 board_enumerate (board, x, y, seen, &word, dict->trie);
163 #define GAME_LENGTH (3 * 60)
170 struct timeval tv, tv_stop;
171 int remaining, minutes, seconds;
173 char prompt[7], *response;
176 gettimeofday (&tv, NULL);
177 srand (tv.tv_sec ^ tv.tv_usec);
180 dict_add_words_from_file (&dict, "words.txt");
183 solution = trie_create ();
184 board_solve (&board, &dict, solution);
186 board_print (&board);
188 gettimeofday (&tv, NULL);
190 tv_stop.tv_sec += GAME_LENGTH;
191 remaining = GAME_LENGTH;
193 minutes = remaining / 60;
194 seconds = remaining % 60;
195 sprintf (prompt, "%02d:%02d ", minutes, seconds);
196 response = readline (prompt);
197 add_history (response);
199 if (strlen (response) == 0) {
200 board_print (&board);
203 t = trie_find (solution, response);
204 if (t && (t->flags & TRIE_FLAGS_IS_WORD)) {
205 if (t->flags & TRIE_FLAGS_SEEN)
206 printf ("(repeat)\n");
208 t->flags |= TRIE_FLAGS_SEEN;
210 t = trie_find (dict.trie, response);
211 if (t && (t->flags & TRIE_FLAGS_IS_WORD))
212 printf ("(a good word, but it's not in the puzzle)\n");
214 printf ("*** %s is not a word\n", response);
218 gettimeofday (&tv, NULL);
219 remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
220 minutes = remaining / 60;
221 } while (remaining > 0);
223 printf ("\nWords you found:\n");
225 found = trie_print_seen (solution, &word);
229 printf ("\nWords you missed:\n");
231 missed = trie_print_unseen (solution, &word);
235 printf ("\nYou found %d of %d words (%.2f%%)\n",
236 found, found + missed,
237 100 * (double) found / (found + missed));