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 "grid.h"
  20
  21 #include <string.h>
  22 #include <ctype.h>
  23 #include <assert.h>
  24
  25 #define GRID_CUBES_MAX (GRID_SIZE_MAX * GRID_SIZE_MAX)
  26
  27 char *cubes4[16] = {
  28     "aaeeng", "abbjoo", "achops", "affkps",
  29     "aoottw", "cimotu", "deilrx", "delrvy",
  30     "distty", "eeghnw", "eeinsu", "ehrtvw",
  31     "eiosst", "elrtty", "himnqu", "hlnnrz"
  32 };
  33
  34 char *cubes5[25] = {
  35     "aaafrs", "aaeeee", "aafirs", "adennn", "aeeeem",
  36     "aeegmu", "aegmnn", "afirsy", "bjkqxz", "ccnstw",
  37     "ceiilt", "ceilpt", "ceipst", "ddlnor", "dhhlor",
  38     "dhhnot", "dhlnor", "eiiitt", "emottt", "ensssu",
  39     "fiprsy", "gorrvw", "hiprry", "nootuw", "ooottu"
  40 };
  41
  42 static int
  43 rand_within (int num_values)
  44 {
  45     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
  46 }
  47
  48 static void
  49 shuffle (int *array, int length)
  50 {
  51     int i, r, tmp;
  52
  53     for (i = 0; i < length; i++)
  54     {
  55         r = i + rand_within (length - i);
  56         tmp = array[i];
  57         array[i] = array[r];
  58         array[r] = tmp;
  59     }
  60 }
  61
  62 void
  63 grid_init (grid_t *grid, int size)
  64 {
  65     int i;
  66     int cubes[GRID_CUBES_MAX];
  67     char **cubes_source;
  68     int num_cubes;
  69
  70     assert (size == 4 || size == 5);
  71
  72     grid->size = size;
  73     num_cubes = size * size;
  74
  75     if (size == 4)
  76         cubes_source = cubes4;
  77     else
  78         cubes_source = cubes5;
  79
  80     for (i = 0; i < num_cubes; i++)
  81         cubes[i] = i;
  82     shuffle (cubes, num_cubes);
  83
  84     for (i = 0; i < num_cubes; i++)
  85         grid->letters[i / grid->size][i % grid->size] =
  86             cubes_source[cubes[i]][rand_within(6)];
  87 }
  88
  89 void
  90 grid_set_letters (grid_t        *grid,
  91                   const char    *letters)
  92 {
  93     int i;
  94     int num_cubes = grid->size * grid->size;
  95     char letter;
  96
  97     if (strlen (letters) != num_cubes) {
  98         fprintf (stderr, "Error: Invalid string for %dx%d grid. Expected %d letters: %s\n",
  99                  grid->size, grid->size, num_cubes, letters);
 100         exit (1);
 101     }
 102
 103     for (i = 0; i < num_cubes; i++) {
 104         letter = tolower (letters[i]);
 105         if (letter < 'a' || letter > 'z') {
 106             fprintf (stderr, "Error: Invalid character '%c' in letters: %s\n",
 107                      letters[i], letters);
 108             exit (1);
 109         }
 110         grid->letters[i / grid->size][i % grid->size] = letter;
 111     }
 112 }
 113
 114 char *
 115 grid_string (grid_t *grid)
 116 {
 117     char c;
 118     int x, y;
 119     char *s = grid->string;
 120
 121     for (y = 0; y < grid->size; y++) {
 122         for (x = 0; x < grid->size; x++) {
 123             c = grid->letters[y][x];
 124             *s++ = ' ';
 125             *s++ = toupper (c);
 126             if (c == 'q')
 127                 *s++ = 'u';
 128             else
 129                 *s++ = ' ';
 130         }
 131         if (y != (grid->size - 1))
 132             *s++ = '\n';
 133     }
 134     *s = '\0';
 135
 136     return grid->string;
 137 }
 138
 139 #define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x)))
 140 static void
 141 grid_enumerate (grid_t          *grid,
 142                 int              x,
 143                 int              y,
 144                 int32_t          seen,
 145                 char            *word,
 146                 dict_cursor_t    dict_cursor)
 147 {
 148     char c;
 149     int dx, dy;
 150
 151     if (dict_cursor == DICT_CURSOR_NIL)
 152         return;
 153
 154     if (x < 0 || x >= grid->size ||
 155         y < 0 || y >= grid->size ||
 156         seen & SEEN_BIT (x, y))
 157     {
 158         return;
 159     }
 160
 161     seen |= SEEN_BIT (x, y);
 162
 163     c = grid->letters[y][x];
 164     word[strlen (word)] = c;
 165     dict_cursor = dict_cursor_next (dict_cursor, c);
 166
 167     if (c == 'q') {
 168         word[strlen (word)] = 'u';
 169         dict_cursor = dict_cursor_next (dict_cursor, 'u');
 170     }
 171
 172     /* For the 4x4 grid any word of length 3 or more counts.
 173      * For the 5x5 grid any word of length 4 or more counts.
 174      */
 175     if (strlen (word) >= (grid->size - 1) &&
 176         DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
 177     {
 178         dict_add_word (grid->results, word);
 179     }
 180
 181     for (dy = -1; dy <= 1; dy++)
 182         for (dx = -1; dx <= 1; dx++)
 183             grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
 184
 185     if (c == 'q')
 186         word [strlen (word) - 1] = '\0';
 187     word [strlen (word) - 1] = '\0';
 188 }
 189
 190 void
 191 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
 192 {
 193     int x, y;
 194     int32_t seen = 0;
 195     char word[18];
 196
 197     grid->results = solution;
 198
 199     memset (word, '\0', 18);
 200
 201     for (y = 0; y < grid->size; y++)
 202         for (x = 0; x < grid->size; x++)
 203             grid_enumerate (grid, x, y, seen, word, dict_root (dict));
 204 }