billr@saab.CNA.TEK.COM (Bill Randle) (06/04/91)
Submitted-by: Morten Ronseth <morten@dcs.qmw.ac.uk>
Posting-number: Volume 12, Issue 82
Archive-name: ag2/Part01
Supersedes: ag: Volume 12, Issue 81
[This is a revised version of ag which fixes some minor bugs
and includes some output filters that deletes many of the
"bad" anagrams. -br]
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 1)."
# Contents: README MANIFEST Makefile anagram.c postf.c pref.c pref.l
# Wrapped by billr@saab on Mon Jun 3 16:45:31 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(2767 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
X
XThis is an anagram generator I wrote a little while back, based
Xon an article in Byte, Nov. 1987, by Mike Morton.
XI have included comments in the sources to indicate the original
Xparts as coded by Mr. Morton (if I missed any, please don't kill me,
XMike!).
X
XShould any of you come up with a good user interface, preferably
Xgraphical, then Mr. Morton would be interested in hearing from
Xyou. He can be reached at: ``mikem@uhccux.uhcc.hawaii.edu''
X(which eventually will be replaced by: ``mike@daba1.pegasus.com'').
X
X
X
XAdded in this release are two filters, written by Sean Barret,
X``buzzard@eng.umd.edu''. There is a pre- and a postfilter, one
Xfor sorting out and ``customizing'' the dictionary, and one for
Xpostprocessing, sorting out unwanted anagrams. As he writes:
X
X|"...Still, I decided to make a go-round again with ag, an#d so wrote
X| these filters. It is quite possible and even probable that some
X| good anagrams will get cut using 'postf'; still, like a good judicial
X| system, hopefully it'll be many more of the "bad" ones, percentage
X| wise."
X| .
X| .
X| .
X|"...it is the postfix word-length processing that cuts out
X| the vast majority of words."
X|
X|"Both programs should be considered public domain. I always
X| like getting credit for my ideas, but admittedly the programs
X| here are nothing astonishing. They're not even bug-free."
X
XAs you can see, he places the code in the public domain, free for
Xanyone to use (even though it probably would be nice if you
Xmentioned his name somewhere).
X
X
X
XThis version fixes a bug which (so far) only occured on SPARC's,
Xnamely when dereferencing a NULL pointer in the ``parse_flags''
Xroutine. All the other compilers I've tried quite happily ignored
Xthe fact that this is illogical.
X
XI have also added the feature of reading the dictionary from stdin.
XIf, when specifying input dictionary, you give it ``-d -'', ag will
Xread the dictionary from stdin. Note, however, that only 1 phrase
Xcan be processed when making use of this, as it isn't possible to
Xrewind standard input. Any additional phrases will be ignored by ag.
X
XThis means that ag can be put in a pipeline, and the output from
Xany filter can be used as input.
X
X
X
XThe genarator compiles with
X make ag
Xand should run on any Unix; I've compiled and run it on
XHP-UX (6.5 - 7.0), Sun 3 (3.5, 4.0, 4.1.1), Sun4c (4.1.1),
XSequent (DYNIX(R) V3.0.14 NFS #18), Mac (Think C, MPW).
X
XThe algorithm used to generate anagrams is very quick, an order
Xof magnitude faster than the program found on uunet.uu.net.
X(well, now this little thingy is also on uunet so...)
XAs literally zillions of anagrams are generated, long phrases
Xshould be avoided, and the output redirected to a file (for
Xlater humorous viewing..:-)
X
XHave Fun!
X
XMorten (morten@dcs.qmw.ac.uk)
END_OF_FILE
if test 2767 -ne `wc -c <'README'`; then
echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'MANIFEST' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'MANIFEST'\"
else
echo shar: Extracting \"'MANIFEST'\" \(331 characters\)
sed "s/^X//" >'MANIFEST' <<'END_OF_FILE'
X File Name Archive # Description
X-----------------------------------------------------------
X MANIFEST 1 This shipping list
X Makefile 1
X README 1
X anagram.c 1
X postf.c 1
X pref.c 1
X pref.l 1
END_OF_FILE
if test 331 -ne `wc -c <'MANIFEST'`; then
echo shar: \"'MANIFEST'\" unpacked with wrong size!
fi
# end of 'MANIFEST'
fi
if test -f 'Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(1247 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
X# Makefile for ag - Anagram Generator
X# Written by Morten Lerskau Ronseth
X# May 30, 1991
X#
X
XCC = gcc
X
XCCFLAGS = -O #-g
X
XSHELL = /bin/sh
X
XINSTALL = install
X
XBINDIR = /export/users/morten/bin
X
XCSOURCES = anagram.c postf.c
X
XFILES = Makefile README $(CSOURCES) pref.l fag
X
X
Xall: ag pref postf
X
Xag : anagram.c
X $(CC) $(CCFLAGS) $? -o ag
X
Xpostf: postf.c
X $(CC) $(CCFLAGS) postf.c -o postf
X
Xpref: pref.l
X @$(LEX) pref.l
X @mv lex.yy.c $@.c
X $(CC) $(CCFLAGS) -ll $@.c -o pref
X
Xinstall : ag
X $(INSTALL) -s ag $(BINDIR)
X
Xclean : NOTREACHED
X rm -f ag pref postf *.o lex.yy.c shar.out
X
Xshar : NOTREACHED
X @shar $(FILES) > shar.out
X @echo Archive in shar.out
X
Xlint: NOTREACHED
X lint $(CSOURCES) 2>&1 | tee lint.out
X
Xctags: NOTREACHED
X ctags anagram.c
X
Xdiff: NOTREACHED
X @echo > ag.pch
X @(for i in $(FILES); do \
X if [ -r $${i}.orig -a -r $${i} ]; then \
X set +e; \
X diff -c $${i}.orig $${i} > tmp; \
X case $$? in \
X 1) cat tmp >> ag.pch;; \
X 2) echo diff: error 2; exit 2;; \
X esac \
X else \
X echo either $${i}.orig or $${i} does not exist; \
X fi \
X done)
X @echo Context diff created in ag.pch
X
Xpatch: *.pch
X for i in $(FILES); do \
X cp $${i} ${i}.orig; \
X done
X patch < $?
X
X
XNOTREACHED:
END_OF_FILE
if test 1247 -ne `wc -c <'Makefile'`; then
echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'anagram.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'anagram.c'\"
else
echo shar: Extracting \"'anagram.c'\" \(17694 characters\)
sed "s/^X//" >'anagram.c' <<'END_OF_FILE'
X/**********************************************************
X * *
X * *
X * *
X * A program to generate anagrams *
X * Based on an idea in Byte, Nov 1987 *
X * *
X * Written by *
X * *
X * Morten Lerskau Ronseth *
X * morten@dcs.qmw.ac.uk *
X * *
X * 9|3|1988 *
X * *
X * *
X **********************************************************/
X
X/*
X * May 29, 1991
X * Fixed a bug in the reallocation of the memory pool.
X * Whenever this hapened, the ``next_slot'' variable
X * was not updated.
X * Also, added the ``-'' feature, which, on its own,
X * signals the end of the option list, and treats the
X * rest of the command line as phrases only, regardless
X * of whether they start with a ``-'.
X */
X
X/*
X * May 28, 1991
X * Added option to read dictionary from stdin. This way,
X * ag can be used in a pipeline with both pre- and post filters.
X */
X
X/*
X * May 20, 1991
X * Fixed a bug in the parsing routine. Broke on SPARC's when
X * dereferencing a NULL pointer.
X * Bug report from: harry@neuron5.jpl.nasa.gov
X */
X
X/*
X * Jan. 30, 1991
X * rewrote the dictionary loader, now uses a pool for allocation.
X */
X
X/*
X * Sept. 28, 1990
X * removed "islower" & "isupper" - they didn't work...
X */
X
X/*
X * Sept. 26, 1990
X * wrote my own "toupper" & "tolower" so as to be compatible
X * with any system.
X */
X
X/*
X * March 9, 1988
X * Wrote initial version, as described in BYTE, Nov. 1987
X */
X
X#include <stdio.h>
X#include <signal.h>
X#include <malloc.h>
X
Xextern char *xmalloc (), *xrealloc ();
Xextern void xfree ();
Xextern char *cat_strings ();
Xextern char *xindex ();
Xextern void fatal ();
Xextern void _abort ();
X
X
X/* various definitions */
X
X#define STD_DICTIONARY "/usr/dict/words"
X#define MAX_LINELEN 70
X#define MAX_WORDLEN 32
X#define MAXMASKS 3
X#define bitmask long
X#define maskwidth (8 * sizeof (bitmask))
X#define large_pool_space 8192
X#define large_word_space 80
X#define large_stack_space 200
X#define tolower(c) hi2lo[c - 65]
X#define toupper(c) lo2hi[c - 65]
X
X/* some systems cannot handle lowercase in tolower
X and vice versa...use my own table for fast lookup */
X
Xchar hi2lo[] = {
X 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o',
X 'p','q','r','s','t','u','v','w','x','y','z',0,0,0,0,0,0,
X 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o',
X 'p','q','r','s','t','u','v','w','x','y','z'
X};
X
Xchar lo2hi[] = {
X 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
X 'P','Q','R','S','T','U','V','W', 'X','Y','Z', 0,0,0,0,0,0,
X 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
X 'P','Q','R','S','T','U','V','W', 'X','Y','Z'
X};
X
X
Xchar *program;
Xchar *usage = "[-d `dictionary'] [-a] [-v] [-V] [-w] [-W] [-s `SIZE'] [-o `outfile'] [phrase(s)]";
X
X/* 1 if only action is to print out the ellegible words [-W]*/
X
Xint words_only = 0;
X
X/* 1 if the ellegible words are to be printed out [-w]*/
X
Xint words_out = 0;
X
X/* size of smallest word in an angram.
X i.e. -s 2 would prevent angrams with singlelettered words [-s]*/
X
Xint min_size = 2;
X
X/* should we count `a' and `i' as complete words? [-a]*/
X
Xint do_ai = 0;
X
X/* speak up! [-v] */
X
Xint verbose = 0;
X
X/* 1 if write out version info [-V] */
X
Xint version = 0;
X
X/* file to write anagrams to, if any */
X
Xchar *outfile = NULL;
Xchar *infile = NULL;
X
Xchar version_string[] = "Anagram Finder v. 1.0";
X
Xint no_of_phrases = 0;
X
Xint pipeline = 0;
X
X
X/* phrase variables */
X
Xtypedef bitmask bitsig[MAXMASKS];
Xint freqs[26], letmask[26], letbit[26], letwidth[26], lastmask;
Xbitsig uflosig;
Xchar *phrase;
Xbitmask phrasesig[MAXMASKS];
X
X/* pool information */
X
Xchar *pool = NULL;
X
X/* dictionary information */
X
Xchar **wordlist = NULL;
Xshort int wordcount = 0;
Xbitmask *wordsigs;
X
X/* for printing anagrams */
X
Xchar **analist;
Xshort int anacount = 0;
Xshort int total = 0;
X
X
X/*************************************************************************/
X
X#define IS_NUMBER(X) ((X) >= '0' && (X) <= '9')
X#define IS_LETTER(c) (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z'))
X
Xint
Xstr_to_num (s)
X char *s;
X{
X int result = 0;
X
X while (*s) {
X if (IS_NUMBER(*s))
X result = (result * 10) + *s++ - '0';
X }
X return result;
X}
X
Xint
Xcandidate (word)
X register char *word;
X{
X register char c;
X register int count = 0;
X
X if (strlen (word) < min_size && !do_ai) return 0;
X while (c = word[count++]) {
X if (!IS_LETTER (c) ||
X (!xindex (phrase, tolower (c)) &&
X !xindex (phrase, toupper (c))))
X return 0;
X }
X if (do_ai && !word[1])
X return (xindex ("aAiI", word[0]) != 0);
X return 1;
X}
X
X
X
X/* prints out all the anagrams found so far, if any */
X
Xvoid
Xprintlist (list, no)
X char **list;
X short int no;
X{
X register int count;
X register int linelen = 0;
X
X for (count = 0; count < no; count++) {
X linelen += strlen (list[count]) + 1;
X if (linelen >= MAX_LINELEN) {
X linelen = 0;
X (void)fprintf (stdout, "\n");
X }
X (void)fprintf (stdout, "%s ", list[count]);
X }
X (void)fprintf (stdout, "\n");
X (void)fflush (stdout);
X}
X
X/* old version using log didn't work too well...
X use smalltalk's version of highBit instead */
Xint
Xfieldwidth (v)
X int v;
X{
X register int i = 1, bit = 1;
X
X if (v < 0) _abort ("Fieldwidth: negative number.");
X if (!v) return 2;
X while (v > bit) {
X i++; bit += bit + 1;
X }
X return (i + 2);
X}
X
X/* FROM BYTE, NOVEMBER 1987 */
Xvoid
Xmakefreqs (str, freq)
X register char *str;
X register int freq[];
X{
X register char c;
X register int f;
X
X for (f = 0; f < 26; f++)
X freq[f] = 0;
X while (c = *(str++)) {
X freq[tolower (c) - 97] += 1;
X }
X}
X
X/* FROM BYTE, NOVEMBER 1987 */
Xvoid
Xchoosefields (frq)
X int frq[];
X{
X register int letter, width;
X int curmask = 0, curbit = 0;
X
X for (letter = 0; letter < 26; letter++)
X if (frq[letter] != 0) {
X width = fieldwidth (frq[letter]);
X if ((curbit + width) > maskwidth) {
X if (++curmask >= MAXMASKS)
X _abort ("Phrase too long to handle.");
X curbit = 0;
X }
X letmask[letter] = curmask;
X letbit[letter] = curbit;
X letwidth[letter] = width;
X curbit += width;
X }
X lastmask = curmask;
X}
X
X/* FROM BYTE, NOVEMBER 1987 */
Xvoid
Xmakeonesig (str, sig)
X register char *str;
X register bitmask sig[];
X{
X register int i, j = 0;
X int sfreqs[26];
X register bitmask fr;
X
X makefreqs (str, sfreqs);
X for (i = 0; i <= lastmask; i++)
X sig[i] = 0;
X for (i = 0; i < 26; i++)
X if (sfreqs[i]) {
X fr = ((bitmask)sfreqs[i]) << letbit[i];
X sig[letmask[i]] += fr;
X j += fr;
X }
X}
X
X/* FROM BYTE, NOVEMBER 1987 */
Xvoid
Xmakeuf (frq)
X int frq[];
X{
X int i, bnum, bwidth;
X
X for (i = 0; i < MAXMASKS; i++)
X uflosig[i] = 0;
X for (i = 0; i < 26; i++)
X if (frq[i]) {
X bnum = letbit[i];
X bwidth = letwidth[i];
X uflosig[letmask[i]] += (1L << (bnum + bwidth - 1));
X }
X}
X
X#define DOMASK(MASK) { \
X newmask = curnode[MASK] - cursig[MASK]; \
X if (newmask & uflosig[MASK]) break; \
X newsig[MASK] = newmask; \
X bitsleft |= newmask; \
X}
X
X
X/* FROM BYTE, NOVEMBER 1987 */
X/* MODIFIED BY MLR */
Xvoid
Xfindanagrams (curword, curnode)
X register int curword;
X register bitmask *curnode;
X{
X bitsig newsig;
X register bitmask newmask, *cursig;
X register long bitsleft;
X int bsize = large_stack_space;
X
X cursig = &wordsigs[curword * (lastmask + 1)];
X while (curword < wordcount) {
X bitsleft = 0;
X switch (lastmask) {
X case 2:DOMASK(2)
X case 1:DOMASK(1)
X case 0:DOMASK(0)
X
X if (anacount == bsize) {
X bsize *= 2;
X analist = (char **)xrealloc ((char *)analist, bsize * sizeof (char *));
X }
X analist[anacount++] = wordlist[curword];
X if (!bitsleft) {
X printlist (analist, anacount);
X total++;
X }
X else findanagrams (curword, newsig);
X --anacount;
X }
X curword++;
X cursig += (lastmask + 1);
X }
X}
X
X
X/* If realloc moves the list around in memory
X * then update all pointers in the wordlist.
X */
X
Xvoid
Xadjust_list (list, offset, count)
X char **list;
X int offset, count;
X{
X register int i;
X
X for (i = 0; i < count; i++)
X list[i] += offset;
X}
X
X
Xvoid
Xread_dict ()
X{
X int psize = large_pool_space;
X int bsize = large_stack_space;
X int msize = large_stack_space * MAXMASKS;
X char *pend, *next_slot;
X
X if (verbose) {
X (void)fprintf (stderr, "\nLoading dictionary...");
X (void)fflush (stderr);
X }
X
X /* analist has to be set up here, as "findanagrams" is recursive */
X analist = (char **)xmalloc (bsize * sizeof (char *));
X wordlist = (char **) xmalloc (bsize * sizeof (char *));
X wordsigs = (bitmask *) xmalloc (msize * sizeof (bitmask));
X pool = (char *)xmalloc (psize * sizeof (char));
X pend = pool + psize;
X next_slot = pool;
X
X while (fscanf (stdin, "%s", next_slot) != EOF) {
X if (candidate (next_slot)) {
X
X /* if this entry would overflow stack, expand it */
X
X if (wordcount == bsize) {
X bsize *= 2; msize *= 2;
X wordlist = (char **)xrealloc ((char *)wordlist, bsize * sizeof (char *));
X wordsigs = (bitmask *)xrealloc ((char *)wordsigs, msize * sizeof (bitmask));
X }
X wordlist[wordcount] = next_slot;
X makeonesig (next_slot, &wordsigs[wordcount * (lastmask + 1)]);
X
X next_slot += strlen (next_slot) + 1;
X if ((next_slot + MAX_WORDLEN) >= pend) {
X char *old_pool = pool;
X
X psize *= 2;
X pool = (char *)xrealloc (pool, psize * sizeof (char));
X if (old_pool != pool)
X adjust_list (wordlist, pool - old_pool, wordcount);
X next_slot += pool - old_pool;
X pend = pool + psize;
X }
X wordcount++;
X }
X }
X if (!pipeline) (void)rewind (stdin);
X if (verbose) {
X (void)fprintf (stderr, "done\n");
X (void)fflush (stderr);
X }
X}
X
Xvoid
Xclean_up ()
X{
X /* first, free all strings allocated */
X xfree ((char *)pool);
X
X /* then, free the array of pointers to these strings */
X xfree ((char *)wordlist);
X
X /* then, free the array of pointers to the anagrams */
X xfree ((char *)analist);
X
X /* At last, free the array `wordsigs' */
X xfree ((char *)wordsigs);
X}
X
Xvoid
Xparse_flags (argc, argv)
X int argc;
X char *argv[];
X{
X int i, end_of_opts = 0;
X
X for (i = 1; i < argc; i++) {
X if (argv[i][0] == '-' && !end_of_opts) {
X register char *str = argv[i] + 1;
X
X switch (*str) {
X case NULL:
X case '-':
X end_of_opts = 1;
X break;
X
X case '|':
X return;
X
X case '\n':
X if (outfile == NULL)
X outfile = "";
X break;
X
X case 'a':
X do_ai = 1;
X break;
X
X case 'd':
X if (infile != NULL)
X _abort ("Infile specified twice.");
X if (argv[i + 1] != NULL) {
X infile = argv[++i];
X if (!strncmp (infile, "-", 1)) {
X infile = "";
X pipeline = 1;
X }
X }
X else
X _abort ("No infile specified.");
X break;
X
X case 'o':
X if (outfile != NULL)
X _abort ("Outfile specified twice.");
X if (argv[i + 1] != NULL) {
X outfile = argv[++i];
X if (!strncmp (outfile, "-", 1))
X outfile = "";
X }
X else
X _abort ("No outfile specified.");
X break;
X
X case 's':
X if (argv[i + 1] != NULL)
X min_size = str_to_num (argv[++i]);
X else
X _abort ("No size specified.");
X break;
X
X case 'v':
X verbose = 1;
X break;
X
X case 'V':
X version = 1;
X break;
X
X case 'w':
X words_out = 1;
X break;
X
X case 'W':
X words_only = 1;
X break;
X
X default : {
X char *s = cat_strings ("Unrecognized flag: \"", str, "\".");
X _abort (s);
X }
X }
X }
X else if (++no_of_phrases != i)
X argv[no_of_phrases] = argv[i];
X }
X}
X
Xvoid
Xdo_all (argv)
X char *argv[];
X{
X int i, j;
X
X for (i = 1; i <= no_of_phrases; i++) {
X
X phrase = argv[i];
X wordcount = 0;
X anacount = 0;
X total = 0;
X
X makefreqs (phrase, freqs);
X choosefields (freqs);
X makeonesig (phrase, phrasesig);
X makeuf (freqs);
X read_dict ();
X if (words_out || words_only) {
X (void)fprintf (stdout, "number of words read : %d\n", wordcount);
X (void)fflush (stdout);
X printlist (wordlist, wordcount);
X }
X if (words_only)
X continue;
X if (verbose) {
X (void)fprintf (stderr, "\nStarting generator...");
X
X (void)fprintf (stdout, "\n Anagrams generated from \"%s\" :", phrase);
X (void)fprintf (stdout, "\n--------------------------");
X for (j = 0; j < strlen (phrase); j++)
X (void)fprintf (stdout, "-");
X (void)fprintf (stdout, "---\n");
X (void)fflush (stdout);
X }
X
X /* Find all anagrams asociated with the specified pattern */
X
X findanagrams (0, phrasesig);
X if (verbose) {
X (void)fprintf (stdout, "\nNo. of anagrams : %ld\n", total);
X (void)fprintf (stderr, "done\n");
X }
X clean_up ();
X }
X
X}
X
Xmain (argc, argv)
X int argc;
X char **argv;
X{
X /* set up interrupt handler */
X if (signal (SIGINT, SIG_IGN) != SIG_IGN)
X signal (SIGINT, fatal);
X if (signal (SIGKILL, SIG_IGN) != SIG_IGN)
X signal (SIGKILL, fatal);
X
X
X program = argv[0];
X
X if (argc == 1)
X _abort (usage);
X
X parse_flags (argc, argv);
X
X if (version) {
X (void)fprintf (stderr, "%s\n", version_string);
X if (no_of_phrases == 0)
X (void)exit (0);
X }
X if (no_of_phrases == 0)
X _abort ("No pattern(s) specified.");
X
X /* Open input file */
X if (!infile)
X infile = STD_DICTIONARY;
X if (!strcmp (infile, ""))
X infile = "stdin";
X else if (!freopen (infile, "r", stdin)) {
X char *s = cat_strings ("Couldn't open ", infile, " for input.");
X _abort (s);
X }
X
X /* Open output file */
X if (!outfile || !strcmp (outfile, ""))
X outfile = "stdout";
X else if (!freopen (outfile, "w", stdout)) {
X char *s = cat_strings ("Couldn't open ", outfile, " for output.");
X _abort (s);
X }
X
X if (pipeline && no_of_phrases > 1) {
X (void)fprintf (stderr, "Only 1 phrase when reading from stdin.\n");
X no_of_phrases = 1;
X }
X do_all (argv);
X return (0);
X}
X
X
X
Xchar *
Xxrealloc (ptr, size)
X char *ptr;
X int size;
X{
X register char *result = (char *)realloc (ptr, (unsigned)size);
X if (!result)
X _abort ("Virtual memory exhausted.");
X return result;
X}
X
Xchar *
Xxmalloc (size)
X int size;
X{
X register char *result = (char *)calloc (1, (unsigned)size);
X if (!result)
X _abort ("Virtual memory exhausted.");
X return result;
X}
X
Xvoid
Xxfree (ptr)
X char *ptr;
X{
X if (ptr) free (ptr);
X}
X
Xvoid
Xfatal (signum)
X int signum;
X{
X signal (signum, SIG_DFL);
X}
X
Xchar *
Xcat_strings (s1, s2, s3)
X char *s1, *s2, *s3;
X{
X int len1 = strlen (s1), len2 = strlen (s2), len3 = strlen (s3);
X char *s = (char *) xmalloc (len1 + len2 + len3 + 1);
X
X (void)strcpy (s, s1);
X (void)strcpy (s + len1, s2);
X (void)strcpy (s + len1 + len2, s3);
X *(s + len1 + len2 + len3) = 0;
X
X return s;
X}
X
X/* BSD and SYSV use different names, so use my own */
X
Xchar *
Xxindex (s, c)
X register char *s, c;
X{
X while (*s) {
X if (*s == c) return (s);
X s++;
X }
X return 0;
X}
X
Xvoid
X_abort (arg)
X char *arg;
X{
X (void)fprintf (stderr, "%s: ", program);
X (void)fprintf (stderr, arg);
X (void)fprintf (stderr, "\n");
X (void)fflush (stderr);
X (void)exit (1);
X}
END_OF_FILE
if test 17694 -ne `wc -c <'anagram.c'`; then
echo shar: \"'anagram.c'\" unpacked with wrong size!
fi
# end of 'anagram.c'
fi
if test -f 'postf.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'postf.c'\"
else
echo shar: Extracting \"'postf.c'\" \(1834 characters\)
sed "s/^X//" >'postf.c' <<'END_OF_FILE'
X/*
X ANAGRAM FILTER
X
X Sean Barrett May 1991
X
X This post-filter for anagramming removes all output anagrams
X which do not meet certain criteria. This documentation
X assumes the output filename from compiling is "postf".
X
X The default criteria is that only entries which use
X a 5-or-more-letter word or entries which have an
X average wordlength of 4 are approved.
X
X These can be altered on the command line by supplying
X paramters:
X
X postf <min-length> [<average-length>]
X
X For example,
X
X postf 6 3
X
X will accept any entry with a 6 or-more letter word, or
X any entry with an average word length of at least three.
X
X The default is
X
X postf 5 4
X
X and if the only one number is supplied, the second one is
X taken to be 4.
X
X It is generally meaningless to use a min-length lower
X than the average length.
X
X To only do a min-length check, set the average length
X arbitrarily high (any number higher than the min-length).
X
X To only do an average-length check, set the min-length
X arbitrarily high (higher than the longest entry in the
X dictionary--99 should be plenty).
X*/
X
X#include <stdio.h>
Xint MIN = 5;
Xint MIN_AVERAGE=4;
X
Xint main(argc,argv)
Xint argc;
Xchar **argv;
X{
X char s[128],*p;
X char c;
X int flag,words,count,this;
X
X if (argc>1)
X MIN = atoi(argv[1]);
X if (argc==3)
X MIN_AVERAGE = atoi(argv[2]);
X if (argc>3) {
X printf("Usage: %s [<min-word-length> [<average-word-length>]]\n",
X argv[0]);
X exit(0);
X }
X
X while(!(feof(stdin))) { /* for each word */
X
X p = s;
X this = 0;
X flag = 0;
X words= 1;
X count= 0;
X
X while ((c=fgetc(stdin))!='\n' && c!=-1) {
X *p++ = c;
X if (c==' ') {
X if (this > MIN)
X flag = 1;
X ++words;
X this =0 ;
X } else {
X ++this;
X ++count;
X }
X }
X *p='\n';
X *++p=0;
X
X if (flag || this>MIN || MIN_AVERAGE*words<count)
X fputs(s, stdout);
X }
X return 0;
X}
END_OF_FILE
if test 1834 -ne `wc -c <'postf.c'`; then
echo shar: \"'postf.c'\" unpacked with wrong size!
fi
# end of 'postf.c'
fi
if test -f 'pref.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'pref.c'\"
else
echo shar: Extracting \"'pref.c'\" \(7149 characters\)
sed "s/^X//" >'pref.c' <<'END_OF_FILE'
X# include "stdio.h"
X# define U(x) x
X# define NLSTATE yyprevious=YYNEWLINE
X# define BEGIN yybgin = yysvec + 1 +
X# define INITIAL 0
X# define YYLERR yysvec
X# define YYSTATE (yyestate-yysvec-1)
X# define YYOPTIM 1
X# define YYLMAX BUFSIZ
X# define output(c) putc(c,yyout)
X# define input() (((yytchar=yysptr>yysbuf?U(*--yysptr):getc(yyin))==10?(yylineno++,yytchar):yytchar)==EOF?0:yytchar)
X# define unput(c) {yytchar= (c);if(yytchar=='\n')yylineno--;*yysptr++=yytchar;}
X# define yymore() (yymorfg=1)
X# define ECHO fprintf(yyout, "%s",yytext)
X# define REJECT { nstr = yyreject(); goto yyfussy;}
Xint yyleng; extern char yytext[];
Xint yymorfg;
Xextern char *yysptr, yysbuf[];
Xint yytchar;
XFILE *yyin = {stdin}, *yyout = {stdout};
Xextern int yylineno;
Xstruct yysvf {
X struct yywork *yystoff;
X struct yysvf *yyother;
X int *yystops;};
Xstruct yysvf *yyestate;
Xextern struct yysvf yysvec[], *yybgin;
X# define YYNEWLINE 10
Xyylex(){
Xint nstr; extern int yyprevious;
Xwhile((nstr = yylook()) >= 0)
Xyyfussy: switch(nstr){
Xcase 0:
Xif(yywrap()) return(0); break;
Xcase 1:
X{ ECHO; printf("%\n"); }
Xbreak;
Xcase 2:
X { }
Xbreak;
Xcase 3:
X { }
Xbreak;
Xcase -1:
Xbreak;
Xdefault:
Xfprintf(yyout,"bad switch yylook %d",nstr);
X} return(0); }
X/* end of yylex */
Xyywrap() { return 1; }
X
Xint yyvstop[] = {
X0,
X
X2,
X0,
X
X3,
X0,
X
X2,
X-1,
X0,
X
X1,
X0,
X
X-1,
X0,
X0};
X# define YYTYPE char
Xstruct yywork { YYTYPE verify, advance; } yycrank[] = {
X0,0, 0,0, 1,3, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 1,4,
X0,0, 5,6, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 0,0, 0,0,
X0,0, 0,0, 1,3, 2,5,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 5,7, 5,7,
X5,7, 5,7, 0,0, 0,0,
X0,0};
Xstruct yysvf yysvec[] = {
X0, 0, 0,
Xyycrank+-1, 0, 0,
Xyycrank+-2, yysvec+1, 0,
Xyycrank+0, 0, yyvstop+1,
Xyycrank+0, 0, yyvstop+3,
Xyycrank+3, 0, yyvstop+5,
Xyycrank+0, 0, yyvstop+8,
Xyycrank+0, yysvec+5, yyvstop+10,
X0, 0, 0};
Xstruct yywork *yytop = yycrank+125;
Xstruct yysvf *yybgin = yysvec+1;
Xchar yymatch[] = {
X00 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,012 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,01 ,01 ,01 ,01 ,01 ,01 ,01 ,
X01 ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,
X'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,
X'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,'a' ,
X'a' ,'a' ,'a' ,01 ,01 ,01 ,01 ,01 ,
X0};
Xchar yyextra[] = {
X0,1,0,0,0,0,0,0,
X0};
X#ifndef lint
Xstatic char ncform_sccsid[] = "@(#)ncform 1.2 86/10/08 SMI"; /* from S5R2 1.2 */
X#endif
X
Xint yylineno =1;
X# define YYU(x) x
X# define NLSTATE yyprevious=YYNEWLINE
Xchar yytext[YYLMAX];
Xstruct yysvf *yylstate [YYLMAX], **yylsp, **yyolsp;
Xchar yysbuf[YYLMAX];
Xchar *yysptr = yysbuf;
Xint *yyfnd;
Xextern struct yysvf *yyestate;
Xint yyprevious = YYNEWLINE;
Xyylook(){
X register struct yysvf *yystate, **lsp;
X register struct yywork *yyt;
X struct yysvf *yyz;
X int yych, yyfirst;
X struct yywork *yyr;
X# ifdef LEXDEBUG
X int debug;
X# endif
X char *yylastch;
X /* start off machines */
X# ifdef LEXDEBUG
X debug = 0;
X# endif
X yyfirst=1;
X if (!yymorfg)
X yylastch = yytext;
X else {
X yymorfg=0;
X yylastch = yytext+yyleng;
X }
X for(;;){
X lsp = yylstate;
X yyestate = yystate = yybgin;
X if (yyprevious==YYNEWLINE) yystate++;
X for (;;){
X# ifdef LEXDEBUG
X if(debug)fprintf(yyout,"state %d\n",yystate-yysvec-1);
X# endif
X yyt = yystate->yystoff;
X if(yyt == yycrank && !yyfirst){ /* may not be any transitions */
X yyz = yystate->yyother;
X if(yyz == 0)break;
X if(yyz->yystoff == yycrank)break;
X }
X *yylastch++ = yych = input();
X yyfirst=0;
X tryagain:
X# ifdef LEXDEBUG
X if(debug){
X fprintf(yyout,"char ");
X allprint(yych);
X putchar('\n');
X }
X# endif
X yyr = yyt;
X if ( (int)yyt > (int)yycrank){
X yyt = yyr + yych;
X if (yyt <= yytop && yyt->verify+yysvec == yystate){
X if(yyt->advance+yysvec == YYLERR) /* error transitions */
X {unput(*--yylastch);break;}
X *lsp++ = yystate = yyt->advance+yysvec;
X goto contin;
X }
X }
X# ifdef YYOPTIM
X else if((int)yyt < (int)yycrank) { /* r < yycrank */
X yyt = yyr = yycrank+(yycrank-yyt);
X# ifdef LEXDEBUG
X if(debug)fprintf(yyout,"compressed state\n");
X# endif
X yyt = yyt + yych;
X if(yyt <= yytop && yyt->verify+yysvec == yystate){
X if(yyt->advance+yysvec == YYLERR) /* error transitions */
X {unput(*--yylastch);break;}
X *lsp++ = yystate = yyt->advance+yysvec;
X goto contin;
X }
X yyt = yyr + YYU(yymatch[yych]);
X# ifdef LEXDEBUG
X if(debug){
X fprintf(yyout,"try fall back character ");
X allprint(YYU(yymatch[yych]));
X putchar('\n');
X }
X# endif
X if(yyt <= yytop && yyt->verify+yysvec == yystate){
X if(yyt->advance+yysvec == YYLERR) /* error transition */
X {unput(*--yylastch);break;}
X *lsp++ = yystate = yyt->advance+yysvec;
X goto contin;
X }
X }
X if ((yystate = yystate->yyother) && (yyt= yystate->yystoff) != yycrank){
X# ifdef LEXDEBUG
X if(debug)fprintf(yyout,"fall back to state %d\n",yystate-yysvec-1);
X# endif
X goto tryagain;
X }
X# endif
X else
X {unput(*--yylastch);break;}
X contin:
X# ifdef LEXDEBUG
X if(debug){
X fprintf(yyout,"state %d char ",yystate-yysvec-1);
X allprint(yych);
X putchar('\n');
X }
X# endif
X ;
X }
X# ifdef LEXDEBUG
X if(debug){
X fprintf(yyout,"stopped at %d with ",*(lsp-1)-yysvec-1);
X allprint(yych);
X putchar('\n');
X }
X# endif
X while (lsp-- > yylstate){
X *yylastch-- = 0;
X if (*lsp != 0 && (yyfnd= (*lsp)->yystops) && *yyfnd > 0){
X yyolsp = lsp;
X if(yyextra[*yyfnd]){ /* must backup */
X while(yyback((*lsp)->yystops,-*yyfnd) != 1 && lsp > yylstate){
X lsp--;
X unput(*yylastch--);
X }
X }
X yyprevious = YYU(*yylastch);
X yylsp = lsp;
X yyleng = yylastch-yytext+1;
X yytext[yyleng] = 0;
X# ifdef LEXDEBUG
X if(debug){
X fprintf(yyout,"\nmatch ");
X sprint(yytext);
X fprintf(yyout," action %d\n",*yyfnd);
X }
X# endif
X return(*yyfnd++);
X }
X unput(*yylastch);
X }
X if (yytext[0] == 0 /* && feof(yyin) */)
X {
X yysptr=yysbuf;
X return(0);
X }
X yyprevious = yytext[0] = input();
X if (yyprevious>0)
X output(yyprevious);
X yylastch=yytext;
X# ifdef LEXDEBUG
X if(debug)putchar('\n');
X# endif
X }
X }
Xyyback(p, m)
X int *p;
X{
Xif (p==0) return(0);
Xwhile (*p)
X {
X if (*p++ == m)
X return(1);
X }
Xreturn(0);
X}
X /* the following are only used in the lex library */
Xyyinput(){
X return(input());
X }
Xyyoutput(c)
X int c; {
X output(c);
X }
Xyyunput(c)
X int c; {
X unput(c);
X }
END_OF_FILE
if test 7149 -ne `wc -c <'pref.c'`; then
echo shar: \"'pref.c'\" unpacked with wrong size!
fi
# end of 'pref.c'
fi
if test -f 'pref.l' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'pref.l'\"
else
echo shar: Extracting \"'pref.l'\" \(473 characters\)
sed "s/^X//" >'pref.l' <<'END_OF_FILE'
X/* ANAGRAM FILTER */
X
X/* Sean Barrett May 1991 */
X
X/* This lex filter removes all numeric and capitalized entries */
X/* from stdin. This may result in a more "useful" dictionary */
X/* for anagramming from, which you can do by */
X
X/* % lex pre_filter.l */
X/* % cc -ll -o pref lex.yy.c */
X/* % pref </usr/dict/words >words */
X
X/* and by tailoring anagram.c to look for the right dictionary. */
X
X%%
X^[a-z]+$ { ECHO; printf("%\n"); }
X. { }
X\n { }
X%%
Xyywrap() { return 1; }
X
END_OF_FILE
if test 473 -ne `wc -c <'pref.l'`; then
echo shar: \"'pref.l'\" unpacked with wrong size!
fi
# end of 'pref.l'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have the archive.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0