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 <stdint.h>
  24 #include <string.h>
  25 #include <errno.h>
  26 #include <ctype.h>
  27 #include <sys/time.h>
  28 #include <time.h>
  29 #include <math.h>
  30
  31 #include <readline/readline.h>
  32 #include <readline/history.h>
  33
  34 #ifndef FALSE
  35 # define FALSE 0
  36 #endif
  37
  38 #ifndef TRUE
  39 # define TRUE 1
  40 #endif
  41
  42 typedef int bool_t;
  43
  44 #define TRIE_FLAGS_IS_WORD      (1<<0)
  45 #define TRIE_FLAGS_SEEN         (1<<1)
  46
  47 typedef struct _trie {
  48     uint32_t flags;
  49     struct _trie *next[26];
  50 } trie_t;
  51
  52 typedef bool_t
  53 (*trie_predicate_t) (trie_t *trie);
  54
  55 void *
  56 xmalloc (size_t size)
  57 {
  58     void *res;
  59
  60     res = malloc (size);
  61     if (res == NULL) {
  62         fprintf (stderr, "Error: out of memory\n");
  63         exit (1);
  64     }
  65
  66     return res;
  67 }
  68
  69 void *
  70 xrealloc (void *ptr, size_t size)
  71 {
  72     void *res;
  73
  74     res = realloc (ptr, size);
  75     if (res == NULL) {
  76         fprintf (stderr, "Error: out of memory\n");
  77         exit (1);
  78     }
  79
  80     return res;
  81 }
  82
  83 void
  84 chomp (char *s)
  85 {
  86     int len = strlen (s);
  87     if (s[len - 1] == '\n')
  88         s[len - 1] = '\0';
  89 }
  90
  91 typedef struct _string {
  92     size_t size;
  93     char *s;
  94     size_t len;
  95 } string_t;
  96
  97 void
  98 string_init (string_t *string)
  99 {
 100     string->size = 0;
 101     string->s = NULL;
 102     string->len = 0;
 103 }
 104
 105 void
 106 string_fini (string_t *string)
 107 {
 108     string->size = 0;
 109     if (string->s)
 110         free (string->s);
 111     string->len = 0;
 112 }
 113
 114 void
 115 string_append_char (string_t *string, char c)
 116 {
 117     if (string->size == 0) {
 118         string->size = 8;
 119         string->s = xmalloc (string->size);
 120         string->s[0] = '\0';
 121         string->len = 0;
 122     }
 123
 124     if (string->len + 1 == string->size) {
 125         string->size *= 2;
 126         string->s = xrealloc (string->s, string->size);
 127     }
 128
 129     string->s[string->len++] = c;
 130     string->s[string->len] = '\0';
 131 }
 132
 133 void
 134 string_chop (string_t *string)
 135 {
 136     if (string->len == 0)
 137         return;
 138
 139     string->s[--string->len] = '\0';
 140 }
 141
 142 static void
 143 trie_init (trie_t *trie)
 144 {
 145     int i;
 146     trie->flags = 0;
 147     for (i = 0; i < 26; i++)
 148         trie->next[i] = NULL;
 149 }
 150
 151 trie_t *
 152 trie_create (void)
 153 {
 154     trie_t *trie;
 155
 156     trie = xmalloc (sizeof (trie_t));
 157
 158     trie_init (trie);
 159
 160     return trie;
 161 }
 162
 163 void
 164 trie_destroy (trie_t *trie)
 165 {
 166     int i;
 167
 168     for (i = 0; i < 26; i++)
 169         if (trie->next[i])
 170             trie_destroy (trie->next[i]);
 171
 172     free (trie);
 173 }
 174
 175 #define TRIE_CHAR_TO_INDEX(c)   (tolower (c) - 'a')
 176 #define TRIE_INDEX_TO_CHAR(i)   (i + 'a')
 177 void
 178 trie_add (trie_t        *trie,
 179           const char    *word_chunk)
 180 {
 181     char c = word_chunk[0];
 182     int i;
 183
 184     if (c == '\0') {
 185         trie->flags |= TRIE_FLAGS_IS_WORD;
 186         return;
 187     }
 188
 189     i = TRIE_CHAR_TO_INDEX (c);
 190     if (trie->next[i] == NULL)
 191         trie->next[i] = trie_create ();
 192
 193     trie_add (trie->next[i], word_chunk + 1);
 194 }
 195
 196 trie_t *
 197 trie_find (trie_t       *trie,
 198            const char   *word_chunk)
 199 {
 200     const char *s = word_chunk;
 201
 202     while (trie && *s)
 203         trie = trie->next[TRIE_CHAR_TO_INDEX (*s++)];
 204
 205     return trie;
 206 }
 207
 208 int
 209 trie_print (trie_t              *trie,
 210             string_t            *string,
 211             trie_predicate_t     predicate)
 212 {
 213     char c;
 214     int i;
 215     int count = 0;
 216
 217     if (trie->flags & TRIE_FLAGS_IS_WORD
 218         && (predicate == NULL || predicate (trie)))
 219     {
 220         count = 1;
 221         printf ("%s ", string->s);
 222     }
 223
 224     /* Loop over each element, appending the character and recursing. */
 225     for (i = 0; i < 26; i++) {
 226         if (trie->next[i] == NULL)
 227             continue;
 228
 229         c = TRIE_INDEX_TO_CHAR (i);
 230
 231         string_append_char (string, c);
 232         count += trie_print (trie->next[i], string, predicate);
 233         string_chop (string);
 234     }
 235
 236     return count;
 237 }
 238
 239 bool_t
 240 trie_seen_predicate (trie_t *trie)
 241 {
 242     return (trie->flags & TRIE_FLAGS_SEEN);
 243 }
 244
 245 int
 246 trie_print_seen (trie_t *trie, string_t *word)
 247 {
 248     return trie_print (trie, word, trie_seen_predicate);
 249 }
 250
 251 bool_t
 252 trie_unseen_predicate (trie_t *trie)
 253 {
 254     return (! trie_seen_predicate (trie));
 255 }
 256
 257 int
 258 trie_print_unseen (trie_t *trie, string_t *word)
 259 {
 260     return trie_print (trie, word, trie_unseen_predicate);
 261 }
 262
 263 typedef struct _dict {
 264     trie_t *trie;
 265 } dict_t;
 266
 267 void
 268 dict_init (dict_t       *dict,
 269            const char   *filename)
 270 {
 271     FILE *file;
 272     char *line = NULL;
 273     size_t line_size = 0;
 274     ssize_t bytes_read;
 275
 276     file = fopen (filename, "r");
 277     if (file == NULL) {
 278         fprintf (stderr, "Error: failed to open %s: %s\n",
 279                  filename, strerror (errno));
 280         exit (1);
 281     }
 282
 283     dict->trie = trie_create ();
 284
 285     while (1) {
 286         bytes_read = getline (&line, &line_size, file);
 287         if (bytes_read == -1)
 288             break;
 289         chomp (line);
 290         trie_add (dict->trie, line);
 291     }
 292     if (line)
 293         free (line);
 294
 295     fclose (file);
 296 }
 297
 298 void
 299 dict_fini (dict_t *dict)
 300 {
 301     trie_destroy (dict->trie);
 302 }
 303
 304 void
 305 dict_print (dict_t *dict)
 306 {
 307     string_t string;
 308
 309     string_init (&string);
 310
 311     trie_print (dict->trie, &string, NULL);
 312
 313     string_fini (&string);
 314 }
 315
 316 char *cube_faces[16] = {
 317     "aaeeng", "abbjoo", "achops", "affkps",
 318     "aoottw", "cimotu", "deilrx", "delrvy",
 319     "distty", "eeghnw", "eeinsu", "ehrtvw",
 320     "eiosst", "elrtty", "himnqu", "hlnnrz"
 321 };
 322
 323 typedef struct _board {
 324     char letters[4][4];
 325
 326     /* Private, transient state used by enumerate */
 327     trie_t *result_trie;
 328 } board_t;
 329
 330 int
 331 rand_within (int num_values)
 332 {
 333     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
 334 }
 335
 336 void
 337 shuffle (int *array, int length)
 338 {
 339     int i, r, tmp;
 340
 341     for (i = 0; i < length; i++)
 342     {
 343         r = i + rand_within (length - i);
 344         tmp = array[i];
 345         array[i] = array[r];
 346         array[r] = tmp;
 347     }
 348 }
 349
 350 void
 351 board_init (board_t *board)
 352 {
 353     int i;
 354     int cubes[16];
 355
 356     for (i = 0; i < 16; i++)
 357         cubes[i] = i;
 358     shuffle (cubes, 16);
 359
 360     for (i = 0; i < 16; i++)
 361         board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
 362 }
 363
 364 void
 365 board_print (board_t *board)
 366 {
 367     int x, y;
 368     char c;
 369
 370     printf ("\n");
 371     for (y = 0; y < 4; y++) {
 372         for (x = 0; x < 4; x++) {
 373             c = board->letters[y][x];
 374             printf (" %c%s", toupper (c),
 375                     c == 'q' ? "u" : " ");
 376         }
 377         printf ("\n");
 378     }
 379     printf ("\n");
 380 }
 381
 382 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
 383 void
 384 board_enumerate (board_t        *board,
 385                  int             x,
 386                  int             y,
 387                  int16_t         seen,
 388                  string_t       *word,
 389                  trie_t         *dict_trie)
 390 {
 391     char c;
 392     int dx, dy;
 393
 394     if (x < 0 || x >= 4 ||
 395         y < 0 || y >= 4 ||
 396         seen & SEEN_BIT (x, y))
 397     {
 398         return;
 399     }
 400
 401     seen |= SEEN_BIT (x, y);
 402
 403     c = board->letters[y][x];
 404     string_append_char (word, c);
 405     dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX (c)];
 406     if (dict_trie == NULL)
 407         goto BAIL0;
 408
 409     if (c == 'q') {
 410         string_append_char (word, 'u');
 411         dict_trie = dict_trie->next[TRIE_CHAR_TO_INDEX ('u')];
 412         if (dict_trie == NULL)
 413             goto BAIL1;
 414     }
 415
 416     if (dict_trie->flags & TRIE_FLAGS_IS_WORD)
 417         trie_add (board->result_trie, word->s);
 418
 419     for (dy = -1; dy <= 1; dy++)
 420         for (dx = -1; dx <= 1; dx++)
 421             board_enumerate (board, x + dx, y + dy, seen, word, dict_trie);
 422
 423   BAIL1:
 424     if (c == 'q')
 425         string_chop (word);
 426   BAIL0:
 427     string_chop (word);
 428 }
 429
 430 void
 431 board_solve (board_t *board, dict_t *dict, trie_t *solution)
 432 {
 433     int x, y;
 434     int16_t seen = 0;
 435     string_t word;
 436
 437     board->result_trie = solution;
 438
 439     string_init (&word);
 440
 441     for (y = 0; y < 4; y++)
 442         for (x = 0; x < 4; x++)
 443             board_enumerate (board, x, y, seen, &word, dict->trie);
 444
 445     string_fini (&word);
 446 }
 447
 448 #define GAME_LENGTH (3 * 60)
 449 int
 450 main (void)
 451 {
 452     dict_t dict;
 453     board_t board;
 454     trie_t *solution;
 455     struct timeval tv, tv_stop;
 456     int remaining, minutes, seconds;
 457     int found, missed;
 458     char prompt[7], *response;
 459     string_t word;
 460
 461     gettimeofday (&tv, NULL);
 462     srand (tv.tv_sec ^ tv.tv_usec);
 463
 464     dict_init (&dict, "words.txt");
 465     board_init (&board);
 466
 467     solution = trie_create ();
 468     board_solve (&board, &dict, solution);
 469
 470     board_print (&board);
 471
 472     gettimeofday (&tv, NULL);
 473     tv_stop = tv;
 474     tv_stop.tv_sec += GAME_LENGTH;
 475     remaining = GAME_LENGTH;
 476     do {
 477         minutes = remaining / 60;
 478         seconds = remaining % 60;
 479         sprintf (prompt, "%02d:%02d ", minutes, seconds);
 480         response = readline (prompt);
 481         add_history (response);
 482         chomp (response);
 483         if (strlen (response) == 0) {
 484             board_print (&board);
 485         } else {
 486             trie_t *t;
 487             t = trie_find (solution, response);
 488             if (t && (t->flags & TRIE_FLAGS_IS_WORD)) {
 489                 if (t->flags & TRIE_FLAGS_SEEN)
 490                     printf ("(repeat)\n");
 491                 else
 492                     t->flags |= TRIE_FLAGS_SEEN;
 493             } else {
 494                 t = trie_find (dict.trie, response);
 495                 if (t && (t->flags & TRIE_FLAGS_IS_WORD))
 496                     printf ("(a good word, but it's not in the puzzle)\n");
 497                 else
 498                     printf ("*** %s is not a word\n", response);
 499             }
 500         }
 501         free (response);
 502         gettimeofday (&tv, NULL);
 503         remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
 504         minutes = remaining / 60;
 505     } while (remaining > 0);
 506
 507     printf ("\nWords you found:\n");
 508     string_init (&word);
 509     found = trie_print_seen (solution, &word);
 510     string_fini (&word);
 511     printf ("\n");
 512
 513     printf ("\nWords you missed:\n");
 514     string_init (&word);
 515     missed = trie_print_unseen (solution, &word);
 516     string_fini (&word);
 517     printf ("\n");
 518
 519     printf ("\nYou found %d of %d words (%.2f%%)\n",
 520             found, found + missed,
 521             100 * (double) found / (found + missed));
 522
 523     dict_fini (&dict);
 524
 525     return 0;
 526 }