X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=grid.c;h=acfee21831118ef1f1c28df7d975639b1fcee0fb;hb=c0136554ee870455bf1d1b527d7a724beda989b3;hp=9b0ffbe7eeb30896af40c006dae551373463a70d;hpb=70914305c0fe98948ba7e105a220fe7a36a62fec;p=wordgame diff --git a/grid.c b/grid.c index 9b0ffbe..acfee21 100644 --- a/grid.c +++ b/grid.c @@ -16,39 +16,36 @@ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." */ -#include -#include -#include -#include -#include -#include +#include "grid.h" -#include -#include +#include +#include +#include -#include "dict.h" +#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" +}; -int +static int rand_within (int num_values) { return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0))); } -void +static void shuffle (int *array, int length) { int i, r, tmp; @@ -63,51 +60,74 @@ shuffle (int *array, int length) } void -board_init (board_t *board) +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)]; } -void -board_print (board_t *board) +char * +grid_string (grid_t *grid) { - int x, y; char c; - - 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" : " "); + 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++ = ' '; } - printf ("\n"); + if (y != 3) + *s++ = '\n'; } - printf ("\n"); + *s = '\0'; + + return grid->string; } -#define SEEN_BIT(x, y) (1 << (4*(y)+(x))) -void -board_enumerate (board_t *board, - int x, - int y, - int16_t seen, - string_t *word, - trie_t *dict_trie) +#define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x))) +static void +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 (x < 0 || x >= 4 || - y < 0 || y >= 4 || + if (dict_cursor == DICT_CURSOR_NIL) + return; + + if (x < 0 || x >= grid->size || + y < 0 || y >= grid->size || seen & SEEN_BIT (x, y)) { return; @@ -115,127 +135,42 @@ board_enumerate (board_t *board, seen |= SEEN_BIT (x, y); - c = board->letters[y][x]; - string_append_char (word, c); - dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)]; - if (dict_trie == NULL) - goto BAIL0; + c = grid->letters[y][x]; + word[strlen (word)] = c; + dict_cursor = dict_cursor_next (dict_cursor, c); if (c == 'q') { - string_append_char (word, 'u'); - dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')]; - if (dict_trie == NULL) - goto BAIL1; + word[strlen (word)] = 'u'; + dict_cursor = dict_cursor_next (dict_cursor, 'u'); } - if (dict_trie->flags & TRIE_FLAGS_IS_WORD) - dict_add_word (board->results, word->s); + if (strlen (word) > 2 && + 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_trie); + grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor); - BAIL1: if (c == 'q') - string_chop (word); - BAIL0: - string_chop (word); + word [strlen (word) - 1] = '\0'; + word [strlen (word) - 1] = '\0'; } void -board_solve (board_t *board, dict_t *dict, dict_t *solution) +grid_solve (grid_t *grid, dict_t *dict, dict_t *solution) { int x, y; - int16_t seen = 0; - string_t word; + int32_t seen = 0; + char word[18]; - board->results = solution; + grid->results = solution; - string_init (&word); + memset (word, '\0', 18); - for (y = 0; y < 4; y++) - for (x = 0; x < 4; x++) - board_enumerate (board, x, y, seen, &word, dict); - - string_fini (&word); -} - -#define GAME_LENGTH (3 * 60) -int -main (void) -{ - dict_t dict, solution; - board_t board; - struct timeval tv, tv_stop; - int remaining, minutes, seconds; - int found, missed; - char prompt[7], *response; - string_t word; - - 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); - - board_print (&board); - - 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); - chomp (response); - if (strlen (response) == 0) { - board_print (&board); - } else { - trie_t *t; - t = trie_find (&solution, response); - if (t && (t->flags & TRIE_FLAGS_IS_WORD)) { - if (t->flags & TRIE_FLAGS_SEEN) - printf ("(repeat)\n"); - else - t->flags |= TRIE_FLAGS_SEEN; - } else { - t = trie_find (&dict, response); - if (t && (t->flags & TRIE_FLAGS_IS_WORD)) - 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); - - printf ("\nWords you found:\n"); - string_init (&word); - found = trie_print_seen (&solution, &word); - string_fini (&word); - printf ("\n"); - - printf ("\nWords you missed:\n"); - string_init (&word); - missed = trie_print_unseen (&solution, &word); - string_fini (&word); - printf ("\n"); - - printf ("\nYou found %d of %d words (%.2f%%)\n", - found, found + missed, - 100 * (double) found / (found + missed)); - - 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)); }