sys/src/games/ana.c

   1 #include        <u.h>
   2 #include        <libc.h>
   3 #include        <bio.h>
   4 #include        <ctype.h>
   5
   6 #define NULL            ((void *)0)
   7
   8 #define WORD_LIST       "/sys/games/lib/anawords"
   9 #define VOWELS          "aeiouy"
  10 #define ALPHAS          26
  11 #define LENLIMIT        64
  12
  13 #define talloc(t)       salloc(sizeof (t))
  14 #define MAP(c)          ((c) - 'a')
  15
  16 enum
  17 {
  18         in_fd,
  19         out_fd,
  20         err_fd,
  21 };
  22
  23 typedef struct word     word;
  24
  25 struct word
  26 {
  27         char    *text;
  28         int     length;
  29         ulong   mask;
  30         word    *next;
  31 };
  32
  33 typedef word    *set[LENLIMIT];
  34
  35 typedef struct
  36 {
  37         int     count[ALPHAS];
  38         int     length;
  39         ulong   mask;
  40 }
  41         target;
  42
  43 int     fixed;
  44 int     maxwords;
  45 set     words;
  46 word    *list[LENLIMIT];
  47
  48 void
  49 error(char *s)
  50 {
  51         fprint(err_fd, "fatal error: %s\n", s);
  52         exits("fatal error");
  53 }
  54
  55 void    *
  56 salloc(ulong z)
  57 {
  58         void    *p;
  59
  60         if ((p = malloc(z)) == NULL)
  61                 error("ran out of memory");
  62
  63         return p;
  64 }
  65
  66 void
  67 clean_word(char *s)
  68 {
  69         while (*s && *s != '\n')
  70         {
  71                 if (isupper(*s))
  72                         *s = tolower(*s);
  73
  74                 s++;
  75         }
  76         if (*s == '\n')
  77                 *s = 0;
  78 }
  79
  80 int
  81 word_ok(word *w)
  82 {
  83         char    *s;
  84         int     vowel;
  85
  86         if (w->length == 0 || w->length >= LENLIMIT)
  87                 return 0;
  88
  89         if (w->length == 1)
  90                 return strchr("aio", w->text[0]) != NULL;
  91
  92         vowel = 0;
  93         s = w->text;
  94
  95         while (*s != '\0')
  96         {
  97                 if (!isalpha(*s))
  98                         return 0;
  99
 100                 switch (*s)
 101                 {
 102                 case 'a':
 103                 case 'e':
 104                 case 'i':
 105                 case 'o':
 106                 case 'u':
 107                 case 'y':
 108                         vowel = 1;
 109                 }
 110
 111                 s++;
 112         }
 113
 114         return vowel;
 115 }
 116
 117 ulong
 118 str_to_mask(char *s)
 119 {
 120         ulong   m;
 121
 122         m = 0;
 123
 124         while (*s != '\0')
 125                 m |= 1 << MAP(*s++);
 126
 127         return m;
 128 }
 129
 130 word    *
 131 get_word(Biobuf *bp)
 132 {
 133         char    *s;
 134         word    *w;
 135
 136 retry:
 137         if ((s = Brdline(bp, '\n')) == NULL)
 138                 return NULL;
 139
 140         clean_word(s);
 141
 142         w = talloc(word);
 143         w->length = strlen(s);
 144         w->text = strcpy(salloc(w->length+1), s);
 145         w->mask = str_to_mask(s);
 146
 147         if (!word_ok(w))
 148         {
 149                 free(w->text);
 150                 free(w);
 151                 goto retry;
 152         }
 153
 154         return w;
 155 }
 156
 157 void
 158 build_wordlist(void)
 159 {
 160         Biobuf  *bp;
 161         word    *w;
 162         word    **p;
 163
 164         bp = Bopen(WORD_LIST, OREAD);
 165         if (!bp)
 166         {
 167                 perror(WORD_LIST);
 168                 exits(WORD_LIST);
 169         }
 170
 171         while ((w = get_word(bp)) != NULL)
 172         {
 173                 p = &words[w->length];
 174                 w->next = *p;
 175                 *p = w;
 176         }
 177 }
 178
 179 void
 180 count_letters(target *t, char *s)
 181 {
 182         int     i;
 183
 184         for (i = 0; i < ALPHAS; i++)
 185                 t->count[i] = 0;
 186
 187         t->length = 0;
 188
 189         while (*s != '\0')
 190         {
 191                 t->count[MAP(*s++)]++;
 192                 t->length++;
 193         }
 194 }
 195
 196 int
 197 contained(word *i, target *t)
 198 {
 199         int     n;
 200         char    *v;
 201         target  it;
 202
 203         if ((i->mask & t->mask) != i->mask)
 204                 return 0;
 205
 206         count_letters(&it, i->text);
 207
 208         for (n = 0; n < ALPHAS; n++)
 209         {
 210                 if (it.count[n] > t->count[n])
 211                         return 0;
 212         }
 213
 214         if (it.length == t->length)
 215                 return 1;
 216
 217         for (v = VOWELS; *v != '\0'; v++)
 218         {
 219                 if (t->count[MAP(*v)] > it.count[MAP(*v)])
 220                         return 1;
 221         }
 222
 223         return 0;
 224 }
 225
 226 int
 227 prune(set in, int m, target *filter, set out)
 228 {
 229         word    *i, *o, *t;
 230         int     n;
 231         int     nz;
 232
 233         nz = 0;
 234
 235         for (n = 1; n < LENLIMIT; n++)
 236         {
 237                 if (n > m)
 238                 {
 239                         out[n] = NULL;
 240                         continue;
 241                 }
 242
 243                 o = NULL;
 244
 245                 for (i = in[n]; i != NULL; i = i->next)
 246                 {
 247                         if (contained(i, filter))
 248                         {
 249                                 t = talloc(word);
 250                                 *t = *i;
 251                                 t->next = o;
 252                                 o = t;
 253                                 nz = 1;
 254                         }
 255                 }
 256
 257                 out[n] = o;
 258         }
 259
 260         return nz;
 261 }
 262
 263 void
 264 print_set(set s)
 265 {
 266         word    *w;
 267         int     n;
 268
 269         for (n = 1; n < LENLIMIT; n++)
 270         {
 271                 for (w = s[n]; w != NULL; w = w->next)
 272                         fprint(out_fd, "%s\n", w->text);
 273         }
 274 }
 275
 276 ulong
 277 target_mask(int c[])
 278 {
 279         ulong   m;
 280         int     i;
 281
 282         m = 0;
 283
 284         for (i = 0; i < ALPHAS; i++)
 285         {
 286                 if (c[i] != 0)
 287                         m |= 1 << i;
 288         }
 289
 290         return m;
 291 }
 292
 293 void
 294 dump_list(word **e)
 295 {
 296         word    **p;
 297
 298         fprint(out_fd, "%d", (int)(e - list + 1));
 299
 300         for (p = list; p <= e; p++)
 301                 fprint(out_fd, " %s", (*p)->text);
 302
 303         fprint(out_fd, "\n");
 304 }
 305
 306 void
 307 free_set(set s)
 308 {
 309         int     i;
 310         word    *p, *q;
 311
 312         for (i = 1; i < LENLIMIT; i++)
 313         {
 314                 for (p = s[i]; p != NULL; p = q)
 315                 {
 316                         q = p->next;
 317                         free(p);
 318                 }
 319         }
 320 }
 321
 322 void
 323 enumerate(word **p, target *i, set c)
 324 {
 325         target  t;
 326         set     o;
 327         word    *w, *h;
 328         char    *s;
 329         int     l, m, b;
 330
 331         l = p - list;
 332         b = (i->length + (maxwords - l - 1)) / (maxwords - l);
 333
 334         for (m = i->length; m >= b; m--)
 335         {
 336                 h = c[m];
 337
 338                 for (w = h; w != NULL; w = w->next)
 339                 {
 340                         if (i->length == m)
 341                         {
 342                                 *p = w;
 343                                 dump_list(p);
 344                                 continue;
 345                         }
 346
 347                         if (l == maxwords - 1)
 348                                 continue;
 349
 350                         t = *i;
 351                         t.length -= m;
 352
 353                         for (s = w->text; *s != '\0'; s++)
 354                                 t.count[MAP(*s)]--;
 355
 356                         t.mask = target_mask(t.count);
 357                         c[m] = w->next;
 358
 359                         if (prune(c, m, &t, o))
 360                         {
 361                                 *p = w;
 362                                 enumerate(p + 1, &t, o);
 363                                 free_set(o);
 364                         }
 365                 }
 366
 367                 c[m] = h;
 368         }
 369 }
 370
 371 void
 372 clean(char *s)
 373 {
 374         char    *p, *q;
 375
 376         for (p = s, q = s; *p != '\0'; p++)
 377         {
 378                 if (islower(*p))
 379                         *q++ = *p;
 380                 else if (isupper(*p))
 381                         *q++ = tolower(*p);
 382         }
 383
 384         *q = '\0';
 385 }
 386
 387 void
 388 anagramulate(char *s)
 389 {
 390         target  t;
 391         set     subjects;
 392
 393         clean(s);
 394
 395         if (fixed)
 396                 maxwords = fixed;
 397         else if ((maxwords = strlen(s) / 4) < 3)
 398                 maxwords = 3;
 399
 400         fprint(out_fd, "%s:\n", s);
 401         t.mask = str_to_mask(s);
 402         count_letters(&t, s);
 403
 404         if (!prune(words,t.length, &t, subjects))
 405                 return;
 406
 407         enumerate(&list[0], &t, subjects);
 408 }
 409
 410 void
 411 set_fixed(char *s)
 412 {
 413         if ((fixed = atoi(s)) < 1)
 414                 fixed = 1;
 415 }
 416
 417 void
 418 read_words(void)
 419 {
 420         char    *s;
 421         Biobuf  b;
 422
 423         Binit(&b, in_fd, OREAD);
 424         while ((s = Brdline(&b, '\n')) != NULL)
 425         {
 426                 s[Blinelen(&b)-1] = '\0';
 427                 if (isdigit(s[0]))
 428                 {
 429                         set_fixed(s);
 430                         fprint(out_fd, "Fixed = %d.\n", fixed);
 431                 }
 432                 else
 433                 {
 434                         anagramulate(s);
 435                         fprint(out_fd, "Done.\n");
 436                 }
 437
 438         }
 439 }
 440
 441 void
 442 main(int argc, char **argv)
 443 {
 444         build_wordlist();
 445
 446         if (argc > 1)
 447                 set_fixed(argv[1]);
 448
 449         read_words();
 450         exits(0);
 451 }