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
error(char * s)49 error(char *s)
50 {
51 fprint(err_fd, "fatal error: %s\n", s);
52 exits("fatal error");
53 }
54
55 void *
salloc(ulong z)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
clean_word(char * s)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
word_ok(word * w)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
str_to_mask(char * s)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 *
get_word(Biobuf * bp)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
build_wordlist(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
count_letters(target * t,char * s)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
contained(word * i,target * t)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
prune(set in,int m,target * filter,set out)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
print_set(set s)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
target_mask(int c[])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
dump_list(word ** e)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
free_set(set s)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
enumerate(word ** p,target * i,set c)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
clean(char * s)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
anagramulate(char * s)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
set_fixed(char * s)411 set_fixed(char *s)
412 {
413 if ((fixed = atoi(s)) < 1)
414 fixed = 1;
415 }
416
417 void
read_words(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
main(int argc,char ** argv)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 }
452