123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460 |
- /*
- * This file is part of the UCB release of Plan 9. It is subject to the license
- * terms in the LICENSE file found in the top-level directory of this
- * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
- * part of the UCB release of Plan 9, including this file, may be copied,
- * modified, propagated, or distributed except according to the terms contained
- * in the LICENSE file.
- */
- #include <u.h>
- #include <libc.h>
- #include <bio.h>
- #include <ctype.h>
- #define NULL ((void *)0)
- #define WORD_LIST "/sys/games/lib/anawords"
- #define VOWELS "aeiouy"
- #define ALPHAS 26
- #define LENLIMIT 64
- #define talloc(t) salloc(sizeof (t))
- #define MAP(c) ((c) - 'a')
- enum
- {
- in_fd,
- out_fd,
- err_fd,
- };
- typedef struct word word;
- struct word
- {
- char *text;
- int length;
- uint32_t mask;
- word *next;
- };
- typedef word *set[LENLIMIT];
- typedef struct
- {
- int count[ALPHAS];
- int length;
- uint32_t mask;
- }
- target;
- int fixed;
- int maxwords;
- set words;
- word *list[LENLIMIT];
- void
- error(char *s)
- {
- fprint(err_fd, "fatal error: %s\n", s);
- exits("fatal error");
- }
- void *
- salloc(uint32_t z)
- {
- void *p;
- if ((p = malloc(z)) == NULL)
- error("ran out of memory");
- return p;
- }
- void
- clean_word(char *s)
- {
- while (*s && *s != '\n')
- {
- if (isupper(*s))
- *s = tolower(*s);
- s++;
- }
- if (*s == '\n')
- *s = 0;
- }
- int
- word_ok(word *w)
- {
- char *s;
- int vowel;
- if (w->length == 0 || w->length >= LENLIMIT)
- return 0;
- if (w->length == 1)
- return strchr("aio", w->text[0]) != NULL;
- vowel = 0;
- s = w->text;
- while (*s != '\0')
- {
- if (!isalpha(*s))
- return 0;
- switch (*s)
- {
- case 'a':
- case 'e':
- case 'i':
- case 'o':
- case 'u':
- case 'y':
- vowel = 1;
- }
- s++;
- }
- return vowel;
- }
- uint32_t
- str_to_mask(char *s)
- {
- uint32_t m;
- m = 0;
- while (*s != '\0')
- m |= 1 << MAP(*s++);
- return m;
- }
- word *
- get_word(Biobuf *bp)
- {
- char *s;
- word *w;
- retry:
- if ((s = Brdline(bp, '\n')) == NULL)
- return NULL;
- clean_word(s);
- w = talloc(word);
- w->length = strlen(s);
- w->text = strcpy(salloc(w->length+1), s);
- w->mask = str_to_mask(s);
- if (!word_ok(w))
- {
- free(w->text);
- free(w);
- goto retry;
- }
- return w;
- }
- void
- build_wordlist(void)
- {
- Biobuf *bp;
- word *w;
- word **p;
- bp = Bopen(WORD_LIST, OREAD);
- if (!bp)
- {
- perror(WORD_LIST);
- exits(WORD_LIST);
- }
- while ((w = get_word(bp)) != NULL)
- {
- p = &words[w->length];
- w->next = *p;
- *p = w;
- }
- }
- void
- count_letters(target *t, char *s)
- {
- int i;
- for (i = 0; i < ALPHAS; i++)
- t->count[i] = 0;
- t->length = 0;
- while (*s != '\0')
- {
- t->count[MAP(*s++)]++;
- t->length++;
- }
- }
- int
- contained(word *i, target *t)
- {
- int n;
- char *v;
- target it;
- if ((i->mask & t->mask) != i->mask)
- return 0;
- count_letters(&it, i->text);
- for (n = 0; n < ALPHAS; n++)
- {
- if (it.count[n] > t->count[n])
- return 0;
- }
- if (it.length == t->length)
- return 1;
- for (v = VOWELS; *v != '\0'; v++)
- {
- if (t->count[MAP(*v)] > it.count[MAP(*v)])
- return 1;
- }
- return 0;
- }
- int
- prune(set in, int m, target *filter, set out)
- {
- word *i, *o, *t;
- int n;
- int nz;
- nz = 0;
- for (n = 1; n < LENLIMIT; n++)
- {
- if (n > m)
- {
- out[n] = NULL;
- continue;
- }
- o = NULL;
- for (i = in[n]; i != NULL; i = i->next)
- {
- if (contained(i, filter))
- {
- t = talloc(word);
- *t = *i;
- t->next = o;
- o = t;
- nz = 1;
- }
- }
- out[n] = o;
- }
- return nz;
- }
- void
- print_set(set s)
- {
- word *w;
- int n;
- for (n = 1; n < LENLIMIT; n++)
- {
- for (w = s[n]; w != NULL; w = w->next)
- fprint(out_fd, "%s\n", w->text);
- }
- }
- uint32_t
- target_mask(int c[])
- {
- uint32_t m;
- int i;
- m = 0;
- for (i = 0; i < ALPHAS; i++)
- {
- if (c[i] != 0)
- m |= 1 << i;
- }
- return m;
- }
- void
- dump_list(word **e)
- {
- word **p;
- fprint(out_fd, "%d", (int)(e - list + 1));
- for (p = list; p <= e; p++)
- fprint(out_fd, " %s", (*p)->text);
- fprint(out_fd, "\n");
- }
- void
- free_set(set s)
- {
- int i;
- word *p, *q;
- for (i = 1; i < LENLIMIT; i++)
- {
- for (p = s[i]; p != NULL; p = q)
- {
- q = p->next;
- free(p);
- }
- }
- }
- void
- enumerate(word **p, target *i, set c)
- {
- target t;
- set o;
- word *w, *h;
- char *s;
- int l, m, b;
- l = p - list;
- b = (i->length + (maxwords - l - 1)) / (maxwords - l);
- for (m = i->length; m >= b; m--)
- {
- h = c[m];
- for (w = h; w != NULL; w = w->next)
- {
- if (i->length == m)
- {
- *p = w;
- dump_list(p);
- continue;
- }
- if (l == maxwords - 1)
- continue;
- t = *i;
- t.length -= m;
- for (s = w->text; *s != '\0'; s++)
- t.count[MAP(*s)]--;
- t.mask = target_mask(t.count);
- c[m] = w->next;
- if (prune(c, m, &t, o))
- {
- *p = w;
- enumerate(p + 1, &t, o);
- free_set(o);
- }
- }
- c[m] = h;
- }
- }
- void
- clean(char *s)
- {
- char *p, *q;
- for (p = s, q = s; *p != '\0'; p++)
- {
- if (islower(*p))
- *q++ = *p;
- else if (isupper(*p))
- *q++ = tolower(*p);
- }
- *q = '\0';
- }
- void
- anagramulate(char *s)
- {
- target t;
- set subjects;
- clean(s);
- if (fixed)
- maxwords = fixed;
- else if ((maxwords = strlen(s) / 4) < 3)
- maxwords = 3;
- fprint(out_fd, "%s:\n", s);
- t.mask = str_to_mask(s);
- count_letters(&t, s);
- if (!prune(words,t.length, &t, subjects))
- return;
- enumerate(&list[0], &t, subjects);
- }
- void
- set_fixed(char *s)
- {
- if ((fixed = atoi(s)) < 1)
- fixed = 1;
- }
- void
- read_words(void)
- {
- char *s;
- Biobuf b;
- Binit(&b, in_fd, OREAD);
- while ((s = Brdline(&b, '\n')) != NULL)
- {
- s[Blinelen(&b)-1] = '\0';
- if (isdigit(s[0]))
- {
- set_fixed(s);
- fprint(out_fd, "Fixed = %d.\n", fixed);
- }
- else
- {
- anagramulate(s);
- fprint(out_fd, "Done.\n");
- }
- }
- }
- void
- main(int argc, char **argv)
- {
- build_wordlist();
- if (argc > 1)
- set_fixed(argv[1]);
- read_words();
- exits(0);
- }
|