
/* ARS.C--

   A dictionary-driven program which finds all possible anagrams using a
   recursive search.  Words and phrases are represented by compact "bit
   signatures", which can be easily subtracted with underflow detection.

   Written by Mike Morton in LightspeedC, October 1986.
   Demo version for publication (c) 1986 by Michael S. Morton.
   Portions of the executable version (c) 1986 by Think Technologies,
     Inc.

  Functions included:
    STARTUP:
             choosefields -- decide where fields go in a signature
               makeonesig -- make the bit signature for a word
                   makeuf -- compute the "underflow" signature
                 getwords -- read the dictionary and store all usable
                             words
                storeword -- store a usable word
              makeallsigs -- make bit signatures for all usable words
    SEARCH ROUTINES:
             findanagrams -- recursively search from a given node in the
                             tree
            printanagrams -- print an anagram from the recursion stack
    UTILITY ROUTINES:
                    clean -- remove non-alphabetics and map to lowercase
                   usable -- see if a word is usable in anagrams for a
                             phrase
                makefreqs -- find frequency distribution for a string
               fieldwidth -- compute minimum field width for a frequency
                             count
                      die -- print dying words and cash in the chips
*/

#include "stdio.h"                  /* for terminal and file I/O */
#include "storage.h"                /* for doing mallocs, reallocs */
#include "ctype.h"                  /* for isalpha(), isupper(), etc. */

/**** Easily changeable constants: ****/
#define STRMAX    100               /* size of character strings */
#define STACKMAX  20                /* recursion max (max words/anagram)
                                     */
#define SCRLEN    22                /* count of output lines between
                                       pauses */

/** The anagram-equivalent of a word is stored in a "bit signature"**/

/* NOTE: the "switch" in findanagrams() depends on MAXMASKS */
#define bitmask   long              /* a "bitsig" is made of
                                       "bitmasks" */
#define MAXMASKS  3                 /* at most this many masks per
                                       signature */
typedef bitmask bitsig[MAXMASKS];   /* so, a bit signature looks like
                                       this */
#define maskwidth (8*sizeof(bitmask)) /* number of bits per bitmask */

/**** Global information about the phrase being anagrammed: ****/
char phrase [STRMAX];       /* the phrase */
int freqs [26];             /* frequency distribution of phrase */
bitsig phrasesig;           /* bit signature for the phrase */
bitsig uflosig;             /* bit signature to detect underflow */

/**** Each letter in the phrase has a field in the bit signature: ****/
int letmask [26];           /* which mask is each letter's field in? */
int letbit [26];            /* what bit # does each field start at? */
int letwidth[26];           /* how wide is field for each letter? */
int lastmask;               /* highest mask # used (0..MAXMASKS-1) */

/**** Dictionary information: ****/
char **wordlist = NULL;     /* dynamic array of pointers to words */
int maxwords = 0;           /* wordlist has bounds [0..maxwords-1] */
int numwords;               /* usable words are in [0..numwords-1] */
char *textnext = NULL;      /* next character to store a word at */
int textleft = 0;           /* characters left in current text chunk */

/* Since we don't always use all bitmasks in a signature, when we
   allocate bit signatures for the usable words, we may use smaller
   signatures (with as few as 1 bitmask).  Hence this array is really
   a list of shrunken bitsigs, but is ACCESSED as bitmasks. */

bitmask *wordsigs;          /* bitsigs for usables; [0..numwords-1] */

/**** For printing anagrams: ****/
char *anawords [STACKMAX];  /* recursion stack to remember words */
char **anaptr;              /* stack ptr (points to 1st unused slot) */
long anacount = 0;          /* total number of anagrams found */

/**** Main program: ****/
/* Get the phrase, neaten it, find the letter frequency distribution.
   Use the distribution to decide where fields go in the bit signature.
   Calculate the signature for the phrase and the "underflow" signature.
   Search the dictionary for all usable words and make their signatures.
   Set up the recursion stack and start the search. */

main()                      /* anagram generator */
{
  printf ("What's the phrase you'd like to anagram? "); /* prompt 'em */
  gets (phrase);            /* get the phrase */
  clean (phrase);           /* remove junk chars; make it lower case */
  makefreqs (phrase, freqs);/* find the frequency distribution */
  choosefields (freqs);     /* assign fields for letters; check size */
  makeuf (freqs, letmask, letbit, letwidth);  /* compute underflow bit
                                                 sig */
  makeonesig (phrase, phrasesig);   /* make bit signature for phrase */

  getwords();               /* get all words usable for this phrase */
  makeallsigs();            /* make signatures for them all */

  anaptr = anawords;                /* initialize the stack pointer */
  findanagrams (0, phrasesig);      /* find f print all anagrams for
                                       phrase */
  printf ("\n   %ld anagrams found.\n", anacount); /* be informative */
}                                   /* end of main program */

/**** clean -- Map alphabetics to lowercase and discard everything
               else. ****/
clean (s)
  char *s;                  /* UPDATE: string to clean in place */
{
  char *out = s;            /* output pointer */
  char c;                   /* working copy of character */

  while (c = *s++)          /* loop through whole input string */
  {
    if (isupper (c)) c -= ('A' - 'a');
                            /* if uppercase, map to lowercase */
    if (isalpha (c)) *out++ = c;    /* and keep only alphabetics */
  }                         /* end of loop mapping f discarding */
  *out++ = c;               /* store the final null */
}                           /* end of clean() */

/**** makefreqs -- Take a phrase and produce its frequency table. ****/
makefreqs (s, ftable)
  char *s;                          /* INPUT: string to analyze */
  int ftable[];                     /* OUTPUT: frequency distribution */
{
  int i;                            /* loop index */

  for (i = 0; i<26; i++)            /* loop through and initialize... */
    ftable [i] = 0;                 /* ...the frequency array */
  while (*s)                        /* while there's more to the
                                       string... */
    ftable [*s++ - 'a'] ++;         /* ...bump frequency slot; advance
                                          s */
}                                   /* end of makefreqs() */

/**** choosefields -- assign bit positions for each letter in the
                      phrase. ****/
/* For each letter, assign it a field in the bit signature.  To do this,
   find how wide the field is with fieldwidth(), then decide whether
   there's enough room for it in the current mask (kick to the next mask
    if necessary) and allocate room for it.  Then remember all information for
the letter. */

choosefields (freqs)
  int freqs [];                    /* INPUT: phrase's frequency table */
  /* GLOBAL OUTPUT: letmask[], letbit[], letwidth[], lastmask */
{
  int letter;                       /* letter value (0..25) */
  int curmask = 0, curbit = 0;      /* initial mask and bit numbers */
  int width;                        /* fieldwidth of letter's field */

  for (letter = 0; letter < 26; letter++) /* loop through all letters */
    if (freqs[letter] != 0)        /* any occurrences of this letter? */
    {                               /* yes: find where it'll go */
      width = fieldwidth (freqs [letter]); /* how much room does it
                                              need? */

      if (curbit+width > maskwidth) /* too wide to fit in rest of this
                                       mask? */
      {                           /* yes: have to kick into next mask */
        if (++curmask >= MAXMASKS)/* next mask number; is there room? */
          die ("Sorry -- that phrase is too long to handle.\n")
                                  /* nope */
        curbit = 0;               /* start at 1st bit of next mask */
      }                           /* end of kicking into next mask */

      letmask [letter] = curmask;   /* note which mask this letter goes
                                       in */
      letbit [letter] = curbit;     /* ..and bit position in the mask */
      letwidth [letter] = width;    /* ..and the width */
      curbit += width;              /* advance past this bit field */

    }                       /* end of handling char found in phrase */

  lastmask = curmask;       /* remember highest used mask number */
}                           /* end of choosefields() */

/**** fieldwidth -- Find the width of field needed to store a
                    count. ****/
/* Find how wide a bit field we need to store a small integer.  We're
   passed the maximum count we'll ever see for that letter, and find the
   smallest field which can hold that count.  Then we add in 1 more bit
   for the "underflow" bit.  Our output looks like:
          Freq      Width (+ 1 underflow bit)
          1         1 (+ 1)
          2..3      2 (+ 1)
          4..7      3 (+ 1) ...etc. */

int fieldwidth (count)      /* find width of field to hold "count" */
  int count;                /* INPUT: frequency of letter */
{
  int width = 1;            /* result -- start at 1 for underflow */

  while (count != 0)        /* loop 'til all bits discarded */
  {
    width++;                /* counting the bits... */
    count >>= 1;            /* ...and chuck out one more */
  }                         /* end of loop counting bits */
  return (width);           /* that's the answer */
}                           /* end of fieldwidth() */

/**** makeuf -- Make the "underflow" signature. ****/
/* The underflow signature is the only bit signature which doesn't
   correspond to a word or phrase.  Instead, it has the bit just ABOVE
   each letter's count field set.  If too many letters are subtracted
   from a field in a real bit signature, the underflow bit to the left
   of that field will be set, and ANDing the now-bogus signature with
   the "underflow" signature will yield a nonzero result, indicating
   underflow. */

makeuf (freqs, letmask, letbit, letwidth)
  int freqs [];             /* INPUT: the phrase's frequency table */
  int letmask [], letbit [], letwidth[];/* INPUT: mask #, bit #, field
                                           width */
  /* GLOBAL OUTPUT: uflosig */
{
  int l;                            /* letter number */
  int bnum, bwidth;                 /* bit number, field width */

  for (l = 0; l <= MAXMASKS; l++)   /* to start with, clean out... */
    uflosig [l] = 0;                /* ...each bitmask in the underflow
                                       sig */

  for (l = 0; l < 26; l++)  /* loop through all 26 letters */
    if (freqs [l] != 0)     /* did this letter occur in the phrase? */
    {                       /* yes: it has a field */
      bnum = letbit [l];    /* get the starting bit for the field */
      bwidth = letwidth [l];/* and get the field's width */

      /* Note that we must use "1L", not just "1" -- these are
         longwords. */
      uflosig [letmask [l]] +=  /* take letter's mask from the sig... */
        (1L << (bnum+bwidth-1));/* ...and put the underflow bit in */
    }                           /* end of handling letter in phrase */
}                               /* end of makeuf() */

/**** makeonesig -- Create the bit signature for a string. ****/
makeonesig (str, sig)
  register char *str;               /* INPUT: string to analyze */
  register bitmask sig[];           /* OUTPUT: signature for string */
  /* GLOBAL INPUT: letmask[] and letbit[] */
{
  register int l;           /* letter number (and loop counter) */
  int sfreqs [26];          /* frequency distribution for "str" */
  register bitmask fr;      /* one frequency, shifted into position */

  makefreqs (str, sfreqs);  /* create a frequency table for string */

  for (l = 0; l <= lastmask; l++) /* go through all used bitmasks... */
    sig[l] = 0;                   /* ...initializing their signature */

  for (l = 0; l < 26; l++)          /* loop through all letters */
    if (sfreqs [l])                 /* does this letter occur? */
    {                               /* yes: want to add into its mask */
      fr = ((bitmask) sfreqs [l]) << letbit [l]; /* shift freq ->
                                                    position */
      sig [letmask [l]] += fr;      /* and add into the right mask */
    }                       /* end of adding in letter frequency */
}                           /* end of makeonesig() */

/**** usable -- See if a string is usable; return 0 if not. ****/
int usable (str)                    /* returns zero on failure */
  register char *str;               /* INPUT: string to analyze */
  /* GLOBAL INPUT: frequency table */
{
  register int l;                   /* letter number */
  register char c;                  /* character from the string */
  int sfreqs [26];                  /* string's frequency profile */

  if (*str == '\0') return (0);     /* null string is no good */

  /* We could use makefreqs() here, but we'll usually disqualify the
     word before we build its whole frequency table, so this way is
     faster. */
  for (l = 0; l < 26; l++)          /* loop through all letters... */
    sfreqs [l] = 0;                 /* ...zeroing their frequency */

  while (c = *str++)        /* pick up all characters in str... */
  {
    c -= 'a';               /* convert each one from a..z to 0..25 */
    if (++sfreqs [c] > freqs[c])    /* tally up their count */
      return (0);           /* ...and see if there are too many */
  }                         /* end of loop through string's letters */

  return (1);               /* we're OK -- say so */
}                           /* end of usable() */

/**** getwords -- Read in and count all the usable words. ****/
/* The dictionary may be packed: each word is prefixed with an ASCII
   count of the number of letters in common with the previous word.
   Note that if there are no such prefixes (i.e., it's not compressed),
   the routine works fine anyway. */

getwords()
{
  FILE *dictfile;           /* the dictionary file */
  char inpline [STRMAX];    /* raw input line (still compressed) */
  char lastline [STRMAX];   /* last line read (after unpacking) */
  char *inp;                /* input line pointer */
  int common;               /* # of letters in common w/last word */
  char word [STRMAX];       /* word rebuilt from packed dict */
  long wordsread = 0;       /* word count, to give some feedback */

  numwords = 0;                     /* no words yet */
  printf ("Reading dictionary..."); /* explain this unavoidable delay */
  dictfile = fopen ("dictionary", "r"); /* open dictionary;
                                           assume success */
  fseek (dictfile, 0L, 0);  /* reset to start of file */
  while (1)                 /* EOF is noticed in mid-loop */
  {
    if (fgets (inpline, STRMAX, dictfile) == NULL)  /* get a word */
      break;                        /* if end-of-file, quit */
    inpline [strlen(inpline)-1] = '\0'; /* strip off trailing newline */

    common = 0;             /* initially, no letters in common */
    inp = inpline;          /* point to start of input line */
    while (isdigit (*inp))  /* process digits... */
      common = (common * 10) + (*inp++ - '0');
                            /* ...accumulate number */
    lastline [common] = '\0'; /* take first N chars of previous line */
    strcat (lastline, inp);   /* and add the rest to create this word */

    strcpy (word, lastline);  /* remember uncleaned word for next time */
    clean (word);             /* clean up punctuation, etc. */
    if (usable (word) != 0)   /* can it be used in anagrams? */
      storeword (lastline);   /* yes: store the UNcleaned version */
    if ((++wordsread % 1000) == 0) putch ('.');
                              /* whistle while we work */
  }                                 /* end of loop through dict */
  putch ('\n');                     /* finish off the line of dots */

  if (numwords == 0)                /* NOTHING found? */
    die ("Sorry -- absolutely NO usable words found!\n");
  printf ("%d usable words found.\n", numwords);
                                    /* hint at size of output */
}                                   /* end of getwords() */

/**** storeword -- Store a word ****/
/* Because many malloc() routines are slow or space-greedy we batch up
   words and store them in large buffers, allocating buffers
   when needed. */

storeword (word)
  register char *word;              /* word to stash */
{
  register char *memword;           /* allocated word */
  register int len = 1 + strlen (word); /* size we need to store word */
  register int size;                /* size of new chunk */

  /* Decide if the current buffer has enough room for the word. */
  if (len > textleft)             /* no room in current text chunk? */
    if ((textnext = malloc (textleft = 5000))
                                  /* reset size and allocate */
          == NULL)                /* did we fail? */
      die ("Sorry -- not enough memory for this anagram!\n");

  memword = textnext;       /* allocate at first free character */
  textnext += len;          /* next time, alloc after this word... */
  textleft -= len;          /* ...and debit free length in chunk */
  strcpy (memword, word);   /* store the word in the new chunk */

  /* Store the word's pointer in the dynamic array "wordlist". */
  if ((numwords+1) >= maxwords)
                            /* would this overflow the current list? */
  {
    maxwords += 512;        /* jump to next size */
    size = maxwords * sizeof (char *);
                            /* find new array size, in bytes */

    if (wordlist == NULL)   /* no list yet? */
      wordlist = (char **) malloc (size);
                            /* 1st time: allocate the block */
    else wordlist = (char **) realloc (wordlist, size);
                            /* grow the block */

    if (wordlist == NULL)           /* blew it? */
      die ("Sorry -- not enough memory for this anagram!\n");
  }                                 /* end of handling list overflow */

  wordlist [numwords++] = memword;  /* store this word in the list */
}                                   /* end of storeword() */

/**** makeallsigs -- Make signatures for each word we saved
                     earlier. ****/
/* Note that "lastmask" may not be as large as MAXMASKS--in other words,
   we don't always use full-sized signatures.  To save memory, we
   allocate them only as large as needed.  Thus some pointers which
   ought to be declared as *bitsig are declared as *bitmask and
   incremented by (lastmask+1) units instead of a simple "++" . */

makeallsigs()
  /* GLOBAL INPUT: numwords, wordlist[] */
  /* GLOBAL OUTPUT: wordsigs[] */
{
  int i;                            /* one more loop index */
  int size;                         /* size of all bit signatures */
  bitmask *sigp;                    /* pointer into array of bitsigs */
  char wordcopy [STRMAX];           /* working copy of a saved word */

  size = numwords * (lastmask+1) * sizeof (bitmask);
                                    /* size of all sigs */
  wordsigs = (bitmask *) malloc (size);/* allocate space for it */
  if (wordsigs == NULL)             /* blew it? */
    die ("Sorry -- not enough memory for this anagram!\n");

  /* Loop through the words; generate and save each one's signature. */
  sigp = wordsigs;                  /* point to the first signature
                                       slot */
  for (i = 0; i < numwords; i++)    /* loop through every word... */
  {
    strcpy (wordcopy, wordlist [i]);/* ...copy the word */
    clean (wordcopy);               /* ...clean it up */
    makeonesig (wordcopy, sigp); /* ...make and store its signature */
    sigp += (lastmask+1);        /* ...and bump to next word's slot */
  }                              /* end of loop through usable words */
}                                /* end of makeallsigs() */

/**** findanagrams -- Recursively search for complete anagrams. ****/
/* We're passed a node, which may be the complete phrase or the
   phrase with some letters already removed.  We're also given the last
   word used, so we can print each permutation in only one order.

   The main loop tries all words from the current word to the last one.
   Each word is "subtracted" from a copy of the current node.  If the
   result underflows, we skip the word.  Otherwise, we push it on our

   stack.  If the result of the subtraction is exactly an empty
   signature (all zero), then we've generated an anagram and can print
   it.  Otherwise we recurse, passing the selected word as the current
   word, and the new, reduced signature as the current node.

   The code to subtract masks is combined with the checks for underflow
   andzero results in a cascaded "switch" which breaks as soon as it
   sees an underflow.  The cases in the switch are nearly identical, and
   are built with the DOMASK macro.  If none of the cases detect
   overflow, the lastcase falls into processing for a successful
   subtraction. */

#define DOMASK(MASK) {         /* one case of switch               */  \
    newmask = curnode [MASK] - cursig [MASK];/*subtract from anagram*/ \
    if (newmask f uflosig [MASK])/* did the subtraction underflow? */  \
        break;                  /* yes: break switch f do next word */ \
    newsig [MASK] = newmask;     /* it's OK; store it               */ \
    bitsleft |= newmask;       /* note if there are any bits left   */ }

findanagrams (curword, curnode)
  register int curword;       /* current word number (used in loop) */
  register bitmask *curnode;  /* bit signature for current node */
{
  bitsig newsig;              /* the new signature (next node down) */
  register bitmask newmask;   /* a single bitmask from new signature */
  register bitmask *cursig;   /* current word's signature */
  register long bitsleft;   /* flag: nonzero if not all letters used */

  cursig = fwordsigs [curword * (lastmask+1)];
                              /* get signature for word */

  while (curword < numwords)  /* loop through all words after this one*/
  {
    bitsleft = 0;             /* no remaining bits seen yet */
    switch (lastmask)         /* check only used masks in signature */
    {
      case 2: DOMASK(2)       /* handle the 3rd mask, if there is one */
      case 1: DOMASK(1)       /* handle the 2nd mask, if there is one */
      case 0: DOMASK(0)       /* handle the 1st mask, if there is one */

    /* We didn't break, so no underflows occurred.  Print or recurse. */

      *anaptr++ = wordlist [curword];
                              /* stack word for printing/recursing */
   /* Decide whether the anagram is complete or if we must search
      deeper. */
      if (! bitsleft)       /* no bits left in the signature? */
        printanagram();     /* yes: used up all letters!  print it */
      else findanagrams (curword, newsig);
                            /* nope: climb down to subnode */
      --anaptr;             /* discard the word from the stack */
    }                       /* end of switch to subtract and process */

    curword++;              /* advance to next word's number... */
    cursig += (lastmask+1); /* ...and to next word's bit signature */
  }                         /* end of loop through words */

}                           /* end of findanagrams() */

/**** printanagram -- Print an anagram stored on the recursion
                      stack. ****/
printanagram()
{
  register char **wp;       /* roving pointer for climbing stack */
  char response [STRMAX];   /* response for when we pause */

  for (wp = anawords; wp < anaptr; wp++)
                            /* go through the whole stack */
    printf ("%s ", *wp);    /* print each word, separated by blanks */
  printf ("\n");            /* kick to a new line after anagram */

  if ((++anacount % SCRLEN) == 0)/* are we at the end of a screenful? */
  {                              /* yes: time to pause */
    printf ("   Press return to continue; anything else to quit...");
    gets (response);                /* see what they want */
    if (strlen (response) != 0) exit();
                                 /* quit if they typed anything */
  }                              /* end of periodic pause */
}                                /* end of printanagram() */

/**** die -- Print the passed message and call it quits: ****/
die (s)
  char *s;                          /* dying words */
{
  printf ("%s", s);                 /* help out the user... */
  exit();                           /* and skip town */
}                                   /* end of die() */
