* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
*/
-#include <stdio.h>
-#include <stdlib.h>
-#include <ctype.h>
-#include <sys/time.h>
-#include <time.h>
-#include <math.h>
-
-#include <readline/readline.h>
-#include <readline/history.h>
+#include "grid.h"
-#include "dict.h"
+#include <string.h>
+#include <ctype.h>
+#include <assert.h>
-/* Remember that dict reserves the 0th bit for IS_WORD */
-#define GRID_WORD_SEEN (1<<1)
+#define GRID_CUBES_MAX (GRID_SIZE_MAX * GRID_SIZE_MAX)
-char *cube_faces[16] = {
+char *cubes4[16] = {
"aaeeng", "abbjoo", "achops", "affkps",
"aoottw", "cimotu", "deilrx", "delrvy",
"distty", "eeghnw", "eeinsu", "ehrtvw",
"eiosst", "elrtty", "himnqu", "hlnnrz"
};
-typedef struct _board {
- char letters[4][4];
-
- /* Private, transient state used by enumerate */
- dict_t *results;
-} board_t;
+char *cubes5[25] = {
+ "aaafrs", "aaeeee", "aafirs", "adennn", "aeeeem",
+ "aeegmu", "aegmnn", "afirsy", "bjkqxz", "ccnstw",
+ "ceiilt", "ceilpt", "ceipst", "ddlnor", "dhhlor",
+ "dhhnot", "dhlnor", "eiiitt", "emottt", "ensssu",
+ "fiprsy", "gorrvw", "hiprry", "nootuw", "ooottu"
+};
static int
rand_within (int num_values)
}
}
-static void
-board_init (board_t *board)
+void
+grid_init (grid_t *grid, int size)
{
int i;
- int cubes[16];
+ int cubes[GRID_CUBES_MAX];
+ char **cubes_source;
+ int num_cubes;
+
+ assert (size == 4 || size == 5);
- for (i = 0; i < 16; i++)
+ grid->size = size;
+ num_cubes = size * size;
+
+ if (size == 4)
+ cubes_source = cubes4;
+ else
+ cubes_source = cubes5;
+
+ for (i = 0; i < num_cubes; i++)
cubes[i] = i;
- shuffle (cubes, 16);
+ shuffle (cubes, num_cubes);
- for (i = 0; i < 16; i++)
- board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
+ for (i = 0; i < num_cubes; i++)
+ grid->letters[i / grid->size][i % grid->size] =
+ cubes_source[cubes[i]][rand_within(6)];
}
-static void
-board_print (board_t *board)
+void
+grid_set_letters (grid_t *grid,
+ const char *letters)
{
- int x, y;
- char c;
+ int i;
+ int num_cubes = grid->size * grid->size;
+ char letter;
- printf ("\n");
- for (y = 0; y < 4; y++) {
- for (x = 0; x < 4; x++) {
- c = board->letters[y][x];
- printf (" %c%s", toupper (c),
- c == 'q' ? "u" : " ");
+ if (strlen (letters) != num_cubes) {
+ fprintf (stderr, "Error: Invalid string for %dx%d grid. Expected %d letters: %s\n",
+ grid->size, grid->size, num_cubes, letters);
+ exit (1);
+ }
+
+ for (i = 0; i < num_cubes; i++) {
+ letter = tolower (letters[i]);
+ if (letter < 'a' || letter > 'z') {
+ fprintf (stderr, "Error: Invalid character '%c' in letters: %s\n",
+ letters[i], letters);
+ exit (1);
}
- printf ("\n");
+ grid->letters[i / grid->size][i % grid->size] = letter;
}
- printf ("\n");
}
-#define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
+char *
+grid_string (grid_t *grid)
+{
+ char c;
+ int x, y;
+ char *s = grid->string;
+
+ for (y = 0; y < grid->size; y++) {
+ for (x = 0; x < grid->size; x++) {
+ c = grid->letters[y][x];
+ *s++ = ' ';
+ *s++ = toupper (c);
+ if (c == 'q')
+ *s++ = 'u';
+ else
+ *s++ = ' ';
+ }
+ if (y != (grid->size - 1))
+ *s++ = '\n';
+ }
+ *s = '\0';
+
+ return grid->string;
+}
+
+#define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x)))
static void
-board_enumerate (board_t *board,
- int x,
- int y,
- int16_t seen,
- char *word,
- dict_cursor_t dict_cursor)
+grid_enumerate (grid_t *grid,
+ int x,
+ int y,
+ int32_t seen,
+ 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 ||
+ if (x < 0 || x >= grid->size ||
+ y < 0 || y >= grid->size ||
seen & SEEN_BIT (x, y))
{
return;
seen |= SEEN_BIT (x, y);
- c = board->letters[y][x];
+ c = grid->letters[y][x];
word[strlen (word)] = c;
dict_cursor = dict_cursor_next (dict_cursor, c);
dict_cursor = dict_cursor_next (dict_cursor, 'u');
}
- if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
- dict_add_word (board->results, word);
+ /* For the 4x4 grid any word of length 3 or more counts.
+ * For the 5x5 grid any word of length 4 or more counts.
+ */
+ if (strlen (word) >= (grid->size - 1) &&
+ DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
+ {
+ dict_add_word (grid->results, word);
+ }
for (dy = -1; dy <= 1; dy++)
for (dx = -1; dx <= 1; dx++)
- board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor);
+ grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
if (c == 'q')
word [strlen (word) - 1] = '\0';
word [strlen (word) - 1] = '\0';
}
-static void
-board_solve (board_t *board, dict_t *dict, dict_t *solution)
+void
+grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
{
int x, y;
- int16_t seen = 0;
+ int32_t seen = 0;
char word[18];
- board->results = solution;
+ grid->results = solution;
memset (word, '\0', 18);
- for (y = 0; y < 4; y++)
- for (x = 0; x < 4; x++)
- 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]++;
-
- for (c = 'a'; c <= 'z'; c++)
- _count_possible (dict_cursor_next (cursor, c), depth + 1, possible);
-}
-
-#define GAME_LENGTH (3 * 60)
-int
-main (void)
-{
- int i;
- dict_t dict, solution;
- board_t board;
- struct timeval tv, tv_stop;
- int remaining, minutes, seconds;
- /* 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;
- bool_t just_saw_board;
-
- gettimeofday (&tv, NULL);
- srand (tv.tv_sec ^ tv.tv_usec);
-
- dict_init (&dict);
- dict_add_words_from_file (&dict, "words.txt");
- board_init (&board);
-
- 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;
- tv_stop.tv_sec += GAME_LENGTH;
- remaining = GAME_LENGTH;
- do {
- minutes = remaining / 60;
- seconds = remaining % 60;
- sprintf (prompt, "%02d:%02d ", minutes, seconds);
- response = readline (prompt);
- add_history (response);
- if (strlen (response) == 0) {
- 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 {
- 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 {
- *entry |= GRID_WORD_SEEN;
- found [strlen (response)]++;
- found_total++;
- }
- } else {
- 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);
- }
- }
- free (response);
- gettimeofday (&tv, NULL);
- remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
- minutes = remaining / 60;
- } while (remaining > 0);
-
- board_print (&board);
-
- printf ("Words you found:\n");
- dict_print_by_length_if (&solution, seen_predicate);
-
- printf ("\nWords you missed:\n");
- dict_print_by_length_if (&solution, unseen_predicate);
- printf ("\n");
-
- printf ("You found %d of %d words (%.2f%%)\n",
- found_total, possible_total,
- 100 * (double) found_total / possible_total);
-
- dict_fini (&dict);
-
- return 0;
+ for (y = 0; y < grid->size; y++)
+ for (x = 0; x < grid->size; x++)
+ grid_enumerate (grid, x, y, seen, word, dict_root (dict));
}
projects / wordgame / blobdiff