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 /* Remember that dict reserves the 0th bit for IS_WORD */
32 #define GRID_WORD_SEEN (1<<1)
34 char *cube_faces[16] = {
35 "aaeeng", "abbjoo", "achops", "affkps",
36 "aoottw", "cimotu", "deilrx", "delrvy",
37 "distty", "eeghnw", "eeinsu", "ehrtvw",
38 "eiosst", "elrtty", "himnqu", "hlnnrz"
41 typedef struct _board {
44 /* Private, transient state used by enumerate */
49 rand_within (int num_values)
51 return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
55 shuffle (int *array, int length)
59 for (i = 0; i < length; i++)
61 r = i + rand_within (length - i);
69 board_init (board_t *board)
74 for (i = 0; i < 16; i++)
78 for (i = 0; i < 16; i++)
79 board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
83 board_print (board_t *board)
89 for (y = 0; y < 4; y++) {
90 for (x = 0; x < 4; x++) {
91 c = board->letters[y][x];
92 printf (" %c%s", toupper (c),
93 c == 'q' ? "u" : " ");
100 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
102 board_enumerate (board_t *board,
107 dict_cursor_t dict_cursor)
112 if (dict_cursor == DICT_CURSOR_NIL)
115 if (x < 0 || x >= 4 ||
117 seen & SEEN_BIT (x, y))
122 seen |= SEEN_BIT (x, y);
124 c = board->letters[y][x];
125 word[strlen (word)] = c;
126 dict_cursor = dict_cursor_next (dict_cursor, c);
129 word[strlen (word)] = 'u';
130 dict_cursor = dict_cursor_next (dict_cursor, 'u');
133 if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
134 dict_add_word (board->results, word);
136 for (dy = -1; dy <= 1; dy++)
137 for (dx = -1; dx <= 1; dx++)
138 board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor);
141 word [strlen (word) - 1] = '\0';
142 word [strlen (word) - 1] = '\0';
146 board_solve (board_t *board, dict_t *dict, dict_t *solution)
152 board->results = solution;
154 memset (word, '\0', 17);
156 for (y = 0; y < 4; y++)
157 for (x = 0; x < 4; x++)
158 board_enumerate (board, x, y, seen, word, dict_root (dict));
162 seen_predicate (dict_entry_t entry)
164 return entry & GRID_WORD_SEEN;
168 unseen_predicate (dict_entry_t entry)
170 return ! seen_predicate (entry);
173 #define GAME_LENGTH (3 * 60)
177 dict_t dict, solution;
179 struct timeval tv, tv_stop;
180 int remaining, minutes, seconds;
182 char prompt[7], *response;
184 gettimeofday (&tv, NULL);
185 srand (tv.tv_sec ^ tv.tv_usec);
188 dict_add_words_from_file (&dict, "words.txt");
191 dict_init (&solution);
192 board_solve (&board, &dict, &solution);
194 board_print (&board);
196 gettimeofday (&tv, NULL);
198 tv_stop.tv_sec += GAME_LENGTH;
199 remaining = GAME_LENGTH;
201 minutes = remaining / 60;
202 seconds = remaining % 60;
203 sprintf (prompt, "%02d:%02d ", minutes, seconds);
204 response = readline (prompt);
205 add_history (response);
206 if (strlen (response) == 0) {
207 board_print (&board);
210 if (response[strlen (response) - 1] == '\n')
211 response[strlen (response) - 1] = '\0';
212 entry = dict_lookup (&solution, response);
213 if (DICT_ENTRY_IS_WORD (entry)) {
214 if (*entry & GRID_WORD_SEEN)
215 printf ("(repeat)\n");
217 *entry |= GRID_WORD_SEEN;
219 entry = dict_lookup (&dict, response);
220 if (DICT_ENTRY_IS_WORD (entry))
221 printf ("(a good word, but it's not in the puzzle)\n");
223 printf ("*** %s is not a word\n", response);
227 gettimeofday (&tv, NULL);
228 remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
229 minutes = remaining / 60;
230 } while (remaining > 0);
232 printf ("\nWords you found:\n");
233 found = dict_print_by_length_if (&solution, seen_predicate);
235 printf ("\nWords you missed:\n");
236 missed = dict_print_by_length_if (&solution, unseen_predicate);
239 printf ("You found %d of %d words (%.2f%%)\n",
240 found, found + missed,
241 100 * (double) found / (found + missed));