Rev 2 | Blame | Compare with Previous | Last modification | View Log | RSS feed
#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);
}