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
  24 char *cube_faces[16] = {
  25     "aaeeng", "abbjoo", "achops", "affkps",
  26     "aoottw", "cimotu", "deilrx", "delrvy",
  27     "distty", "eeghnw", "eeinsu", "ehrtvw",
  28     "eiosst", "elrtty", "himnqu", "hlnnrz"
  29 };
  30
  31 static int
  32 rand_within (int num_values)
  33 {
  34     return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
  35 }
  36
  37 static void
  38 shuffle (int *array, int length)
  39 {
  40     int i, r, tmp;
  41
  42     for (i = 0; i < length; i++)
  43     {
  44         r = i + rand_within (length - i);
  45         tmp = array[i];
  46         array[i] = array[r];
  47         array[r] = tmp;
  48     }
  49 }
  50
  51 void
  52 grid_init (grid_t *grid)
  53 {
  54     int i;
  55     int cubes[16];
  56
  57     for (i = 0; i < 16; i++)
  58         cubes[i] = i;
  59     shuffle (cubes, 16);
  60
  61     for (i = 0; i < 16; i++)
  62         grid->letters[i / 4][i % 4] = cube_faces[cubes[i]][rand_within(6)];
  63 }
  64
  65 char *
  66 grid_string (grid_t *grid)
  67 {
  68     char c;
  69     int x, y;
  70     char *s = grid->string;
  71
  72     for (y = 0; y < 4; y++) {
  73         for (x = 0; x < 4; x++) {
  74             c = grid->letters[y][x];
  75             *s++ = ' ';
  76             *s++ = toupper (c);
  77             if (c == 'q')
  78                 *s++ = 'u';
  79             else
  80                 *s++ = ' ';
  81         }
  82         if (y != 3)
  83             *s++ = '\n';
  84     }
  85     *s = '\0';
  86
  87     return grid->string;
  88 }
  89
  90 #define SEEN_BIT(x, y) (1 << (4*(y)+(x)))
  91 static void
  92 grid_enumerate (grid_t          *grid,
  93                 int              x,
  94                 int              y,
  95                 int16_t          seen,
  96                 char            *word,
  97                 dict_cursor_t    dict_cursor)
  98 {
  99     char c;
 100     int dx, dy;
 101
 102     if (dict_cursor == DICT_CURSOR_NIL)
 103         return;
 104
 105     if (x < 0 || x >= 4 ||
 106         y < 0 || y >= 4 ||
 107         seen & SEEN_BIT (x, y))
 108     {
 109         return;
 110     }
 111
 112     seen |= SEEN_BIT (x, y);
 113
 114     c = grid->letters[y][x];
 115     word[strlen (word)] = c;
 116     dict_cursor = dict_cursor_next (dict_cursor, c);
 117
 118     if (c == 'q') {
 119         word[strlen (word)] = 'u';
 120         dict_cursor = dict_cursor_next (dict_cursor, 'u');
 121     }
 122
 123     if (strlen (word) > 2 &&
 124         DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
 125     {
 126         dict_add_word (grid->results, word);
 127     }
 128
 129     for (dy = -1; dy <= 1; dy++)
 130         for (dx = -1; dx <= 1; dx++)
 131             grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
 132
 133     if (c == 'q')
 134         word [strlen (word) - 1] = '\0';
 135     word [strlen (word) - 1] = '\0';
 136 }
 137
 138 void
 139 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
 140 {
 141     int x, y;
 142     int16_t seen = 0;
 143     char word[18];
 144
 145     grid->results = solution;
 146
 147     memset (word, '\0', 18);
 148
 149     for (y = 0; y < 4; y++)
 150         for (x = 0; x < 4; x++)
 151             grid_enumerate (grid, x, y, seen, word, dict_root (dict));
 152 }