From b627abd0bb4469460144c6272c115928249a1525 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Sun, 17 Sep 2006 01:00:10 -0700 Subject: [PATCH] Add board and solver. --- wordgame.c | 266 +++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 226 insertions(+), 40 deletions(-) diff --git a/wordgame.c b/wordgame.c index 3b4cbd3..b3df64f 100644 --- a/wordgame.c +++ b/wordgame.c @@ -23,6 +23,8 @@ #include #include #include +#include +#include #ifndef FALSE # define FALSE 0 @@ -67,6 +69,57 @@ xrealloc (void *ptr, size_t size) return res; } +typedef struct _string { + size_t size; + char *s; + size_t len; +} string_t; + +void +string_init (string_t *string) +{ + string->size = 0; + string->s = NULL; + string->len = 0; +} + +void +string_fini (string_t *string) +{ + string->size = 0; + if (string->s) + free (string->s); + string->len = 0; +} + +void +string_append_char (string_t *string, char c) +{ + if (string->size == 0) { + string->size = 8; + string->s = xmalloc (string->size); + string->s[0] = '\0'; + string->len = 0; + } + + if (string->len + 1 == string->size) { + string->size *= 2; + string->s = xrealloc (string->s, string->size); + } + + string->s[string->len++] = c; + string->s[string->len] = '\0'; +} + +void +string_chop (string_t *string) +{ + if (string->len == 0) + return; + + string->s[--string->len] = '\0'; +} + static void trie_init (trie_t *trie) { @@ -140,31 +193,13 @@ trie_contains (trie_t *trie, void trie_print (trie_t *trie, - char **str, - size_t *str_size) + string_t *string) { char c; int i; - size_t str_len; - - if (trie->is_word && *str) - printf ("%s\n", *str); - /* Make room for the extra character. */ - if (*str == NULL) { - *str_size = 8; - *str = xmalloc (*str_size); - (*str)[0] = '\0'; - } - - str_len = strlen (*str); - - if (str_len + 1 == *str_size) { - *str_size *= 2; - *str = xrealloc (*str, *str_size); - } - - (*str)[str_len + 1] = '\0'; + if (trie->is_word && string->s) + printf ("%s ", string->s); /* Loop over each element, appending the character and recursing. */ for (i = 0; i < 26; i++) { @@ -173,18 +208,10 @@ trie_print (trie_t *trie, c = TRIE_INDEX_TO_CHAR (i); - (*str)[str_len] = c; - trie_print (trie->next[i], str, str_size); + string_append_char (string, c); + trie_print (trie->next[i], string); + string_chop (string); } - - (*str)[str_len] = '\0'; -} - -void -chomp (char *str) -{ - if (str[strlen (str) - 1] == '\n') - str[strlen (str) - 1] = '\0'; } typedef struct _dict { @@ -213,32 +240,191 @@ dict_init (dict_t *dict, bytes_read = getline (&line, &line_size, file); if (bytes_read == -1) break; - chomp (line); + if (line[strlen (line) - 1] == '\n') + line[strlen (line) - 1] = '\0'; trie_add (dict->trie, line); } if (line) free (line); + + fclose (file); +} + +void +dict_fini (dict_t *dict) +{ + trie_destroy (dict->trie); } void dict_print (dict_t *dict) { - char *str = NULL; - size_t str_size = 0; + string_t string; - trie_print (dict->trie, &str, &str_size); - if (str) - free (str); + string_init (&string); + + trie_print (dict->trie, &string); + + string_fini (&string); +} + +char *cube_faces[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 */ + trie_t *result_trie; +} board_t; + +int +rand_within (int num_values) +{ + return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0))); +} + +void +shuffle (int *array, int length) +{ + int i, r, tmp; + + for (i = 0; i < length; i++) + { + r = i + rand_within (length - i); + tmp = array[i]; + array[i] = array[r]; + array[r] = tmp; + } +} + +void +board_init (board_t *board) +{ + int i; + int cubes[16]; + + for (i = 0; i < 16; i++) + cubes[i] = i; + shuffle (cubes, 16); + + for (i = 0; i < 16; i++) + board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)]; +} + +void +board_print (board_t *board) +{ + int x, y; + char c; + + 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" : " "); + } + printf ("\n"); + } +} + +#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) +{ + char c; + int dx, dy; + + if (x < 0 || x >= 4 || + y < 0 || y >= 4 || + seen & SEEN_BIT (x, y)) + { + return; + } + + 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; + + if (c == 'q') { + string_append_char (word, 'u'); + dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')]; + if (dict_trie == NULL) + goto BAIL1; + } + + if (dict_trie->is_word) + trie_add (board->result_trie, word->s); + + for (dy = -1; dy <= 1; dy++) + for (dx = -1; dx <= 1; dx++) + board_enumerate (board, x + dx, y + dy, seen, word, dict_trie); + + BAIL1: + if (c == 'q') + string_chop (word); + BAIL0: + string_chop (word); +} + +void +board_solve (board_t *board, dict_t *dict) +{ + int x, y; + int16_t seen = 0; + string_t word; + + board->result_trie = trie_create (); + + string_init (&word); + + for (y = 0; y < 4; y++) + for (x = 0; x < 4; x++) + board_enumerate (board, x, y, seen, &word, dict->trie); + printf ("\n"); + + string_fini (&word); + + string_init (&word); + trie_print (board->result_trie, &word); + printf ("\n"); + string_fini (&word); + + trie_destroy (board->result_trie); } int main (void) { dict_t dict; + board_t board; + struct timeval tv; + + gettimeofday (&tv, NULL); + srand (tv.tv_sec ^ tv.tv_usec); dict_init (&dict, "words.txt"); - dict_print (&dict); + board_init (&board); + board_print (&board); + +/* sleep (3 * 60); */ + + board_solve (&board, &dict); + + dict_fini (&dict); return 0; } - -- 2.43.0