]> git.cworth.org Git - wordgame/blob - grid.c
97ba7d7f3c2306e8921bf81b6e97af18d939849d
[wordgame] / grid.c
1 /*
2  * Copyright © 2006 Carl Worth
3  *
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)
7  * any later version.
8  *
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.
13  *
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."
17  */
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <ctype.h>
22 #include <sys/time.h>
23 #include <time.h>
24 #include <math.h>
25
26 #include <readline/readline.h>
27 #include <readline/history.h>
28
29 #include "dict.h"
30
31 /* Remember that dict reserves the 0th bit for IS_WORD */
32 #define GRID_WORD_SEEN (1<<1)
33
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"
39 };
40
41 typedef struct _board {
42     char letters[4][4];
43
44     /* Private, transient state used by enumerate */
45     dict_t *results;
46 } board_t;
47
48 static int
49 rand_within (int num_values)
50 {
51     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
52 }
53
54 static void
55 shuffle (int *array, int length)
56 {
57     int i, r, tmp;
58
59     for (i = 0; i < length; i++)
60     {
61         r = i + rand_within (length - i);
62         tmp = array[i];
63         array[i] = array[r];
64         array[r] = tmp;
65     }
66 }
67
68 static void
69 board_init (board_t *board)
70 {
71     int i;
72     int cubes[16];
73
74     for (i = 0; i < 16; i++)
75         cubes[i] = i;
76     shuffle (cubes, 16);
77  
78     for (i = 0; i < 16; i++)
79         board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
80 }
81
82 static void
83 board_print (board_t *board)
84 {
85     int x, y;
86     char c;
87
88     printf ("\n");
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" : " ");
94         }
95         printf ("\n");
96     }
97     printf ("\n");
98 }
99
100 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
101 static void
102 board_enumerate (board_t        *board,
103                  int             x,
104                  int             y,
105                  int16_t         seen,
106                  char           *word,
107                  dict_cursor_t   dict_cursor)
108 {
109     char c;
110     int dx, dy;
111
112     if (dict_cursor == DICT_CURSOR_NIL)
113         return;
114
115     if (x < 0 || x >= 4 ||
116         y < 0 || y >= 4 ||
117         seen & SEEN_BIT (x, y))
118     {
119         return;
120     }
121
122     seen |= SEEN_BIT (x, y);
123
124     c = board->letters[y][x];
125     word[strlen (word)] = c;
126     dict_cursor = dict_cursor_next (dict_cursor, c);
127
128     if (c == 'q') {
129         word[strlen (word)] = 'u';
130         dict_cursor = dict_cursor_next (dict_cursor, 'u');
131     }
132
133     if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
134         dict_add_word (board->results, word);
135
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);
139
140     if (c == 'q')
141         word [strlen (word) - 1] = '\0';
142     word [strlen (word) - 1] = '\0';
143 }
144
145 static void
146 board_solve (board_t *board, dict_t *dict, dict_t *solution)
147 {
148     int x, y;
149     int16_t seen = 0;
150     char word[17];
151
152     board->results = solution;
153
154     memset (word, '\0', 17);
155
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));
159 }
160
161 static bool_t
162 seen_predicate (dict_entry_t entry)
163 {
164     return entry & GRID_WORD_SEEN;
165 }
166
167 static bool_t
168 unseen_predicate (dict_entry_t entry)
169 {
170     return ! seen_predicate (entry);
171 }
172
173 #define GAME_LENGTH (3 * 60)
174 int
175 main (void)
176 {
177     dict_t dict, solution;
178     board_t board;
179     struct timeval tv, tv_stop;
180     int remaining, minutes, seconds;
181     int found, missed;
182     char prompt[7], *response;
183
184     gettimeofday (&tv, NULL);
185     srand (tv.tv_sec ^ tv.tv_usec);
186
187     dict_init (&dict);
188     dict_add_words_from_file (&dict, "words.txt");
189     board_init (&board);
190
191     dict_init (&solution);
192     board_solve (&board, &dict, &solution);
193
194     board_print (&board);
195
196     gettimeofday (&tv, NULL);
197     tv_stop = tv;
198     tv_stop.tv_sec += GAME_LENGTH;
199     remaining = GAME_LENGTH;
200     do {
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);
208         } else {
209             dict_entry_t *entry;
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");
216                 else
217                     *entry |= GRID_WORD_SEEN;
218             } else {
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");
222                 else
223                     printf ("*** %s is not a word\n", response);
224             }
225         }
226         free (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);
231
232     printf ("\nWords you found:\n");
233     found = dict_print_by_length_if (&solution, seen_predicate);
234
235     printf ("\nWords you missed:\n");
236     missed = dict_print_by_length_if (&solution, unseen_predicate);
237     printf ("\n");
238
239     printf ("You found %d of %d words (%.2f%%)\n",
240             found, found + missed,
241             100 * (double) found / (found + missed));
242
243     dict_fini (&dict);
244
245     return 0;
246 }