From demon!pipex!uunet!think.com!spdcc!merk!roscom!monty Fri Mar 5 01:55:09 GMT 1993 Article: 750 of alt.sources Newsgroups: alt.sources Path: demon!pipex!uunet!think.com!spdcc!merk!roscom!monty From: Monty Solomon Subject: Ars Magna v1.1 anagram generator Message-ID: <1993Mar4.151523.10347@proponent.com> Followup-To: alt.sources.d Sender: monty@proponent.com (Monty Solomon) Reply-To: Monty Solomon Organization: Proponent Date: Thu, 4 Mar 1993 15:15:23 GMT Expires: Thu, 18 Mar 1993 15:15:24 GMT Lines: 1413 Archive-name: arsmagna Submitted-by: monty@proponent.COM This is the source for Mike Morton's Ars Magna v1.1. Ars Magna generates anagrams and is based on the algorithm as described in the November 1987 issue of BYTE Magazine. #! /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 'ars.c' <<'END_OF_FILE' X/* X Copyright (c) Michael S. Morton X 1986, 1987, 1988, 1989, 1990, 1991, 1992, 1993 X All rights reserved. X X Permission is granted to anyone to use this software for any purpose on X any computer, and to alter it and redistribute it freely, subject X to the following restrictions: X X 0. This software is provided "as is" and without any express or implied X warranties, including, without limitation, the implied warranties of X merchantability and fitness for a particular purpose. X X 1. The author is not responsible for the consequences of the use of this X software, no matter how awful, even if they arise from flaws in it. X X 2. The origin of this software must not be misrepresented, either by X explicit claim or by omission. The credits must mention that this X software is based on the algorithm as described in the November 1987 X issue of BYTE Magazine. The credits must appear in the About... dialog X and any documentation. X X 3. Altered versions must be plainly marked as such, and must not be X misrepresented as being the original software. The credits must appear X in the About... dialog and any documentation. X X 4. This software may not be sold except as part of a substantially X different program. X X 5. The Boston Museum of Science is expressly forbidden to use this program X for profit or to produce revenue. X X 6. This notice may not be removed or altered. X*/ X X/* [Set tabs to 2 characters.] X X This is the source for Ars Magna v1.1, a version with some improvements but X at least one serious bug. It was never widely released. X X This source is not up-to-date, except for this comment. X X I plan to return to work on anagram engines and user interfaces someday, but X it's not going to be soon. I've been thinking hard about user interfaces X for this app since 1984 (the original app was done in '82), and haven't come X up with anything good. My hope is that various developers will experiment, X steal each other's best ideas, and in general have a real good time. I've X already seen some people take Ars Magna's bad user interface and produce a X worse one; get creative here, folks, will ya? X X A few disconnected ideas, more or less off the top of my head: X X * I want to be able to say "Show me everything with word ____" X * Then, of course, the remaining mainstream anagrams omit that word X * Similarly, I want to be able to say "Show me everything with words ____ X and ____". X * I want to be able to say "Don't ever show me this word during this session" X * I want to be able to say "Don't ever show me this word, ever" X * This version tries to do one-word anagrams, then two-word, etc. It X tends to lock up at the each length; there's some obvious pruning X that can be done here. X * Reviewing the output can take hours, so: X (1) the user should be able to do nearly everything with the keyboard X (2) they should be able to save their complete search state X * The app should handle various dictionary formats, and set one or more X default dictionaries as a preference. X * I've never been able to find foreign-language dictionaries; anyone X know if there are public-domain ones around? X * Word order and search order are very important to producing good X anagrams early in the search. What are the possible orderings? X Which help in which ways? How should the user control them? X * The list of eligible words should be displayed somewhere. The user X should be able to save it, specify hot words to try first, etc. X * There should be a way to show incomplete anagrams, with the user X specifying the maximum number of unused letters to show (zero would X make the app behave as it does now). They should be able to rearrange X unused letters under keyboard or mouse control. X * Once you've found an anagram which looks interesting, the app should X let you rearrange them under keyboard or mouse control, or quickly X display all orderings of the words. Of course, a quick command should X save an anagram to the list of cool anagrams. X * When listing anagrams, a change in a given column should be highlighted X to wake up a bored user. This version does this crudely with capitals X when a word first appears in a column, as in this example: X CLIMATE HO MR NO X climate ho mr ON X climate MR NO OH X climate mr OH ON X * I hate retyping anagrams for posting or publication, so the app should: X (1) Allow easy word-shuffling and punctuation and capitalization X changes in the saved list of cool anagrams. X (2) Quickly check a text file or the clipboard's contents to make X sure they're right. X * You should be able to export the list of cool anagrams to the X clipboard or a text file. X * The current bit-banging scheme makes sure that an anagram contains X exactly the right number of letters, by adding them up and checking X that the count is exactly right. This could be generalized to make X sure the count is in a certain range for an attribute OTHER than a X letter. This is useful for: X (a) I'm using several dictionaries, but only one is new, so show me X only anagrams with one or more words from that dictionary. X (b) I want to see no more than 2 one-letter words. X (c) I want to see at least one word that I've marked as interesting. X * Or, if you want to use the counter scheme for "no more than one of" X or "at least one of", you could use AND and OR instead of addition. X * I should be able to quickly count all the anagrams which will result X from a partial anagram I've found, to help me decide when to explore. X * I've tried a NeXT-style browser interface and, at least the way I did X it, it was lousy. Not interactive enough. X * You might be able to prune or order anagrams on the basis of available X or constructed information on word-pair frequencies in natural languages. X This idea strikes me as promising, but I haven't done anything with it. X * Extra credit: Parse the anagrams as natural language to find good ones. X X Don't expect that doing all of the above will give you a good app. This is X just a laundry list, not an overall vision of a good UI. I've talked to X good anagrammers, and they work on paper and in their heads -- devising an X interface which is easier for them, not just for a beginner, will be hard. X X If you develop an app, prototype or not, commercial or not, I'd be interested X in seeing it and commenting on the UI. If you feel like sharing the source, X I'd be interested in that, too. X X Keep in touch, X Mr. Machine Tool X February, 1993 X X Email: Mike_Morton@Proponent.com X Paper: Mike Morton, POB 11299, Honolulu, HI 96828 X*/ X X#include "stdio.h" X#include "stdlib.h" X#include "string.h" X#include "console.h" X#include "MacTypes.h" X#include "FileMgr.h" X X/* Easily changeable constants: */ X#define STRMAX 100 /* size of some strings */ X#define MAXFILES 10 /* maximum number of dictionaries */ X#define MAXMASKS 5 /* number of "masks" for bitbanging */ X /* note that doanagram() depends on MAXMASKS */ X#define DFTFILE "anagram dict" /* default dictionary name */ X#define WPTRDELTA 512 /* # of word ptrs to add */ X#define TEXBSIZE 2048 /* size of a block of text */ X#define DOTFREQ 25 /* anagrams per dot, when filing/counting */ X#define DOTSPERLINE 40 /* dots per line for filing/counting */ X#define PAGESIZE 22 /* lines between prompts */ X#define WORDCHUNK 5000 /* size of chunks for words */ X X/* Not-so-easily-changeable things: */ X#define mask long /* masks are stored in longwords */ X#define maskwidth 8*sizeof(mask) /* and their size is important */ X X/* Global stuff -- phrase information: */ Xchar phrase [STRMAX]; /* the phrase to be anagrammed */ Xchar origphrase [STRMAX]; /* unmunged copy of phrase */ Xshort freqs [26]; /* frequency table for phrase */ Xshort letmask [26], letbit [26]; /* mask, bit positions for each letter */ Xshort letwidth[26]; /* width in mask of each letter */ Xshort usedmasks; /* count of used masks */ Xshort minWords, maxWords; X Xmask oflodesc [MAXMASKS]; /* descriptor used to detect overflow */ Xmask phrasedesc [MAXMASKS]; /* descriptor for main phrase */ Xmask startdesc [MAXMASKS]; /* starting descriptor for search */ X X/* Global stuff -- Dictionary information */ Xshort numdicts = 0; /* number of dictionaries */ XFILE *dicts [MAXFILES]; /* dictionary files */ Xshort numwords; /* number of eligible words */ Xshort maxwords = 0; /* number of words which fit in *wordlist */ Xchar **wordlist = NULL; /* words[0..maxwords-1], X with 0..numwords-1 used */ Xmask *worddescs; /* descriptors [0..numwords-1] */ Xstruct wchunk { X struct wchunk *next; X char text [WORDCHUNK]; X}; Xchar *nextwcp = NULL; /* pointer to next char to fill */ Xshort nextwleft = 0; /* chars left in this block */ Xstruct wchunk *curchunk = NULL; /* pointer to current chunk */ Xstruct wchunk *chunkhead = NULL; /* pointer to first chunk */ X X/* Global stuff -- For printing anagrams */ Xchar *anawords [20]; /* stacked words */ Xchar **anaptr; /* pointer to first unused slot */ XFILE *anafile; /* stdin for screen, output file, or NULL */ Xshort silent; /* 1 iff not printing to screen */ Xunsigned long anacount; /* number of anagrams found */ Xunsigned long startt, endt, tottime; /* timing information */ Xshort paging; /* pause after each screenful? */ X Xenum { /* types of help */ X dict1, dict1dft, dict2, X anahelp, X scf, X overadd, X quithelp, X helppage, helppaused X}; X X#define DR register /* Debugging Register */ X#define pf printf X Xvoid dophrase (void); Xvoid clean (char *s); Xvoid cleannl (char *s); Xvoid makefreqs (char *s); Xshort findbits (void); Xshort findbitwidth (short count); Xvoid makeof (void); Xshort makedesc (char *str, mask desc[]); Xshort okword (char *str); Xshort getdicts (void); Xshort getwords (void); Xshort storeword (char *word); Xvoid freewords (void); Xshort mycmp (char **s1p, char **s2p); Xvoid sortwords (void); Xvoid nodups (void); Xvoid printwords (void); Xvoid makeWrite (FILE *f); Xshort makemasks (void); Xvoid freemasks (void); Xshort doanagrams (short curword, mask *curstate, short wordsLeft); Xshort printana (void); Xshort exitcheck (void); Xvoid getoutput (void); Xshort openoutfile (char *name); Xshort getline (char *prompt, char *keywords, short keyneeded, char *dft, char *reprompt, X short helpstate, char *response); Xvoid dohelp (short state); Xshort keyfind (char *words, char *oneword); Xshort findstr (char *master, char *sub); Xshort strNequal (char *s1, char *s2, short size); Xlong msec (void); Xvoid starttimer (void); Xvoid stoptimer (void); Xvoid inittimer (void); Xvoid printtime (void); Xvoid chkerr (short i); X Xvoid main (void) X{ X cgotoxy (0, 0, stdout); /* don't scroll initial stuff */ X pf ("***************************************************************************** ***\n"); X pf ("* A R S M A G N A (TM), an anagram generator, version 1.1 (24 Sep '90) *\n"); X pf ("* Copyright 1986-1993 Michael Morton (aka "Mr. Machine Tool", "Harmonic motel")*\n"); X pf ("* All rights reserved. *\n"); X pf ("* Based on my algorithm as described in the November 1987 issue of BYTE. *\n"); X pf ("***************************************************************************** ***\n"); X pf ("\n"); X pf ("QUICK...This program finds anagrams for a phrase or name. You can just press\n"); X pf (" INFO RETURN for most questions, or type "HELP" at any point for more info.\n"); X pf ("\n"); X X numdicts = getdicts (); /* just once: open up dictionaries */ X X while (1) X { X printf ("\n"); X getline ("What's the phrase you'd like to anagram? ", X "", 0, "", "\nWhat's the phrase you'd like to anagram? ", X anahelp, phrase); X strcpy (origphrase, phrase); /* remember it, before we... */ X clean (phrase); /* clean up the string */ X X if (strlen (phrase) == 0) /* nothing there? */ X printf ("Come on, don't be shy... try something!\n"); X else dophrase (); X X if ((anafile != NULL) && (anafile != stdout)) X fclose (anafile); /* heavy-handed to put this here... */ X } /* end of infinite main loop */ X} /* end of main program */ X Xvoid dophrase () X{ X short i; /* counter for masks */ X char response [STRMAX]; /* dummy input buffer */ X short wordCount; X short keynum; X X makefreqs (phrase); /* build the frequency table */ X X if (findbits () == 0) /* choose bit fields; check size */ X { X printf ("Sorry -- that phrase is too long to handle.\n"); X return; X } X X getoutput(); /* where should we put this stuff? */ X X if (anafile == stdout) X paging = getline ("Want output to pause after each page [RETURN for YES]? ", X "#no#yes", 1, "yes", X "Please type YES or NO. Want output to pause after each page? ", X helppage, response); X else paging = 0; /* no paging if not printing */ X X makeof (); /* compute overflow and "full" descriptors */ X X makedesc (phrase, phrasedesc); /* make descriptor for phrase; ignore result (can't fail) */ X X for (i = 0; i <= usedmasks; i++) /* loop through all masks we used... */ X startdesc[i] = /* and for each one, the starting descriptor... */ X phrasedesc[i]; /* ...is the full one */ X X getwords (); /* read in words for this phrase */ X if (numwords == 0) return; /* bag it? OK */ X sortwords (); /* get 'em in the right order */ X nodups (); /* eliminate duplicate words */ X printwords (); /* dump 'em to a file */ X if (makemasks () == 0) return; /* make masks for them all -- return on error */ X X inittimer (); X X if (anafile != NULL) X chkerr (fprintf (anafile, "\n\n*** anagrams for '%s' ***\n\n", origphrase)); X for (wordCount = 1; wordCount < 100; wordCount++) X { X anaptr = anawords; /* point to base of stack */ X anacount = 0; /* no anagrams found so far */ X doanagrams (0, startdesc, wordCount); /* print (or whatever) all anagrams */ X if (anafile != stdout) printf ("\n"); /* don't print after dots */ X printf ("Anagrams found with %d words: %ld.\n", wordCount, anacount); X stoptimer (); X keynum = getline (" ...more (next size of anagram)... ", X "#stop", 0, "", " ...more (next size of anagram)... ", X helppaused, response); X starttimer (); X if (keynum == 0) /* bag this anagram? */ X wordCount = 100; /* break the loop */ X } X X printtime (); X X freemasks (); /* ditch the masks */ X freewords (); /* ditch the words */ X} /* end of dophrase() */ X X/* clean -- Clean up a string in place: map all letters to lowercase and X discard everything else. */ X Xvoid clean (s) X DR char *s; /* UPDATE: string to clean */ X{ X DR char *in = s, *out = s; /* reading, writing pointers */ X DR char c; /* working copy of character */ X X while (c = *in++) /* loop through whole input string */ X { X if ( (c>='A') && (c<='Z') ) /* uppercase alphabetic? */ X c -= ('A' - 'a'); /* yup: map it to lower */ X if ( (c>='a') && (c<='z') ) /* after mapping, is it lower case? */ X *out++ = c; /* yup: store it */ X } /* end of loop mapping&discarding */ X *out++ = c; /* store the final null */ X} /* end of clean() */ X X/* cleannl -- Toss all newlines out of a string, in place. */ X Xvoid cleannl (s) X register char *s; X{ X register char *in = s; X register char *out = s; X register char c; X X while (c = *in++) X if (c != '\n') X *out++ = c; X *out++ = '\0'; X} X X/* makefreqs -- Take a phrase and produce a frequency table from it. The X phrase has already been cleaned up, so we know it contains only the X characters 'a'..'z'. */ X Xvoid makefreqs (s) X DR char *s; /* INPUT: string to analyze */ X /* GLOBAL OUTPUT: frequency table */ X{ X DR short i; /* traditional loop index */ X X for (i = 0; i<26; i++) /* loop through and initialize... */ X freqs [i] = 0; /* ...the frequency array */ X X while (*s) /* while there's more to the string... */ X { X freqs [*s - 'a'] ++; /* incremement slot for this letter */ X s++; /* and skip to the next character */ X } /* end of loop through string */ X X} /* end of makefreqs() */ X X X/* findbits -- Given the frequency table, find the bit position for each X character found in the original phrase. Nonexistent letters are X ignored. We may run out of room in the masks in doing this; we X return 0 on failure. */ X Xshort findbits () /* zero <=> failure */ X /* GLOBAL INPUT: frequency table */ X /* GLOBAL OUTPUT: whichword[], whichbit[], count of used masks */ X{ X short letter; /* letter value (0..25) */ X short curword = 0, curbit = 0; /* initial bit and word */ X short width; /* bitwidth of letter's field */ X X for (letter = 0; letter < 26; letter++) /* loop through all letters */ X { X if (freqs[letter] != 0) /* any occurrences of this letter? */ X { /* yes: find where it'll go */ X width = findbitwidth (freqs [letter]); /* how much room does it need? */ X if (curbit+width > maskwidth) /* too wide for this word? */ X { /* yes: have to kick into next word */ X curword++; curbit = 0; /* go to start of next word */ X if (curword >= MAXMASKS) /* no more room? */ X return (0); /* no more: report failure */ X } /* end of kicking into next word */ X X letmask [letter] = curword; /* remember which word we go in */ X letbit [letter] = curbit; /* and bit position in the word */ X letwidth [letter] = width; /* and the width */ X curbit += width; /* advance past this bit field */ X } /* end of handling letter found in phrase */ X } /* end of loop through A..Z */ X X usedmasks = curword; /* remember highest used mask */ X return (1); /* indicate success */ X} /* end of findbits() */ X X/* findbitwidth -- Find the number of bits needed to store a single letter X up to the specified frequency. Our output looks like this: X Frequency: Width (+ one overflow bit) X 0 X 1 1 (+ 1) X 2..3 2 (+ 1) X 4..7 3 (+ 1) X ...etc. */ X Xshort findbitwidth (count) /* find width of field to hold "count" */ X DR short count; /* INPUT: frequency of letter */ X{ X DR short width = 0; /* result */ X X while (count != 0) /* loop 'til all bits discarded */ X { X width++; /* counting the bits... */ X count >>= 1; /* ...and chucking out one more */ X } /* end of loop counting bits */ X X width ++; /* and one more for the overflow */ X return (width); /* that's the answer */ X} /* end of findbitwidth() */ X X X/* makeof -- Find the descriptors for the "overflow" and "full" descriptors. X The former has the bit just ABOVE each bit field set. ANDing with this X set of masks will detect when the thing overflows. The latter is the X former minus one in each bit field -- an almost full field. */ X Xvoid makeof () X /* GLOBAL INPUT: frequency table, letter information, count of masks */ X /* GLOBAL OUTPUT: oflodesc */ X{ X short l; /* letter number */ X short mnum, bnum, bwidth; /* mask #, bit #, field width */ X mask onebit, ovbit; /* bits for single letter, overflow */ X short i; /* usual counter */ X X for (i = 0; i <= usedmasks; i++) /* clean out... */ X oflodesc [i] = 0; /* ...each overflow mask */ X X X for (l = 0; l < 26; l++) /* loop through letters */ X if (freqs [l] != 0) /* any letters in the phrase */ X { X bnum = letbit [l]; /* what's the bit # for this letter? */ X bwidth = letwidth [l]; /* how wide is the field? */ X mnum = letmask [l]; /* and which mask does field go in? */ X X onebit = 1; /* start with a right-aligned 1 */ X onebit <<= bnum; /* ...align it with the field */ X ovbit = onebit << (bwidth-1); /* and find where the overflow bit is */ X X oflodesc [mnum] |= ovbit; /* put the overflow bit in */ X } /* end of handling letter in phrase */ X} /* end of makeof() */ X X X X/* makedesc -- Create the descriptor for a string. If the string contains X too many of any letter, we return zero to say so. */ X Xshort makedesc (str, desc) /* returns zero <=> failure */ X register char *str; /* INPUT: string to analyze */ X register mask desc[]; /* OUTPUT: descriptor for string */ X /* GLOBAL INPUT: frequency table, letter information */ X{ X register short l; /* letter number */ X register char c; /* character from the string */ X short sfreqs [26]; /* string's frequency profile */ X register short i; /* loop counter */ X register mask b; /* a bit, for ORing into the desc */ X X if (*str == '\0') /* null string? */ X return (0); /* no good */ X X for (i = 0; i <= usedmasks; i++) /* go through all used masks... */ X desc[i] = 0; /* ...initializing their descriptors */ X X for (l = 0; l < 26; l++) /* loop through all letters... */ X sfreqs [l] = 0; /* zeroing their frequency */ X X while (c = *str++) /* pick up all characters in str... */ X sfreqs [c - 'a'] ++; /* ...tallying up their count */ X X for (l = 0; l < 26; l++) /* loop through all letters... */ X if (sfreqs [l] != 0) /* did it occur in the string? */ X { X if (sfreqs [l] > freqs[l]) /* did it occur more than in the phrase? */ X return (0); /* yes: fail */ X b = sfreqs [l]; /* start with the count */ X b <<= letbit [l]; /* shift it into the field */ X desc [letmask [l]] += b; /* now add it into the mask */ X } /* end of handling letter in str */ X X return (1); /* we're OK -- say so */ X} /* end of makedesc */ X X/* okword -- See if a string is eligible for use in anagrams. X We return zero if not. */ X Xshort okword (str) /* returns zero <=> failure */ X register char *str; /* INPUT: string to analyze */ X /* GLOBAL INPUT: frequency table */ X{ X register short l; /* letter number */ X register char c; /* character from the string */ X short sfreqs [26]; /* string's frequency profile */ X X if (*str == '\0') /* null string? */ X return (0); /* no good */ X X for (l = 0; l < 26; l++) /* loop through all letters... */ X sfreqs [l] = 0; /* zeroing their frequency */ X X while (c = *str++) /* pick up all characters in str... */ X { X c -= 'a'; X if (++sfreqs [c] > freqs[c]) /* ...tallying up their count */ X return (0); /* ...and checking each one */ X } X X return (1); /* we're OK -- say so */ X} /* end of okword */ X X/* getdicts -- Get and open up at least one dictionary. */ X Xshort getdicts () /* return count of opened dicts */ X /* GLOBAL OUTPUT: dicts[] */ X{ X short count = 0; /* initially none found */ X short done = 0; /* done flag */ X short defaultavail; /* default-file-failed flag */ X char dictname [STRMAX]; /* dictionary file name */ X FILE *testfile; /* used for checking for default file */ X short helptype; X X /* is the default file available? */ X X testfile = fopen (DFTFILE, "r"); X if (testfile == NULL) /* blew it? */ X defaultavail = FALSE; /* yup -- remember it's not there */ X else { /* found it */ X defaultavail = TRUE; /* remember this */ X fclose (testfile); /* and chuck it */ X } /* end of successful find */ X X while (! done) /* loop 'til we're happy */ X { X if (count == 0) /* no files open yet? */ X { /* yes: special greeting */ X printf ("Name of dictionary file"); X helptype = dict1; /* set help state */ X if (defaultavail) X { X printf (" [press RETURN to use '%s']", DFTFILE); X helptype = dict1dft; X } X } X else X { X printf ("Next dictionary name [press RETURN if no more]"); X helptype = dict2; X } X getline ("? ", "", 0, "", "Dictionary name? ", helptype, dictname); /* ask 'em */ X X if (strlen (dictname) == 0) /* just RETURN? */ X { /* handle untalkative input */ X if (count == 0) /* no files yet? */ X { X if (defaultavail == 0) /* no files yet? */ X printf ("Come now, don't be shy.\n"); /* no default available */ X else strcpy (dictname, DFTFILE); /* use default name */ X } X else done = TRUE; /* one or more files is OK */ X } /* end of handling RETURN */ X X if (strlen (dictname) != 0) /* did we read (or plug in) a name? */ X { /* we got a name... */ X testfile = fopen (dictname, "r"); /* ...try to open it */ X if (testfile == NULL) /* failed? */ X printf ("Sorry, can't find the file '%s'. Try again?\n", dictname); X else dicts [count++] = testfile; /* stack this dict; bump count */ X } /* end of processing input name */ X X if (count >= MAXFILES) /* full up? */ X { /* yes: force an exit */ X printf ("\nThat's enough files -- can't handle any more!\n"); X done = TRUE; X } X X } /* end of looping 'til done */ X X return (count); /* say how many dictionaries we got */ X} /* end of getdicts() */ X X/* getwords -- Read in all the usable words from all the dictionaries. X We set the count of usable words, including zero if there are X none. If we run out of memory, we return zero. Either way, we X print a message so the caller doesn't have to. */ X Xshort getwords () /* we return the count of words */ X{ X register short dnum; /* dictionary number */ X register FILE *infile; /* one dictionary's FILE */ X char word [STRMAX]; /* one word from the dictionary */ X char cleanword [STRMAX]; /* cleaned-up copy */ X register long readcount = 0; /* count of words read */ X char lastline [STRMAX]; /* last line read */ X char inpline [STRMAX]; /* raw input line */ X char *inp; /* input line pointer */ X short common; /* count of letters in common */ X X numwords = 0; /* no words yet */ X for (dnum = 0; dnum < numdicts; dnum++) /* loop through all dictionaries */ X { X printf ("Reading dictionary..."); X infile = dicts [dnum]; /* grab this dictionary */ X fseek (infile, 0L, 0); /* reset to start of file */ X while (1) /* EOF is noticed in mid-loop */ X { X if (fgets (inpline, STRMAX, infile) == NULL) /* get a word */ X break; /* if end-of-file, quit */ X common = 0; X inp = inpline; /* point to start of input line */ X while ( (*inp >= '0') && (*inp <= '9') ) /* process digits... */ X common = (common * 10) + (*inp++ - '0'); /* ...accumulate number */ X lastline [common] = '\0'; /* take first N chars of last line */ X strcat (lastline, inp); /* and add the rest */ X X strcpy (word, lastline); /* now get the word */ X cleannl (word); /* ditch the newline */ X strcpy (cleanword, word); /* make a copy... */ X clean (cleanword); /* ...and clean it up */ X readcount++; X if ((readcount % 1000) == 0) X { printf ("."); X fflush (stdout); /* don't let this line buffer up */ X } X X if (okword (cleanword) != 0) /* can it be used in anagrams? */ X { /* yes! */ X if (storeword (word) == 0) /* store it; check for failure */ X return (0); /* say we can't do it */ X } /* end of handling useful word */ X } /* end of loop through one dict */ X printf ("\n"); /* ... left us in mid-line */ X } /* end of loop through dictionaries */ X X if (numwords == 0) /* NOTHING found? */ X printf ("Sorry -- absolutely NO usable words found!\n"); X else printf ("%d usable words found.\n", numwords); X X} /* end of getwords () */ X Xshort storeword (word) X register char *word; X{ X register char *memword; /* allocated word */ X register short len = 1 + strlen (word); /* size we need to store word */ X register short newmaxwords; /* new array size */ X register short size; /* size of new block */ X X if (len > nextwleft) /* no room in this chunk? */ X { X struct wchunk *newchunk; X X newchunk = (struct wchunk *) malloc (sizeof (struct wchunk)); X if (newchunk == NULL) /* blew it? */ X { X printf ("Sorry -- not enough memory for this anagram!\n"); X freewords (); /* discard accumulated words */ X return (0); /* say so */ X } X newchunk -> next = chunkhead; /* make this... */ X chunkhead = newchunk; /* ...the head chunk */ X curchunk = newchunk; /* which (coincidentally) is the current one, too */ X nextwcp = newchunk -> text; /* point to first usable character */ X nextwleft = WORDCHUNK; /* remember available size */ X } X X memword = nextwcp; /* point to first free character */ X nextwcp += len; /* skip to next slot */ X nextwleft -= len; /* and debit available stuff */ X X strcpy (memword, word); /* store the word in new chunk */ X X if ((numwords+1) >= maxwords) /* will this overflow the current list? */ X { X newmaxwords = maxwords + WPTRDELTA; /* jump to next size */ X size = newmaxwords * sizeof (char *); /* find new size */ X X if (wordlist == NULL) X wordlist = (char **) malloc (size); /* first time */ X else wordlist = (char **) realloc (wordlist, size); /* grow the block */ X X if (wordlist == NULL) /* blew it? */ X { /* looks that way */ X printf ("Sorry -- not enough memory for this anagram!\n"); X free (memword); /* chuck word not yet in list */ X freewords (); /* discard accumulated words */ X return (0); /* say to give up */ X } X X maxwords = newmaxwords; /* remember new maximum */ X } /* end of handling list overflow */ X X wordlist [numwords++] = memword; /* stack this word in the list */ X X return (1); /* the sweet smell of success */ X} X Xvoid freewords () X{ X struct wchunk *p; X X for (p = chunkhead; p = p -> next; p != NULL) X free (p); X X nextwcp = NULL; X nextwleft = 0; /* force allocation next time */ X curchunk = NULL; X chunkhead = NULL; X} /* end of freewords() */ X X Xshort mycmp (s1p, s2p) X char **s1p, **s2p; X{ X register char *s1 = *s1p; X register char *s2 = *s2p; X register short i; X X i = strlen (s2) - strlen (s1); /* if S2 is longer, S1 is greater */ X X if (i != 0) X return (i); X return (strcmp (s1, s2)); X} X Xvoid sortwords () X{ X printf ("Sorting words..."); inittimer (); X qsort ((char *) wordlist, numwords, 4, /*mystrcmp*/mycmp); X printf ("\n"); X} X Xvoid nodups () X{ X register short wordnum = 0; X register short move; X X while (wordnum < numwords-1) X { X if (strcmp (wordlist [wordnum], wordlist [wordnum+1]) != 0 ) X wordnum ++; /* different: go to next word */ X else { /* same: have to move down */ X X for (move = wordnum; move < numwords - 1; move++) X wordlist [move] = wordlist [move+1]; X -- numwords; X } X } X} X Xvoid printwords () X{ char response [STRMAX]; X FILE *f; X register short wordnum = 0; X X printf ("What file do you want the word list in [RETURN if none]? "); X gets (response); /* get a line of input */ X if (strlen (response) == 0) /* pressed RETURN? */ X return; /* yes: bag it */ X X f = fopen (response, "a"); /* open, append */ X if (f == NULL) X { printf ("Can't output to that file; sorry!"); X return; X } X X fseek (f, 0L, 2); /* reset to the end */ X while (wordnum < numwords) X { fprintf (f, "%s\r", wordlist [wordnum]); X ++wordnum; X } X X /* makeWrite (f); */ /* make it MacWrite-able */ X fclose (f); X} X Xvoid makeWrite (f) X FILE *f; X{ short refnum; X FInfo info; X Str255 s; X X refnum = f->refnum; X GetFInfo (&s, refnum, &info); X info.fdType = 'TEXT'; X info.fdCreator = 'MACA'; X SetFInfo (&s, refnum, &info); X} X Xshort makemasks () X /* GLOBAL INPUT: numwords, wordlist */ X /* GLOBAL OUTPUT: worddescs[] */ X{ X short i; X short onesize, size; X mask *descp; X char wordcopy [STRMAX]; X X onesize = (usedmasks+1) * sizeof (mask); X size = numwords * onesize; /* compute size of all descriptors */ X X worddescs = (mask *) malloc (size); /* find space for it */ X if (worddescs == NULL) /* blew it? */ X return (0); X X descp = worddescs; /* point to the first descriptor slot */ X for (i = 0; i < numwords; i++) /* loop through every word... */ X { X strcpy (wordcopy, wordlist [i]); /* ...copy the word */ X clean (wordcopy); /* ...clean it up */ X makedesc (wordcopy, descp); /* ...and store each one's descriptor */ X descp += (usedmasks+1); /* ...and bump to next slot */ X } X return (1); /* no memory problems */ X} /* end of makemasks() */ X Xvoid freemasks () X{ X free (worddescs); X} X Xshort doanagrams (curword, curstate, wordCount) /* return 0 to halt search */ X register short curword; /* current word number */ X register mask *curstate; /* descriptor for current state */ X short wordCount; /* words left to stack before we print anagram */ X{ X mask newdesc [MAXMASKS]; /* new descriptor */ X register mask newmask; /* one mask from descriptor */ X register mask *curdesc; /* current word's descriptor */ X register long overflow; /* does this combination overflow? */ X register long bitsleft; /* is this combination full? */ X X curdesc = &worddescs [curword * (usedmasks+1)]; X X wordCount--; /* count the word we're going to stack */ X while (curword < numwords) /* loop through all words after this one */ X { X X#define CASE(MNUM) \ X newmask = curstate [MNUM] - curdesc [MNUM]; /* subtract from anagram */ \ X if (overflow = /* remember if there was oflo... */ \ X (newmask & oflodesc [MNUM])) /* and, if so, bag it */ \ X break; /* note it; break out */ \ X newdesc [MNUM] = newmask; /* it's OK; store it */ \ X bitsleft |= newmask; /* note if done */ X X bitsleft = 0; /* assume complete 'til we see otherwise */ X overflow = 0; /* no overflow 'til we've seen it */ X switch (usedmasks) X { X case 5: CASE(5) X case 4: CASE(4) X case 3: CASE(3) X case 2: CASE(2) X case 1: CASE(1) X case 0: CASE(0) X } X X if (! overflow) X { X *anaptr++ = wordlist [curword]; /* save this word */ X X if ((! bitsleft) /* no bits left? */ X && (wordCount == 0)) /* ...and time to print? */ X { X if (printana () == 0) /* print it; do they want us to stop? */ X return (0); /* yes: stop */ X } X else if (wordCount) /* dive deeper only if caller wants more words */ X { X if (doanagrams (curword, newdesc, wordCount) == 0) X return (0); X } X X --anaptr; /* discard the word from the stack */ X } X X curword++; /* next word number */ X curdesc += (usedmasks+1); /* next word's mask */ X } X X return (1); /* continue the search */ X} /* end of doanagrams() */ X Xstatic char *lastanawords [20]; X Xshort printana () /* return 0 to stop current anagram */ X{ X register char **p; X char response [STRMAX]; /* dummy buffer for answer */ X short keynum; /* keyword number from getline() */ X Boolean caps; X X ++anacount; /* that's one more anagram */ X X if (anafile != stdout) /* not printing to screen? */ X { X if ((anacount % DOTFREQ) == 0) /* every once in a while... */ X { X printf ("."); /* remind them we're here */ X if (exitcheck () == 0) /* time to stop THIS anagram? */ X return (0); /* yes */ X if ((anacount % (DOTFREQ * DOTSPERLINE)) == 0) X { X printf ("anagram #%ld: ", anacount); X for (p = anawords; p < anaptr; p++) X printf ("%s ", *p); X printf ("\n"); X } X } X } X X if (anafile == NULL) return (1); /* no file? no more to do here */ X X if (! paging) /* no way to stop? */ X { X if (exitcheck () == 0) /* time to stop THIS anagram? */ X return (0); /* yes */ X } X else { X if ((anacount % PAGESIZE) == 0) X { X stoptimer (); X keynum = getline (" ...more... ", X "#stop", 0, "", " ...more... ", X helppaused, response); X starttimer (); X if (keynum == 0) /* bag this anagram? */ X return (0); /* yup */ X } X } X X /* Print the damned anagram already: */ X caps = false; X for (p = anawords; p < anaptr; p++) X { if (lastanawords [p-anawords] != *p) /* different word than showed up last time? */ X caps = true; X if (caps) X { char buf [100]; X register char *bp; X strcpy (buf, *p); X bp = buf; X while (*bp) X { if ((*bp >= 'a') && (*bp <= 'z')) X *bp += ('A'-'a'); X bp++; X } X chkerr (fprintf (anafile, "%s ", buf)); X } X else chkerr (fprintf (anafile, "%s ", *p)); X lastanawords [p-anawords] = *p; X } X chkerr (fprintf (anafile, "\n")); X X return (1); X} X Xshort exitcheck () /* return 0 to stop this anagram */ X{ X short c; X short stopped = 0; X short keynum; X char str [STRMAX]; X X#if 0 X while (kbhit ()) X if (getchar () == ' ') X stopped = 1; X#endif X X if (! stopped) return (1); /* continue */ X X stoptimer (); X keynum = getline ( X "\nType STOP for the next anagram, QUIT to leave the program,\nor anything else to continue? ", X "#stop", 0, "", X "Type STOP for the next anagram, QUIT to leave the program,\nor anything else to continue? ", X quithelp, str); X X starttimer (); X if (keynum == 0) /* typed STOP? */ X return (0); /* yes: stop */ X else return (1); /* no: continue */ X} X Xvoid getoutput () X /* GLOBAL OUTPUT: anafile, silent */ X{ X char response [STRMAX]; X short done = 0; X short keywd; X X printf ("Print to the screen, print to a file, or just count anagrams?\n"); X while (! done) X { X keywd = getline ("Type COUNT or a filename [or press RETURN for SCREEN]? ", X "#screen#count", 0, "screen", X "Type COUNT or a filename [or press RETURN for SCREEN]? ", X scf, response); X X if (keywd == 0) X { /* handle SCREEN */ X anafile = stdout; /* output to screen */ X done = TRUE; X } X else if (keywd == 1) /* handle COUNT */ X { X anafile = NULL; /* no output */ X done = TRUE; X } X else done = openoutfile (response); /* see if we can output */ X } /* end of loop 'til done */ X} X Xshort openoutfile (name) X char *name; X{ X short keywd; X char response [STRMAX]; X char *opentype; X X opentype = "w"; /* default open type */ X anafile = fopen (name, "r"); X if (anafile != NULL) /* got it? */ X { X fseek (anafile, 0L, 2); /* reset to the end */ X if (ftell (anafile) != 0L) /* position != 0? (ie, not empty?) */ X { X printf ("'%s' isn't empty. Want to OVERWRITE or ADD to it [press RETURN to ADD]? ", name); X keywd = getline ("", "#overwrite#add", 1, "add", X "Please type OVERWRITE or ADD? ", overadd, response); X if (keywd == 0) X opentype = "w"; /* overwrite */ X else opentype = "a"; /* add */ X } X fclose (anafile); X } X X anafile = fopen (name, opentype); /* try to open it as desired */ X X if (anafile == NULL) /* blew it? */ X { X printf ("Sorry -- can't write to '%s'. Try again?\n", name); X return (0); X } X return (1); /* success */ X} X Xshort getline (prompt, keywords, keyneeded, dft, reprompt, X helpstate, response) X char *prompt; /* INPUT: prompt */ X char *keywords; /* INPUT: keywords, like "#a#b#c" */ X short keyneeded; /* INPUT: insist on a keyword? */ X char *dft; /* INPUT: default response */ X char *reprompt; /* INPUT: repeated prompt */ X short helpstate; /* INPUT: help state */ X char *response; /* OUTPUT: response buffer */ X{ X short done = 0; /* flag to exit loop */ X short keyindex; /* index of word in #string */ X X printf ("%s", prompt); /* prompt 'em */ X while (! done) X { X gets (response); /* get a line of input */ X if (strlen (response) == 0) /* pressed RETURN? */ X strcpy (response, dft); /* yes: supply default */ X X keyindex = keyfind ("#quit#help", response); /* see if it's a standard one */ X if (keyindex >= 0) /* found something? */ X { /* handle QUIT or HELP */ X if (keyindex == 0) /* QUIT? */ X { X printf ("\n\n"); X exit (0); X } X dohelp (helpstate); /* nope: HELP */ X } /* end of standard keywords */ X else { /* not standard */ X keyindex = keyfind (keywords, response); /* look it up */ X X if ( (keyindex >= 0) /* found something... */ X || (! keyneeded) ) /* ...or didn't need it */ X done = TRUE; /* then we're satisfied */ X } /* end of parsing response */ X X if (! done) printf ("%s", reprompt); /* about to loop? be pushy */ X } /* end of loop 'til done */ X X return (keyindex); /* return keyword number or -1 */ X} /* end of getline() */ X Xvoid dohelp (state) X short state; X{ X printf ("\n"); X if (state == anahelp) X { X printf (" Enter a word, name or phrase. This program will print out all\n"); X printf (" the combinations of words which can be made by rearranging the\n"); X printf (" letters in the phrase you type in. Very short phrases won't\n"); X printf (" have many good anagrams, while long phrases may produce too\n"); X printf (" many to sift through.\n"); X } X else if (state == scf) X { X printf (" You can print anagrams on the screen, store them in a file,\n"); X printf (" or just count them without printing them anywhere. To print\n"); X printf (" them on the screen, type SCREEN or just press RETURN. To count\n"); X printf (" them, type COUNT. To send them to a file, type the file's name.\n"); X } X else if (state == overadd) X { X printf (" You can replace the current contents of that document with the\n"); X printf (" anagrams, or you can add them after the old contents. To replace,\N"); X printf (" type OVERWRITE. To add, type ADD.\n"); X } X else if (state == quithelp) X { X printf (" When you press the space bar, it suspends anagram finding\n"); X printf (" in case you want to quit. To leave the program, type QUIT.\n"); X printf (" To do another anagram, type STOP. To resume, type anything else.\n"); X } X else if (state == dict1) X { X printf (" Enter the name of a dictionary file you'd like to use. Usually,\n"); X printf (" '%s' is used, but it doesn't seem to be available.\n", DFTFILE); X printf (" Any text-only file containing one word per line will do.\n"); X } X else if (state == dict1dft) X { X printf (" Enter the name of a dictionary file you'd like to use. Press\n"); X printf (" RETURN to use '%s', the default file.\n", DFTFILE); X } X else if (state == dict2) X { X printf (" Enter the name of another dictionary file, or press RETURN\n"); X printf (" if you don't want to enter any more.\n"); X } X else if (state == helppage) X { X printf (" Normally output to the screen rushes by unless you press the\n"); X printf (" mouse button to freeze it or hit the space bar to suspend it.\n"); X printf (" If you ask for 'paged' output, it'll stop after each screenful.\n"); X } X else if (state == helppaused) X { X printf (" Press RETURN to resume reading anagrams, STOP to do a different\n"); X printf (" anagram, or QUIT to stop.\n"); X } X else printf ("Sorry -- no help available here.\n"); X X if (state != quithelp) X printf (" At any time, you can leave by typing QUIT.\n"); X printf ("\n"); X} X Xshort keyfind (words, oneword) X char *words; X char *oneword; X{ X short cindex; X char wordcopy [STRMAX], lookupword [STRMAX]; X short wordnum; X X strcpy (wordcopy, oneword); X clean (wordcopy); X if (strlen (wordcopy) < 1) return (-1); /* can't find nothing */ X strcpy (lookupword, "#"); X strcat (lookupword, wordcopy); /* construct "#word" */ X X cindex = findstr (words, lookupword); /* look up "#word" in "#a#b... */ X if (cindex == -1) /* not found? */ X return (-1); /* say so */ X X wordnum = 0; /* initially we're at word zero */ X while (cindex-- > 0) /* loop up to "#" in "#word" in str */ X if (*words++ == '#') /* is there a "#"? */ X ++wordnum; /* yes: that's another word */ X X return (wordnum); X} X Xshort findstr (master, sub) X char *master; X char *sub; X{ X short result = 0; X short subsize = strlen (sub); X X while (*master) X { X if (strNequal (master, sub, subsize) == 1) /* match? */ X return (result); /* yup: say where */ X ++result; X ++master; X } X X return (-1); /* no match */ X} X Xshort strNequal (s1, s2, size) X register char *s1, *s2; X register short size; X{ while (size--) X if (*s1++ != *s2++) return 0; /* not equal */ X return 1; /* equal */ X} X Xlong msec () X{ X return (TickCount () * (1000/60)); /* convert from 1/60s to ms */ X} X Xvoid starttimer () X{ X startt = msec (); X} X Xvoid stoptimer () X{ X endt = msec (); X tottime += (endt-startt); X} X Xvoid inittimer () X{ X tottime = 0; X starttimer (); X} X Xvoid printtime () X{ X stoptimer (); X printf ("Computing time: %ld.%03ld seconds. ", X tottime/1000L, (tottime % 1000)); X} X Xvoid chkerr (i) X short i; X{ X if (i == EOF) X { X printf ("Sorry! Error in writing to output file. Perhaps your disk is full?\n"); X exit (0); X } X} END_OF_FILE if test 51223 -ne `wc -c <'ars.c'`; then echo shar: \"'ars.c'\" unpacked with wrong size! fi # end of 'ars.c' fi echo shar: End of shell archive. exit 0 -- # Monty Solomon / PO Box 2486 / Framingham, MA 01701-0405 # monty%roscom@think.com