ref: 556618eb07d1ac6e2c629a60acd53c45d53261be
dir: /sys/src/games/ana.c/
#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; ulong mask; word *next; }; typedef word *set[LENLIMIT]; typedef struct { int count[ALPHAS]; int length; ulong 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(ulong 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; } ulong str_to_mask(char *s) { ulong 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); } } ulong target_mask(int c[]) { ulong 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); }