2 * Copyright © 2006 Carl Worth
4 * This program is free software; you can redistribute it and\/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2, or (at your option)
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
19 #include "word-game.h"
26 char *cube_faces[16] = {
27 "aaeeng", "abbjoo", "achops", "affkps",
28 "aoottw", "cimotu", "deilrx", "delrvy",
29 "distty", "eeghnw", "eeinsu", "ehrtvw",
30 "eiosst", "elrtty", "himnqu", "hlnnrz"
33 typedef struct _board {
36 /* Private, transient state used by enumerate */
41 rand_within (int num_values)
43 return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
47 shuffle (int *array, int length)
51 for (i = 0; i < length; i++)
53 r = i + rand_within (length - i);
61 board_init (board_t *board)
66 for (i = 0; i < 16; i++)
70 for (i = 0; i < 16; i++)
71 board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
77 * ) x 4 rows per board
78 * + 1 terminator character
81 #define BOARD_STRING_MAX 53
83 board_to_string (board_t *board,
84 char board_string[BOARD_STRING_MAX])
88 char *s = &board_string[0];
90 for (y = 0; y < 4; y++) {
91 for (x = 0; x < 4; x++) {
92 c = board->letters[y][x];
106 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
108 board_enumerate (board_t *board,
113 dict_cursor_t dict_cursor)
118 if (dict_cursor == DICT_CURSOR_NIL)
121 if (x < 0 || x >= 4 ||
123 seen & SEEN_BIT (x, y))
128 seen |= SEEN_BIT (x, y);
130 c = board->letters[y][x];
131 word[strlen (word)] = c;
132 dict_cursor = dict_cursor_next (dict_cursor, c);
135 word[strlen (word)] = 'u';
136 dict_cursor = dict_cursor_next (dict_cursor, 'u');
139 if (strlen (word) > 2 &&
140 DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
142 dict_add_word (board->results, word);
145 for (dy = -1; dy <= 1; dy++)
146 for (dx = -1; dx <= 1; dx++)
147 board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor);
150 word [strlen (word) - 1] = '\0';
151 word [strlen (word) - 1] = '\0';
155 board_solve (board_t *board, dict_t *dict, dict_t *solution)
161 board->results = solution;
163 memset (word, '\0', 18);
165 for (y = 0; y < 4; y++)
166 for (x = 0; x < 4; x++)
167 board_enumerate (board, x, y, seen, word, dict_root (dict));
170 #define GAME_LENGTH (3 * 60)
174 dict_t dict, solution;
176 char board_string[BOARD_STRING_MAX];
179 gettimeofday (&tv, NULL);
180 srand (tv.tv_sec ^ tv.tv_usec);
183 dict_add_words_from_file (&dict, "words.txt");
186 board_to_string (&board, board_string);
188 dict_init (&solution);
189 board_solve (&board, &dict, &solution);
191 word_game_play (board_string, &dict, &solution, GAME_LENGTH);
193 dict_fini (&solution);