X-Git-Url: https://git.cworth.org/git?a=blobdiff_plain;f=grid.c;h=c68ae435353d4e09380cfbd46aa874a6cf91c7ec;hb=a46e558ad8d3243c76a9a6cafb6100be4f3f2dae;hp=76428d98bad2b6275c635f635bbef7fdc0d4b852;hpb=a6f9c10c08f706c3c25ab81fef956339490e50f3;p=wordgame diff --git a/grid.c b/grid.c index 76428d9..c68ae43 100644 --- a/grid.c +++ b/grid.c @@ -16,26 +16,28 @@ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA." */ -#include "word-game.h" +#include "grid.h" #include #include -#include -#include +#include -char *cube_faces[16] = { +#define GRID_CUBES_MAX (GRID_SIZE_MAX * GRID_SIZE_MAX) + +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) @@ -57,39 +59,68 @@ shuffle (int *array, int length) } } -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; - for (i = 0; i < 16; i++) + assert (size == 4 || size == 5); + + 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)]; } -/* ( 3 chars per cell - * x 4 cells per row - * + 1 newline per row - * ) x 4 rows per board - * + 1 terminator character - * = 53 - */ -#define BOARD_STRING_MAX 53 -static void -board_to_string (board_t *board, - char board_string[BOARD_STRING_MAX]) +void +grid_set_letters (grid_t *grid, + const char *letters) +{ + int i; + int num_cubes = grid->size * grid->size; + char letter; + + 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); + } + grid->letters[i / grid->size][i % grid->size] = letter; + } +} + +char * +grid_string (grid_t *grid) { char c; int x, y; - char *s = &board_string[0]; + char *s = grid->string; - for (y = 0; y < 4; y++) { - for (x = 0; x < 4; x++) { - c = board->letters[y][x]; + 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') @@ -97,20 +128,22 @@ board_to_string (board_t *board, else *s++ = ' '; } - if (y != 3) + if (y != (grid->size - 1)) *s++ = '\n'; } *s = '\0'; + + return grid->string; } -#define SEEN_BIT(x, y) (1 << (4*(y)+(x))) +#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; @@ -118,8 +151,8 @@ board_enumerate (board_t *board, 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; @@ -127,7 +160,7 @@ board_enumerate (board_t *board, 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); @@ -136,59 +169,36 @@ board_enumerate (board_t *board, 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)); -} - -#define GAME_LENGTH (3 * 60) -int -main (void) -{ - dict_t dict, solution; - board_t board; - char board_string[BOARD_STRING_MAX]; - struct timeval tv; - - gettimeofday (&tv, NULL); - srand (tv.tv_sec ^ tv.tv_usec); - - dict_init (&dict); - dict_add_words_from_file (&dict, "words.txt"); - - board_init (&board); - board_to_string (&board, board_string); - - dict_init (&solution); - board_solve (&board, &dict, &solution); - - word_game_play (board_string, &dict, &solution, GAME_LENGTH); - - dict_fini (&solution); - 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)); }