home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1693 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  6.5 KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: ars magna
  4. Message-ID: <910@tharr.UUCP>
  5. Date: 21 Aug 90 08:22:43 GMT
  6.  
  7. /* Hacked a long time ago from Byte article; sorry I've lost the reference
  8.    to the original author.  This isn't code for reading; this is code
  9.    for laying down and avoiding... ;-)
  10.     This is for the person who requested it recently; I'm afraid his
  11.    article has dropped off here, so I can't mail it.  However it's a
  12.    traditional 'quick hack' so I won't put an 'Archive-name:' header
  13.    in.  If some site *really* wants it archived, why not tidy it up
  14.    and repost it!
  15.  */
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <stdlib.h>
  20. #include <string.h>
  21.  
  22. #define maxtext 250000
  23. #define maxwords 30000
  24. #define NULL 0
  25. #define bitmask unsigned int
  26. #define MAXMASKS 3
  27. #define maskwidth (8*sizeof(bitmask))
  28. #define STACKMAX 32
  29.  
  30. typedef bitmask bitsig[MAXMASKS+1];
  31. int     freqs[26];
  32. bitsig  uflosig;
  33. int     letmask[26];
  34. int     letbit[26];
  35. int     letwidth[26];
  36. int     lastmask;
  37. int     numwords;
  38. char    *textnext;
  39. bitmask *wordsigs;
  40. char    *anawords[STACKMAX];
  41. char    **anaptr;
  42. int     anacount=0;
  43. int     targetwords;
  44.  
  45. void die (char *ermsg);
  46. void printanagram(char *target, int expected);
  47.  
  48. int fieldwidth(num)
  49.   int num;
  50. {
  51.   int tot = 0;
  52.   while (num != 0) {
  53.     tot += 1;
  54.     num = num >> 1;
  55.   }
  56.   return(tot+1);
  57. }
  58.  
  59. void choosefields(freqs)
  60.   int freqs[];
  61. {
  62.   int letter;
  63.   int curmask = 0, curbit = 0;
  64.   int width;
  65.  
  66.   for (letter = 0; letter < 26; letter++)
  67.     if (freqs[letter] != 0) {
  68.       width = fieldwidth(freqs[letter]);
  69.       if (curbit+width > maskwidth) {
  70.         if (++curmask >= MAXMASKS) die("Sorry: Phrase too long to handle.\n");
  71.         curbit = 0;
  72.       }
  73.       letmask[letter] = curmask;
  74.       letbit[letter] = curbit;
  75.       letwidth[letter] = width;
  76.       curbit += width;
  77.     }
  78.   if (curmask > lastmask) lastmask = curmask;
  79. }
  80.  
  81. void makefreqs(str, freq)
  82.   char *str;
  83.   int freq[];
  84. {
  85.   char c;
  86.   int i;
  87.   for (i = 0; i < 26; i++) freq[i] = 0;
  88.   while ((c = *str++) != '\0') {
  89.     if (('A' <= c) && (c <= 'Z')) c += 32;
  90.     c -= 'a';
  91.     if ((c >= 0) && (c < 26)) freq[c] += 1;
  92.   }
  93. }
  94.  
  95. void makeonesig(str, sig)
  96.   register char *str;
  97.   bitmask sig[];
  98. {
  99.   register int l;
  100.   int sfreqs[26];
  101.   register bitmask fr;
  102.  
  103.   makefreqs(str, sfreqs);
  104.  
  105.   for (l = 0; l <= lastmask; l++) sig[l] = 0;
  106.  
  107.   for (l = 0; l < 26; l++) {
  108.       if (sfreqs[l]) {
  109.         fr = ((bitmask) sfreqs[l]) << letbit[l];
  110.         sig[letmask[l]] += fr;
  111.       }
  112.    }
  113. }
  114.  
  115. void makeuf(freqs, letmask, letbit, letwidth)
  116.   int freqs[];
  117.   int letmask[], letbit[], letwidth[];
  118. {
  119.   int l;
  120.   int bnum, bwidth;
  121.  
  122.   for (l = 0; l <= MAXMASKS; l++) uflosig[l] = 0;
  123.  
  124.   for (l = 0; l < 26; l++)
  125.     if (freqs[l] != 0) {
  126.       bnum = letbit[l];
  127.       bwidth = letwidth[l];
  128.       uflosig[letmask[l]] += (1 << (bnum+bwidth-1));
  129.     }
  130. }
  131.  
  132. #define DOMASK(MASK) { \
  133.   newmask = curnode[MASK] - cursig[MASK]; \
  134.   if ((newmask & uflosig[MASK])) break; \
  135.   newsig[MASK] = newmask; \
  136.   bitsleft = bitsleft | newmask; \
  137. }
  138.  
  139.  
  140. void findanagrams(curword, curnode, wordlist, target)
  141.   register int curword;
  142.   register bitmask *curnode;
  143.   char *wordlist[];
  144.   char *target;
  145. {
  146.   bitsig newsig;
  147.   register bitmask newmask;
  148.   register bitmask *cursig;
  149.   register int bitsleft;
  150.  
  151.   cursig = &wordsigs[curword * (lastmask+1)];
  152.  
  153.   while (curword < numwords) {
  154.     bitsleft = 0;
  155.     if (lastmask > 2) {fprintf(stderr,"BUG 1\n");exit(0);}
  156.     if (lastmask < 0) {fprintf(stderr,"BUG 2\n");exit(0);}
  157.     switch (lastmask) {
  158.  
  159.     case 2: DOMASK(2)
  160.     case 1: DOMASK(1)
  161.     case 0: DOMASK(0)
  162.  
  163.       *anaptr++ = wordlist[curword];
  164.       if (bitsleft == 0) {
  165.         printanagram(target,targetwords);
  166.       } else {
  167.         findanagrams(curword, newsig, wordlist, target);
  168.       }
  169.       --anaptr;
  170.     }
  171.     curword++;
  172.     cursig += (lastmask+1);
  173.   }
  174. }
  175.  
  176. void printanagram(target, expected) char *target; int expected;
  177. {
  178.   int wc;
  179.   char **word;
  180.  
  181.   wc = 0;
  182.   for (word = &anawords[0]; word != anaptr; word++) {
  183.     wc ++;
  184.   }
  185. /*  if (wc == expected) {*/
  186.     wc = 0;
  187.     fprintf(stderr, "%s is an anagram of ", target);
  188.     for (word = &anawords[0]; word != anaptr; word++) {
  189.       printf("%s", *word); wc++;
  190.       /*if ((expected > 1) && (wc != expected))*/ fprintf(stderr, " ");
  191.     }
  192.     printf("\n");
  193. /*  }*/
  194. }
  195.  
  196. void die (ermsg)
  197.   char *ermsg;
  198. {
  199.   printf(ermsg);
  200.   exit(0);
  201. }
  202.  
  203. int getline(s, lim)
  204. char s[];
  205. int lim;
  206. {
  207.   int c, i;
  208.  
  209.   fprintf(stderr, "Word: ");
  210.   i = 0;
  211.   for (;;) {
  212.     if (--lim <= 0) break;
  213.     c=fgetc(stdin);
  214.     if (c == EOF) break;
  215.     c &= 255;
  216.     if (c == 10) break;
  217.     if (c == 13) break;
  218.     s[i++] = c;
  219.   }
  220.   s[i] = '\0';
  221.   return(i);
  222. }
  223.  
  224. int main (int argc, char **argv)
  225. {
  226.   int c;
  227.   int i, len, compatible;
  228.   FILE *DictFile;
  229.   char inittarget[64];
  230.   char *target;
  231.   char *textbuffer;
  232.   char **wordlist;
  233.   int wfreqs[26];
  234.  
  235.   if (argc != 2) {
  236.     fprintf(stderr, "syntax: magna wordlist\n");
  237.     exit(0);
  238.   }
  239.  
  240.   textbuffer = (char *)malloc(maxtext);
  241.   wordlist = (char **)malloc(maxwords*sizeof(char *));
  242.   if ((textbuffer == NULL) || (wordlist == NULL)) {
  243.     fprintf(stderr, "Not enough store\n");exit(0);
  244.   }
  245.  
  246.   DictFile = fopen(argv[1], "r");
  247.   if (DictFile == NULL) {
  248.     fprintf(stderr, "Sorry - can\'t open word list \'%s\'\n", argv[1]);
  249.     exit(0);
  250.   } 
  251.   target = &inittarget[0];
  252.   numwords = 0;
  253.   anaptr = &anawords[0];
  254.   textnext = &textbuffer[0];
  255.  
  256.  
  257.   len = getline(target, 64);
  258.   target = strcpy(textnext, target); 
  259.   textnext += len+1;
  260.   textnext = (char *) ((((int) textnext)+3) & (~3));
  261.   makefreqs(target, freqs);
  262.  
  263.   while ((c = fgetc(DictFile)) != EOF) {
  264.     char *backtrack = textnext;
  265.     compatible = 0;
  266.     if ((c < 0) || (c > 128)) compatible = 1;
  267.     wordlist[numwords] = textnext;
  268.     *textnext++ = c;
  269.     while ((c = fgetc(DictFile)) != EOF && c != '\n') {
  270.       if ((c < 0) || (c > 128)) compatible = 1;
  271.       *textnext++ = c;
  272.     }
  273.     *textnext++ = '\0';
  274.     /* If strlen(wordlist[numwords]) > strlen[target]) skip this... */
  275.       makefreqs(wordlist[numwords], wfreqs);
  276.       for (i= 0; i < 26; i++) {
  277.         if (wfreqs[i] > freqs[i]) {
  278.           compatible = 1; break;
  279.         }
  280.       }
  281.       if (compatible==0) {
  282.         fprintf(stderr,"Using %s\n", wordlist[numwords++]);
  283.       } else textnext = backtrack;
  284.   }
  285.   choosefields(freqs);
  286.  
  287.   textnext = (char *)((((int)textnext)+3) & (~3));
  288.   wordsigs = (bitmask *) &textnext[0];
  289.  
  290.  
  291.   makeonesig(target, &wordsigs[numwords*(lastmask+1)]);
  292.   makeuf(freqs, letmask, letbit, letwidth);
  293.  
  294.  
  295.   for (i = 0; i < numwords; i++) {
  296.     makeonesig(wordlist[i], &wordsigs[i*(lastmask+1)]);
  297.   }
  298.  
  299.  
  300.   findanagrams(0, &wordsigs[numwords*(lastmask+1)], wordlist, target);
  301.   return(0);
  302. }
  303.