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 char *
  90 grid_string (grid_t *grid)
  91 {
  92     char c;
  93     int x, y;
  94     char *s = grid->string;
  95
  96     for (y = 0; y < grid->size; y++) {
  97         for (x = 0; x < grid->size; x++) {
  98             c = grid->letters[y][x];
  99             *s++ = ' ';
 100             *s++ = toupper (c);
 101             if (c == 'q')
 102                 *s++ = 'u';
 103             else
 104                 *s++ = ' ';
 105         }
 106         if (y != 3)
 107             *s++ = '\n';
 108     }
 109     *s = '\0';
 110
 111     return grid->string;
 112 }
 113
 114 #define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x)))
 115 static void
 116 grid_enumerate (grid_t          *grid,
 117                 int              x,
 118                 int              y,
 119                 int32_t          seen,
 120                 char            *word,
 121                 dict_cursor_t    dict_cursor)
 122 {
 123     char c;
 124     int dx, dy;
 125
 126     if (dict_cursor == DICT_CURSOR_NIL)
 127         return;
 128
 129     if (x < 0 || x >= grid->size ||
 130         y < 0 || y >= grid->size ||
 131         seen & SEEN_BIT (x, y))
 132     {
 133         return;
 134     }
 135
 136     seen |= SEEN_BIT (x, y);
 137
 138     c = grid->letters[y][x];
 139     word[strlen (word)] = c;
 140     dict_cursor = dict_cursor_next (dict_cursor, c);
 141
 142     if (c == 'q') {
 143         word[strlen (word)] = 'u';
 144         dict_cursor = dict_cursor_next (dict_cursor, 'u');
 145     }
 146
 147     if (strlen (word) > 2 &&
 148         DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
 149     {
 150         dict_add_word (grid->results, word);
 151     }
 152
 153     for (dy = -1; dy <= 1; dy++)
 154         for (dx = -1; dx <= 1; dx++)
 155             grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
 156
 157     if (c == 'q')
 158         word [strlen (word) - 1] = '\0';
 159     word [strlen (word) - 1] = '\0';
 160 }
 161
 162 void
 163 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
 164 {
 165     int x, y;
 166     int32_t seen = 0;
 167     char word[18];
 168
 169     grid->results = solution;
 170
 171     memset (word, '\0', 18);
 172
 173     for (y = 0; y < grid->size; y++)
 174         for (x = 0; x < grid->size; x++)
 175             grid_enumerate (grid, x, y, seen, word, dict_root (dict));
 176 }