#include <string.h>
#include <errno.h>
#include <ctype.h>
+#include <sys/time.h>
+#include <time.h>
#ifndef FALSE
# define FALSE 0
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)
{
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++) {
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 {
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;
}
-
projects / wordgame / commitdiff