git.cworth.org Git - wordgame/blob - grid.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 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <ctype.h>
  22 #include <sys/time.h>
  23 #include <time.h>
  24 #include <math.h>
  25
  26 #include <readline/readline.h>
  27 #include <readline/history.h>
  28
  29 #include "dict.h"
  30
  31 /* Remember that dict reserves the 0th bit for IS_WORD */
  32 #define GRID_WORD_SEEN (1<<1)
  33
  34 char *cube_faces[16] = {
  35     "aaeeng", "abbjoo", "achops", "affkps",
  36     "aoottw", "cimotu", "deilrx", "delrvy",
  37     "distty", "eeghnw", "eeinsu", "ehrtvw",
  38     "eiosst", "elrtty", "himnqu", "hlnnrz"
  39 };
  40
  41 typedef struct _board {
  42     char letters[4][4];
  43
  44     /* Private, transient state used by enumerate */
  45     dict_t *results;
  46 } board_t;
  47
  48 static int
  49 rand_within (int num_values)
  50 {
  51     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
  52 }
  53
  54 static void
  55 shuffle (int *array, int length)
  56 {
  57     int i, r, tmp;
  58
  59     for (i = 0; i < length; i++)
  60     {
  61         r = i + rand_within (length - i);
  62         tmp = array[i];
  63         array[i] = array[r];
  64         array[r] = tmp;
  65     }
  66 }
  67
  68 static void
  69 board_init (board_t *board)
  70 {
  71     int i;
  72     int cubes[16];
  73
  74     for (i = 0; i < 16; i++)
  75         cubes[i] = i;
  76     shuffle (cubes, 16);
  77
  78     for (i = 0; i < 16; i++)
  79         board->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
  80 }
  81
  82 static void
  83 board_print (board_t *board)
  84 {
  85     int x, y;
  86     char c;
  87
  88     printf ("\n");
  89     for (y = 0; y < 4; y++) {
  90         for (x = 0; x < 4; x++) {
  91             c = board->letters[y][x];
  92             printf (" %c%s", toupper (c),
  93                     c == 'q' ? "u" : " ");
  94         }
  95         printf ("\n");
  96     }
  97     printf ("\n");
  98 }
  99
 100 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
 101 static void
 102 board_enumerate (board_t        *board,
 103                  int             x,
 104                  int             y,
 105                  int16_t         seen,
 106                  char           *word,
 107                  dict_cursor_t   dict_cursor)
 108 {
 109     char c;
 110     int dx, dy;
 111
 112     if (dict_cursor == DICT_CURSOR_NIL)
 113         return;
 114
 115     if (x < 0 || x >= 4 ||
 116         y < 0 || y >= 4 ||
 117         seen & SEEN_BIT (x, y))
 118     {
 119         return;
 120     }
 121
 122     seen |= SEEN_BIT (x, y);
 123
 124     c = board->letters[y][x];
 125     word[strlen (word)] = c;
 126     dict_cursor = dict_cursor_next (dict_cursor, c);
 127
 128     if (c == 'q') {
 129         word[strlen (word)] = 'u';
 130         dict_cursor = dict_cursor_next (dict_cursor, 'u');
 131     }
 132
 133     if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
 134         dict_add_word (board->results, word);
 135
 136     for (dy = -1; dy <= 1; dy++)
 137         for (dx = -1; dx <= 1; dx++)
 138             board_enumerate (board, x + dx, y + dy, seen, word, dict_cursor);
 139
 140     if (c == 'q')
 141         word [strlen (word) - 1] = '\0';
 142     word [strlen (word) - 1] = '\0';
 143 }
 144
 145 static void
 146 board_solve (board_t *board, dict_t *dict, dict_t *solution)
 147 {
 148     int x, y;
 149     int16_t seen = 0;
 150     char word[18];
 151
 152     board->results = solution;
 153
 154     memset (word, '\0', 18);
 155
 156     for (y = 0; y < 4; y++)
 157         for (x = 0; x < 4; x++)
 158             board_enumerate (board, x, y, seen, word, dict_root (dict));
 159 }
 160
 161 static bool_t
 162 seen_predicate (dict_entry_t entry)
 163 {
 164     return entry & GRID_WORD_SEEN;
 165 }
 166
 167 static bool_t
 168 unseen_predicate (dict_entry_t entry)
 169 {
 170     return ! seen_predicate (entry);
 171 }
 172
 173 static void
 174 _count_possible (dict_cursor_t  cursor,
 175                  int            depth,
 176                  int            possible[17])
 177 {
 178     char c;
 179
 180     if (cursor == DICT_CURSOR_NIL)
 181         return;
 182
 183     if (DICT_ENTRY_IS_WORD (dict_cursor_resolve (cursor)))
 184         possible[depth]++;
 185
 186     for (c = 'a'; c <= 'z'; c++)
 187         _count_possible (dict_cursor_next (cursor, c), depth + 1, possible);
 188 }
 189
 190 #define GAME_LENGTH (3 * 60)
 191 int
 192 main (void)
 193 {
 194     int i;
 195     dict_t dict, solution;
 196     board_t board;
 197     struct timeval tv, tv_stop;
 198     int remaining, minutes, seconds;
 199     /* 16 tiles + Qu on one tile = max 17 letters in one word. */
 200     int found[17], possible[17];
 201     int found_total, possible_total;
 202     char prompt[7], *response;
 203     bool_t just_saw_board;
 204
 205     gettimeofday (&tv, NULL);
 206     srand (tv.tv_sec ^ tv.tv_usec);
 207
 208     dict_init (&dict);
 209     dict_add_words_from_file (&dict, "words.txt");
 210     board_init (&board);
 211
 212     dict_init (&solution);
 213     board_solve (&board, &dict, &solution);
 214
 215     for (i=0; i < 17; i++) {
 216         found[i] = 0;
 217         possible[i] = 0;
 218     }
 219     _count_possible (dict_root (&solution), 0, possible);
 220     found_total = 0;
 221     possible_total = 0;
 222     for (i=0; i < 17; i++)
 223         possible_total += possible[i];
 224
 225     board_print (&board);
 226     just_saw_board = TRUE;
 227
 228     gettimeofday (&tv, NULL);
 229     tv_stop = tv;
 230     tv_stop.tv_sec += GAME_LENGTH;
 231     remaining = GAME_LENGTH;
 232     do {
 233         minutes = remaining / 60;
 234         seconds = remaining % 60;
 235         sprintf (prompt, "%02d:%02d ", minutes, seconds);
 236         response = readline (prompt);
 237         add_history (response);
 238         if (strlen (response) == 0) {
 239             if (! just_saw_board) {
 240                 board_print (&board);
 241                 just_saw_board = TRUE;
 242             } else {
 243                 for (i = 2; i <= 17; i++)
 244                     if (possible[i])
 245                         printf ("%d: (%d/%d) ", i, found[i], possible[i]);
 246                 printf ("total: (%d/%d = %.2f%%)\n",
 247                         found_total, possible_total,
 248                         100 * (double) found_total / possible_total);
 249             }
 250         } else {
 251             dict_entry_t *entry;
 252             just_saw_board = FALSE;
 253             if (response[strlen (response) - 1] == '\n')
 254                 response[strlen (response) - 1] = '\0';
 255             entry = dict_lookup (&solution, response);
 256             if (DICT_ENTRY_IS_WORD (entry)) {
 257                 if (*entry & GRID_WORD_SEEN) {
 258                     printf ("(repeat)\n");
 259                 } else {
 260                     *entry |= GRID_WORD_SEEN;
 261                     found [strlen (response)]++;
 262                     found_total++;
 263                 }
 264             } else {
 265                 entry = dict_lookup (&dict, response);
 266                 if (DICT_ENTRY_IS_WORD (entry))
 267                     printf ("(a good word, but it's not in the puzzle)\n");
 268                 else
 269                     printf ("*** %s is not a word\n", response);
 270             }
 271         }
 272         free (response);
 273         gettimeofday (&tv, NULL);
 274         remaining = floor (0.5 + (tv_stop.tv_sec - tv.tv_sec) + (tv_stop.tv_usec - tv.tv_usec) / 1000000.0);
 275         minutes = remaining / 60;
 276     } while (remaining > 0);
 277
 278     board_print (&board);
 279
 280     printf ("Words you found:\n");
 281     dict_print_by_length_if (&solution, seen_predicate);
 282
 283     printf ("\nWords you missed:\n");
 284     dict_print_by_length_if (&solution, unseen_predicate);
 285     printf ("\n");
 286
 287     printf ("You found %d of %d words (%.2f%%)\n",
 288             found_total, possible_total,
 289             100 * (double) found_total / possible_total);
 290
 291     dict_fini (&dict);
 292
 293     return 0;
 294 }