home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d03xx / d0366.lha / Makewords / Source / Unjumble.c < prev    next >
C/C++ Source or Header  |  1990-08-12  |  10KB  |  366 lines
  1. /* unjumble.c - try to make words from a jumbled string of letters.
  2.  
  3.                                 Ron Charlton
  4.                              9002 Balcor Circle
  5.                              Knoxville, TN 37923
  6.    
  7.                              Phone: (615)694-0800
  8.    
  9.                               PLINK: R*CHARLTON
  10.                            BINTNET: charltr@utkvx1
  11.  
  12.                                  05-Jul-90
  13.  
  14. This program is in the public domain.  It may be used for any purpose.
  15.  
  16. Algorithm:  Generate all of the permutations of the letters in a string
  17. and test each one for its "trigram weight".  (A trigram is a group of three
  18. letters, e.g., AAA, EWE, QQQ.)    Use a table of trigram weights (frequencies)
  19. derived from a 38,500 word dictionary.    Calculate an n-letter string's
  20. trigram weight as the sum of the weights of its (n - 2) trigrams.  A
  21. trigram's weight is the log base 2 of its frequency of occurrence in
  22. the dictionary.
  23.  
  24. Keep a table of the twenty highest weights while avoiding duplicates due to
  25. multiple occurrences of a single letter.  Print out only the non-zero
  26. entries in the table.  This all works because some trigrams (such as "ING")
  27. are more likely than others (such as "QQQ").
  28.  
  29. The trigram data are stored on disk as a nybble_table and a bit_table for
  30. compactness, then converted to an array (nn[][][]) for execution speed.
  31. The string to be unjumbled is adjusted by making 'A' 1, 'B' 2, ... 'Z' 26
  32. so that the characters can be used as indices into nn[][][].
  33. This allows nn[][][] to be as small as possible (leaving '\0' available as
  34. the end-of-string indicator).
  35.  
  36.  
  37. history:
  38. v1.3 - don't include any 'word' with any individual trigram weight of 0
  39. v1.4 - general cleanup (& change to strupr)
  40. v1.5 - added exit() from main() & editorial comments & misc. tweakings
  41. v1.6 - changed to structure for table of words and weights
  42. v1.7 - changed do{}while() to for() in print_table(); READ_NYBBLE(); test_bit
  43. v1.8 - TEST_BIT() as macro; removed unused variables in main()
  44. v1.9 - rearranged main(), changed function names, modified intro(), strlwr()
  45. v1.10  removed strlwr() definition
  46. v1.11  changed temp variable to static in insert()
  47. v1.12  eliminated second strcpy() in permute() (faster!!)
  48. v1.13  allow 8-letter words, add 'nothing found'
  49. v1.14  adjust MAXLEN, restored strlwr() definition, conbined printf's in intro()
  50. */
  51.  
  52. char version[] = "v1.14";
  53.  
  54. #include <stdio.h>
  55. #include <ctype.h>
  56.  
  57. #define CSI 0x9b
  58. #define CLS 0x0c
  59.  
  60. #define FALSE 0
  61. #define TRUE (!FALSE)
  62.  
  63. #define MAPVALUE ('a'-1)        /* 'A' for uppercase, 'a' for lowercase */
  64.  
  65. #define MAXLEN 10        /* max. length of string to unjumble */
  66. #define TABLESIZE 20        /* size of table of guesses */
  67.  
  68. /* read a nybble from a table of nybbles (32-bit longs in table) */
  69. #define READ_NYBBLE( nyb_number ) \
  70. ( (nybble_table [ nyb_number >> 3 ] >> ((nyb_number & 7L) << 2)) & 0xFL )
  71.  
  72. /* test bit n in table of 32-bit ints */
  73. #define TEST_BIT( n ) \
  74.     ( bit_table [ n >> 5 ] & ( 1L << (n & 0x1FL) ) ? 1 : 0 )
  75.  
  76. /* the follow two lines are associated with tables.c */
  77. extern int bit_table_size, nybble_table_size;
  78. extern unsigned long bit_table[], nybble_table[];
  79.  
  80. /* structure array to hold candidate words and their weights */
  81. struct {
  82.     char word [ MAXLEN + 1 ];
  83.     int weight;
  84.        }  table [ TABLESIZE ];
  85.  
  86. unsigned char nn[27][27][27];    /* array of probabilities of trigrams */
  87. int min_weight;         /* used in insert() for minimum weight */
  88. int min_weight_ptr;        /* used in insert() to point at minimum */
  89.  
  90. char *strlwr();
  91.  
  92.  
  93. /*------------------------------------------------------------------------*/
  94.  
  95. main()
  96. {
  97. char buf [ 255+1 ];
  98. int length;
  99.  
  100. intro();
  101.  
  102. get_weights();                 /* read weights into nn[][][] */
  103.  
  104. for (;;)
  105.   {
  106.   init_table();
  107.   printf ( "\tEnter 3 to 8 letters ( <RETURN> to quit ): ");
  108.  
  109.   if ( ! gets ( buf ) )
  110.     break;
  111.  
  112.   length = strlen ( buf );
  113.  
  114.   if ( length == 0 )
  115.     break;
  116.  
  117.   else if ( !all_letters ( buf ) )
  118.     printf ( "\tYou may only use letters (a-z; A-Z).\n\n" );
  119.  
  120.   else if ( length > 8 )
  121.     printf ( "\tToo many letters.\n\n" );
  122.  
  123.   else if ( length < 3 )
  124.     printf ( "\tToo few letters.\n\n" );
  125.  
  126.   else
  127.     {
  128.     /* do the unjumbling */
  129.     strlwr ( buf );
  130.     map ( buf );            /* convert to array indices */
  131.     permute ( buf, 0, length );     /* do all permutations */
  132.     print_table();            /* display the results */
  133.     }
  134.   }
  135.   exit ( 0 );
  136. }
  137.  
  138. /*------------------------------------------------------------------------*/
  139.  
  140. intro()
  141. {
  142. #ifdef MCH_AMIGA
  143. printf ( "%c", CLS );                   /* clear screen */
  144. printf ( "%c0;33;40m", CSI );           /* color 3,0 */
  145. #endif
  146. printf ( "\n\t\t\t      Unjumble %s\n\n"
  147.        "\t\t\t           by\n\n"
  148.        "\t\t\t      Ron Charlton\n"
  149.        "\t\t\t   9002 Balcor Circle\n"
  150.        "\t\t\t   Knoxville, TN 37923\n"
  151.        "\t\t\t    Plink: R*CHARLTON\n"
  152.        "\t\t\t  BITNET: charltr@utkvx1\n"
  153.        "\t\t    Internet: charltr@utkvx1.utk.edu\n\n", version );
  154. #ifdef MCH_AMIGA
  155. printf ( "%c0;31;40m", CSI );           /* color 1,0 */
  156. #endif
  157.  
  158. printf ( "\tUnjumble tries to create words out of a group of letters\n"
  159.      "\tthat you enter.  It will print out up to twenty guesses in\n"
  160.      "\torder with each guess' weight before it.  Three to 8 letters at\n"
  161.      "\ta time are accepted.  Eight letters requires several seconds of \n"
  162.      "\tcalculation.  More letters are harder to unjumble.\n\n" );
  163. }
  164. /*------------------------------------------------------------------------*/
  165.  
  166. /* test for all letters in a string */
  167. all_letters ( str )
  168.   char *str;
  169.   {
  170.   while ( isalpha ( *str++ ) )
  171.       ;
  172.   return ( ! *--str );    /* pointing at '\0' if all alpha */
  173.   }
  174.  
  175. /*------------------------------------------------------------------------*/
  176.  
  177. /* convert letters to array indices (A-->1, B-->2 ... Z-->26) */
  178. map ( str )
  179.   char *str;
  180.   {
  181.   while ( * str )
  182.     * str++ -= MAPVALUE;
  183.   }
  184.  
  185. /*------------------------------------------------------------------------*/
  186.  
  187. /* find sum of weights of trigrams in a string. */
  188. weigh ( str )
  189.   char *str;
  190.   {
  191.   register int weight = 0, len, pos, triweight;
  192.   if ( (len = strlen ( str ) ) >= 3 )
  193.     for ( pos = 0; pos <= len - 3; pos++)
  194.       {
  195.       triweight = nn [ str [pos] ] [ str [pos+1] ] [ str [pos+2] ];
  196.       if ( triweight > 0 )
  197.       weight += triweight;
  198.       else
  199.       {
  200.       /* eliminate those with any trigram of 0 weight */
  201.       weight = 0;
  202.       break;
  203.       }
  204.       }
  205.   return ( weight );
  206.   }
  207.  
  208. /*------------------------------------------------------------------------*/
  209.  
  210. /* find all permutations of a string */
  211. permute ( a, k, n )
  212. char *a;
  213. int k, n;
  214. {
  215. int i;
  216. char b [ MAXLEN ];
  217. static char temp;
  218. if (k == n)
  219.     insert ( a );            /* insert into table if weighty */
  220. else
  221.     {
  222.     strcpy(b, a);
  223.     for (i = k; i < n; i++)
  224.     {
  225.     temp = b [ k ];
  226.     b [ k ] = b [ i ];
  227.     b [ i ] = temp;
  228.     permute ( b, k+1, n );
  229.     }
  230.     }
  231. }
  232.  
  233. /*------------------------------------------------------------------------*/
  234.  
  235. /* convert array indices to alphabetic 1-->A, 2-->B ... 26-->Z */
  236. unmap ( str )
  237.   char *str;
  238.   {
  239.   while ( * str )
  240.     *str++ += MAPVALUE;
  241.   }
  242.  
  243. /*------------------------------------------------------------------------*/
  244.  
  245. /* initialize the guess table to empty */
  246. init_table()
  247.   {
  248.   int i;
  249.   min_weight = 0;
  250.   min_weight_ptr = 0;
  251.   for ( i = 0; i < TABLESIZE; i++)
  252.     {
  253.     table[i].weight = 0;
  254.     table[i].word[0] = '\0';
  255.     }
  256.   }
  257.  
  258. /*------------------------------------------------------------------------*/
  259.  
  260. /* if this is a weighty word, insert it in the table */
  261. insert ( str )
  262.   char *str;
  263.   {
  264.   register int weight, i;
  265.   
  266.   weight = weigh ( str );
  267.   if ( weight > min_weight ) /* does this word weigh more than table min.? */
  268.     {
  269.     for ( i = 0; i < TABLESIZE; i++ ) /* avoid duplicates (BIGgER BIgGER) */
  270.       if ( ! strcmp ( table[i].word, str ) )
  271.     return;           /* it's already in the table */
  272.  
  273.     /* put this one in table in place of old minimum */
  274.     table [ min_weight_ptr ].weight = weight;
  275.     strcpy ( table [ min_weight_ptr ].word, str );
  276.  
  277.     /* search for new minimum in the table */
  278.     min_weight_ptr = 0;
  279.     min_weight = table [ 0 ].weight;
  280.     for ( i = 1; i < TABLESIZE; i++ )
  281.       if ( table [ i ].weight < min_weight )
  282.     {
  283.     min_weight_ptr = i;
  284.     min_weight = table [ i ].weight;
  285.     }
  286.     }
  287.   }
  288.  
  289. /*------------------------------------------------------------------------*/
  290.  
  291. /* print the non-zero table entries in descending order. */
  292. /* this is a bogus, but adequate, sort */
  293. print_table()
  294.   {
  295.   int max_entry, i, first_pass = TRUE;
  296.  
  297.   for(;;)
  298.     {
  299.     max_entry = 0;            /* point at maximum weight */
  300.  
  301.     for ( i = 1; i < TABLESIZE; i++ )
  302.       if ( table [ i ].weight > table [ max_entry ].weight )
  303.     max_entry = i;
  304.  
  305.     if ( first_pass && table [ max_entry ].weight == 0 )
  306.     {
  307.     printf ( "\t\tNothing found.\n" );
  308.     break;
  309.     }
  310.  
  311.     if ( table [ max_entry ].weight )
  312.       {
  313.       unmap ( table [ max_entry ].word );
  314.       printf("\t\t%5d %s\n", table [ max_entry ].weight,
  315.         table [ max_entry ].word );
  316.       table [ max_entry ].weight = 0;    /* 'delete' from table */
  317.       }
  318.     else
  319.       break;
  320.  
  321.     first_pass = FALSE;
  322.     }
  323. }
  324.  
  325. /*------------------------------------------------------------------------*/
  326.  
  327. /* get trigram weights from nybble_table and bit_table into nn[][][] */
  328. get_weights()
  329.   {
  330.   register int i, j, k, m = 0, ptr = 0;
  331.   for ( i = 1; i <= 26; i++ )
  332.     for ( j = 1; j <= 26; j++ )
  333.       for ( k = 1; k <= 26; k++ )
  334.     {
  335.     /* beware of ++x side effects */
  336.     if ( TEST_BIT ( m ) )
  337.       {
  338.       nn [ i ] [ j ] [ k ] = READ_NYBBLE ( ptr );
  339.       ++ptr;
  340.       }
  341.     ++m;
  342.     }
  343.   }
  344.  
  345. /*------------------------------------------------------------------------*/
  346. /*
  347.  * Convert a string to lower case in place and return a pointer
  348.  * to the resulting string.
  349.  */
  350.  
  351. char *
  352. strlwr ( char *str )
  353.     {
  354.     register char *s = str;
  355.     while ( *s )
  356.     {
  357.     if (*s >= 'A' && *s <= 'Z') 
  358.         *s = *s - 'A' + 'a';
  359.     ++s;
  360.     }
  361.  
  362.     return ( str );
  363.     }
  364.  
  365. /*-------------------------- END OF FILE ---------------------------------*/
  366.