git.cworth.org Git - wordgame/blob - wordgame.c

   1 /*
   2  * Copyright © 2006 Carl Worth
   3  *
   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)
   7  * any later version.
   8  *
   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.
  13  *
  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."
  17  */
  18
  19 /* Portably, schmortability. I want ease of programming. */
  20 #define _GNU_SOURCE
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <ctype.h>
  26 #include <sys/time.h>
  27 #include <time.h>
  28
  29 #ifndef FALSE
  30 # define FALSE 0
  31 #endif
  32
  33 #ifndef TRUE
  34 # define TRUE 1
  35 #endif
  36
  37 typedef int bool_t;
  38
  39 typedef struct _trie {
  40     bool_t is_word;
  41     struct _trie *next[26];
  42 } trie_t;
  43
  44 void *
  45 xmalloc (size_t size)
  46 {
  47     void *res;
  48
  49     res = malloc (size);
  50     if (res == NULL) {
  51         fprintf (stderr, "Error: out of memory\n");
  52         exit (1);
  53     }
  54
  55     return res;
  56 }
  57
  58 void *
  59 xrealloc (void *ptr, size_t size)
  60 {
  61     void *res;
  62
  63     res = realloc (ptr, size);
  64     if (res == NULL) {
  65         fprintf (stderr, "Error: out of memory\n");
  66         exit (1);
  67     }
  68
  69     return res;
  70 }
  71
  72 typedef struct _string {
  73     size_t size;
  74     char *s;
  75     size_t len;
  76 } string_t;
  77
  78 void
  79 string_init (string_t *string)
  80 {
  81     string->size = 0;
  82     string->s = NULL;
  83     string->len = 0;
  84 }
  85
  86 void
  87 string_fini (string_t *string)
  88 {
  89     string->size = 0;
  90     if (string->s)
  91         free (string->s);
  92     string->len = 0;
  93 }
  94
  95 void
  96 string_append_char (string_t *string, char c)
  97 {
  98     if (string->size == 0) {
  99         string->size = 8;
 100         string->s = xmalloc (string->size);
 101         string->s[0] = '\0';
 102         string->len = 0;
 103     }
 104
 105     if (string->len + 1 == string->size) {
 106         string->size *= 2;
 107         string->s = xrealloc (string->s, string->size);
 108     }
 109
 110     string->s[string->len++] = c;
 111     string->s[string->len] = '\0';
 112 }
 113
 114 void
 115 string_chop (string_t *string)
 116 {
 117     if (string->len == 0)
 118         return;
 119
 120     string->s[--string->len] = '\0';
 121 }
 122
 123 static void
 124 trie_init (trie_t *trie)
 125 {
 126     int i;
 127     trie->is_word = FALSE;
 128     for (i = 0; i < 26; i++)
 129         trie->next[i] = NULL;
 130 }
 131
 132 trie_t *
 133 trie_create (void)
 134 {
 135     trie_t *trie;
 136
 137     trie = xmalloc (sizeof (trie_t));
 138
 139     trie_init (trie);
 140
 141     return trie;
 142 }
 143
 144 void
 145 trie_destroy (trie_t *trie)
 146 {
 147     int i;
 148
 149     for (i = 0; i < 26; i++)
 150         if (trie->next[i])
 151             trie_destroy (trie->next[i]);
 152
 153     free (trie);
 154 }
 155
 156 #define TRIE_CHAR_TO_INDEX(c)   (tolower (c) - 'a')
 157 #define TRIE_INDEX_TO_CHAR(i)   (i + 'a')
 158 void
 159 trie_add (trie_t        *trie,
 160           const char    *word_chunk)
 161 {
 162     char c = word_chunk[0];
 163     int i;
 164
 165     if (c == '\0') {
 166         trie->is_word = TRUE;
 167         return;
 168     }
 169
 170     i = TRIE_CHAR_TO_INDEX (c);
 171     if (trie->next[i] == NULL)
 172         trie->next[i] = trie_create ();
 173
 174     trie_add (trie->next[i], word_chunk + 1);
 175 }
 176
 177 bool_t
 178 trie_contains (trie_t           *trie,
 179                const char       *word_chunk)
 180 {
 181     char c = word_chunk[0];
 182     int i;
 183
 184     if (c == '\0')
 185         return trie->is_word;
 186
 187     i = TRIE_CHAR_TO_INDEX (c);
 188     if (trie->next[i] == NULL)
 189         return FALSE;
 190
 191     return trie_contains (trie->next[i], word_chunk + 1);
 192 }
 193
 194 void
 195 trie_print (trie_t      *trie,
 196             string_t    *string)
 197 {
 198     char c;
 199     int i;
 200
 201     if (trie->is_word && string->s)
 202         printf ("%s ", string->s);
 203
 204     /* Loop over each element, appending the character and recursing. */
 205     for (i = 0; i < 26; i++) {
 206         if (trie->next[i] == NULL)
 207             continue;
 208
 209         c = TRIE_INDEX_TO_CHAR (i);
 210
 211         string_append_char (string, c);
 212         trie_print (trie->next[i], string);
 213         string_chop (string);
 214     }
 215 }
 216
 217 typedef struct _dict {
 218     trie_t *trie;
 219 } dict_t;
 220
 221 void
 222 dict_init (dict_t       *dict,
 223            const char   *filename)
 224 {
 225     FILE *file;
 226     char *line = NULL;
 227     size_t line_size = 0;
 228     ssize_t bytes_read;
 229
 230     file = fopen (filename, "r");
 231     if (file == NULL) {
 232         fprintf (stderr, "Error: failed to open %s: %s\n",
 233                  filename, strerror (errno));
 234         exit (1);
 235     }
 236
 237     dict->trie = trie_create ();
 238
 239     while (1) {
 240         bytes_read = getline (&line, &line_size, file);
 241         if (bytes_read == -1)
 242             break;
 243         if (line[strlen (line) - 1] == '\n')
 244             line[strlen (line) - 1] = '\0';
 245         trie_add (dict->trie, line);
 246     }
 247     if (line)
 248         free (line);
 249
 250     fclose (file);
 251 }
 252
 253 void
 254 dict_fini (dict_t *dict)
 255 {
 256     trie_destroy (dict->trie);
 257 }
 258
 259 void
 260 dict_print (dict_t *dict)
 261 {
 262     string_t string;
 263
 264     string_init (&string);
 265
 266     trie_print (dict->trie, &string);
 267
 268     string_fini (&string);
 269 }
 270
 271 char *cube_faces[16] = {
 272     "aaeeng", "abbjoo", "achops", "affkps",
 273     "aoottw", "cimotu", "deilrx", "delrvy",
 274     "distty", "eeghnw", "eeinsu", "ehrtvw",
 275     "eiosst", "elrtty", "himnqu", "hlnnrz"
 276 };
 277
 278 typedef struct _board {
 279     char letters[4][4];
 280
 281     /* Private, transient state used by enumerate */
 282     trie_t *result_trie;
 283 } board_t;
 284
 285 int
 286 rand_within (int num_values)
 287 {
 288     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
 289 }
 290
 291 void
 292 shuffle (int *array, int length)
 293 {
 294     int i, r, tmp;
 295
 296     for (i = 0; i < length; i++)
 297     {
 298         r = i + rand_within (length - i);
 299         tmp = array[i];
 300         array[i] = array[r];
 301         array[r] = tmp;
 302     }
 303 }
 304
 305 void
 306 board_init (board_t *board)
 307 {
 308     int i;
 309     int cubes[16];
 310
 311     for (i = 0; i < 16; i++)
 312         cubes[i] = i;
 313     shuffle (cubes, 16);
 314
 315     for (i = 0; i < 16; i++)
 316         board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
 317 }
 318
 319 void
 320 board_print (board_t *board)
 321 {
 322     int x, y;
 323     char c;
 324
 325     for (y = 0; y < 4; y++) {
 326         for (x = 0; x < 4; x++) {
 327             c = board->letters[y][x];
 328             printf (" %c%s", toupper (c),
 329                     c == 'q' ? "u" : " ");
 330         }
 331         printf ("\n");
 332     }
 333 }
 334
 335 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
 336 void
 337 board_enumerate (board_t        *board,
 338                  int             x,
 339                  int             y,
 340                  int16_t         seen,
 341                  string_t       *word,
 342                  trie_t         *dict_trie)
 343 {
 344     char c;
 345     int dx, dy;
 346
 347     if (x < 0 || x >= 4 ||
 348         y < 0 || y >= 4 ||
 349         seen & SEEN_BIT (x, y))
 350     {
 351         return;
 352     }
 353
 354     seen |= SEEN_BIT (x, y);
 355
 356     c = board->letters[y][x];
 357     string_append_char (word, c);
 358     dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
 359     if (dict_trie == NULL)
 360         goto BAIL0;
 361
 362     if (c == 'q') {
 363         string_append_char (word, 'u');
 364         dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
 365         if (dict_trie == NULL)
 366             goto BAIL1;
 367     }
 368
 369     if (dict_trie->is_word)
 370         trie_add (board->result_trie, word->s);
 371
 372     for (dy = -1; dy <= 1; dy++)
 373         for (dx = -1; dx <= 1; dx++)
 374             board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
 375
 376   BAIL1:
 377     if (c == 'q')
 378         string_chop (word);
 379   BAIL0:
 380     string_chop (word);
 381 }
 382
 383 void
 384 board_solve (board_t *board, dict_t *dict)
 385 {
 386     int x, y;
 387     int16_t seen = 0;
 388     string_t word;
 389
 390     board->result_trie = trie_create ();
 391
 392     string_init (&word);
 393
 394     for (y = 0; y < 4; y++)
 395         for (x = 0; x < 4; x++)
 396             board_enumerate (board, x, y, seen, &word, dict->trie);
 397     printf ("\n");
 398
 399     string_fini (&word);
 400
 401     string_init (&word);
 402     trie_print (board->result_trie, &word);
 403     printf ("\n");
 404     string_fini (&word);
 405
 406     trie_destroy (board->result_trie);
 407 }
 408
 409 int
 410 main (void)
 411 {
 412     dict_t dict;
 413     board_t board;
 414     struct timeval tv;
 415
 416     gettimeofday (&tv, NULL);
 417     srand (tv.tv_sec ^ tv.tv_usec);
 418
 419     dict_init (&dict, "words.txt");
 420     board_init (&board);
 421     board_print (&board);
 422
 423 /*    sleep (3 * 60); */
 424
 425     board_solve (&board, &dict);
 426
 427     dict_fini (&dict);
 428
 429     return 0;
 430 }