home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 2: PC / frozenfish_august_1995.bin / bbs / d03xx / d0366.lha / Makewords / Source / PhoneWord.c < prev    next >
C/C++ Source or Header  |  1990-08-12  |  9KB  |  340 lines
  1. /* PhoneWord.c - try to make words from a phone number.
  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 phone number
  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 its frequency of occurrence in the dictionary.
  22. Keep a table of the twenty highest weights while avoiding duplicates due to
  23. multiple occurrences of a single letter.  Print out only the non-zero
  24. entries in the table.  This all works because some trigrams (such as "ING")
  25. are more likely than others (such as "QQQ").
  26.  
  27. history:
  28. v1.2   converted to be the 'same' as Unjumble.c v1.14
  29.  
  30. */
  31.  
  32. char version[] = "v1.2";
  33.  
  34. #include <stdio.h>
  35. #include <ctype.h>
  36.  
  37. #define FALSE 0
  38. #define TRUE (!FALSE)
  39.  
  40. #ifdef MCH_AMIGA
  41. #define CSI 0x9b
  42. #define CLS 0x0c
  43. #endif
  44.  
  45. #define MAPVALUE ('a'-1)        /* 'A' for uppercase, 'a' for lowercase */
  46.  
  47. #define MAXDIGITS 7
  48. #define MAXLEN MAXDIGITS        /* max. length of string */
  49. #define TABLESIZE 20            /* size of table of guesses */
  50.  
  51. /* read a nybble from a table of nybbles (32-bit longs in table) */
  52. #define READ_NYBBLE( nyb_number ) \
  53. ( (nybble_table [ nyb_number >> 3 ] >> ((nyb_number & 7L) << 2)) & 0xFL )
  54.  
  55. /* test bit n in table of 32-bit ints */
  56. #define TEST_BIT( n ) \
  57.     ( bit_table [ n >> 5 ] & ( 1L << (n & 0x1FL) ) ? 1 : 0 )
  58.  
  59. /* the follow two lines are associated with tables.c */
  60. extern int bit_table_size, nybble_table_size;
  61. extern unsigned long bit_table[], nybble_table[];
  62.  
  63. /* structure array to hold candidate words and their weights */
  64. struct {
  65.     char word [ MAXLEN + 1 ];
  66.     int weight;
  67.        }  table [ TABLESIZE ];
  68.  
  69.  
  70. unsigned char nn[27][27][27];    /* array of probabilities of trigrams */
  71.  
  72. int i [ MAXDIGITS ];
  73. /* here are the letters on the phone dial (none for 0 & 1) */
  74. char letters [][4] = { "@@@", "@@@", "ABC", "DEF", "GHI", "JKL", "MNO",
  75.                "PRS", "TUV", "WXY" };
  76. char Dstr [ 255+1 ];            /* string from user */
  77. char work [ MAXDIGITS+1 ];        /* build string to test here */
  78.  
  79. int min_weight;         /* used in insert() for minimum weight */
  80. int min_weight_ptr;        /* used in insert() to point at minimum */
  81.  
  82. /*------------------------------------------------------------------------*/
  83.  
  84. main()
  85. {
  86. int dig_pos, length, good;
  87.  
  88. intro();
  89.  
  90. get_weights();
  91.  
  92. do
  93.   {
  94.   good = TRUE;
  95.   init_table();
  96.   printf ( "\tEnter 2 to 7 digits (no 1 or 0) <RETURN> to quit): " );
  97.   gets ( Dstr );
  98.   length = strlen ( Dstr );
  99.   if ( length == 0 ) exit ();
  100.   if ( length > MAXDIGITS )
  101.     {
  102.     printf ( "\t\tEnter no more than %d digits.\n\n", MAXDIGITS );
  103.     continue;
  104.     }
  105.     /* check for bad characters ( only 2-9 allowed ) */
  106.   for ( dig_pos = 0; dig_pos < length; dig_pos++ )
  107.     {
  108.     if ( !isdigit ( Dstr [ dig_pos ] ) || Dstr [ dig_pos ] == '1' ||
  109.         Dstr [ dig_pos ] == '0' )
  110.       {
  111.       printf ( "\t\tOnly digits 2-9 allowed.\n\n" );
  112.       good = FALSE;
  113.       break;
  114.       }
  115.     Dstr [ dig_pos ] -= '0';
  116.     }
  117.   if ( good )
  118.     switch ( length )
  119.       {
  120.       case 1:
  121.     printf ( "\t\tThat's too easy.\n\n" );
  122.     break;
  123.       case 2:
  124.     do_two();
  125.     break;
  126.       case 3: 
  127.       case 4:
  128.       case 5:
  129.       case 6:
  130.       case 7:
  131.     generate ( 0, length );        /* generate all of the possibilies */
  132.     print_table();            /* display the results */
  133.     break;
  134.       default:
  135.         break;
  136.       }
  137.   } while ( length > 0 );
  138. }
  139.  
  140. /*------------------------------------------------------------------------*/
  141.  
  142. intro()
  143. {
  144. #ifdef MCH_AMIGA
  145. printf ( "%c", CLS );            /* clear screen */
  146. printf ( "%c0;33;40m", CSI );        /* color 3,0 */
  147. #endif
  148. printf ( "\n\t\t\t      PhoneWord %s\n\n", version );
  149. printf (   "\t\t\t           by\n" );
  150. printf (   "\t\t\t      Ron Charlton\n" );
  151. printf (   "\t\t\t   9002 Balcor Circle\n" );
  152. printf (   "\t\t\t   Knoxville, TN 37923\n" );
  153. printf (   "\t\t\t    Plink: R*CHARLTON\n" );
  154. printf (   "\t\t\t  BITNET: charltr@utkvx1\n\n" );
  155. #ifdef MCH_AMIGA
  156. printf ( "%c0;31;40m", CSI );        /* color 1,0 */
  157. #endif
  158.  
  159. printf ( "\tPhoneWord tries to create words out of telephone numbers\n" );
  160. printf ( "\tthat you enter.  It will print out up to twenty guesses in\n" );
  161. printf ( "\torder with each guess' weight before it.  One and zero\n" );
  162. printf ( "\tare not accepted.  Seven digits requires several seconds'\n");
  163. printf ( "\tcalculation.  If there is no guess, then it is noted.\n\n" );
  164. printf ( "\tIf your number has 1 or 0 in it you can enter the other\n" );
  165. printf ( "\tdigits in several groups.  It is good to try different\n" );
  166. printf ( "\tgroups of digits anyway, for example, if your number is\n" );
  167. printf ( "\t234-5678, then try 234 & 5678; 2345 & 678; 23456 & 78;\n" );
  168. printf ( "\t2345678, etc.\n\n" );
  169. }
  170.  
  171. /*------------------------------------------------------------------------*/
  172.  
  173. do_two()
  174.   /* do simple case of two digits */
  175.   {
  176.   int ii, jj;
  177.   for ( ii = 0; ii < 3; ii++ )
  178.     for ( jj = 0; jj < 3; jj++ )
  179.       printf ( "\t\t%c%c\n", letters [ Dstr[0] ] [ii], letters [ Dstr[1] ] [jj]);
  180.   }
  181.  
  182. /*------------------------------------------------------------------------*/
  183.  
  184. generate ( pos, len )
  185.   /* generate the "words" recursively (creates "len" nested "for" loops) */
  186.   int pos, len;
  187.   {
  188.   int s;
  189.   if ( pos < len )
  190.     for ( i [ pos ] = 0; i [ pos ] < 3; ++i[pos] )
  191.       {
  192.       generate ( pos+1, len );
  193.       }
  194.   else
  195.     {
  196.     /* build string and test it */
  197.     for ( s = 0; s < len; s++ )
  198.       work [ s ] = letters [ Dstr[s] ] [ i[s] ] - '@';
  199.     work [ s ] = '\0';
  200.     insert ( work );           /* insert into table if weighty */
  201.     }
  202.   }
  203.  
  204. /*------------------------------------------------------------------------*/
  205.  
  206. /* find sum of weights of trigrams in a string. */
  207. weigh ( str )
  208.   char *str;
  209.   {
  210.   register int weight = 0, len, pos, triweight;
  211.   if ( (len = strlen ( str ) ) >= 3 )
  212.     for ( pos = 0; pos <= len - 3; pos++)
  213.       {
  214.       triweight = nn [ str [pos] ] [ str [pos+1] ] [ str [pos+2] ];
  215.       if ( triweight > 0 )
  216.       weight += triweight;
  217.       else
  218.       {
  219.       /* eliminate those with any trigram of 0 weight */
  220.       weight = 0;
  221.       break;
  222.       }
  223.       }
  224.   return ( weight );
  225.   }
  226.  
  227. /*------------------------------------------------------------------------*/
  228.  
  229. /* convert array indices to alphabetic 1-->A, 2-->B ... 26-->Z */
  230. unmap ( str )
  231.   char *str;
  232.   {
  233.   while ( * str )
  234.     *str++ += MAPVALUE;
  235.   }
  236.  
  237. /*------------------------------------------------------------------------*/
  238.  
  239. /* initialize the guess table to empty */
  240. init_table()
  241.   {
  242.   int i;
  243.   min_weight = 0;
  244.   min_weight_ptr = 0;
  245.   for ( i = 0; i < TABLESIZE; i++)
  246.     {
  247.     table[i].weight = 0;
  248.     table[i].word[0] = '\0';
  249.     }
  250.   }
  251.  
  252. /*------------------------------------------------------------------------*/
  253.  
  254. /* if this is a weighty word, insert it in the table */
  255. insert ( str )
  256.   char *str;
  257.   {
  258.   register int weight, i;
  259.   
  260.   weight = weigh ( str );
  261.   if ( weight > min_weight ) /* does this word weigh more than table min.? */
  262.     {
  263.     for ( i = 0; i < TABLESIZE; i++ ) /* avoid duplicates (BIGgER BIgGER) */
  264.       if ( ! strcmp ( table[i].word, str ) )
  265.     return;           /* it's already in the table */
  266.  
  267.     /* put this one in table in place of old minimum */
  268.     table [ min_weight_ptr ].weight = weight;
  269.     strcpy ( table [ min_weight_ptr ].word, str );
  270.  
  271.     /* search for new minimum in the table */
  272.     min_weight_ptr = 0;
  273.     min_weight = table [ 0 ].weight;
  274.     for ( i = 1; i < TABLESIZE; i++ )
  275.       if ( table [ i ].weight < min_weight )
  276.     {
  277.     min_weight_ptr = i;
  278.     min_weight = table [ i ].weight;
  279.     }
  280.     }
  281.   }
  282.  
  283. /*------------------------------------------------------------------------*/
  284.  
  285. /* print the non-zero table entries in descending order. */
  286. /* this is a bogus, but adequate, sort */
  287. print_table()
  288.   {
  289.   int max_entry, i, first_pass = TRUE;
  290.  
  291.   for(;;)
  292.     {
  293.     max_entry = 0;            /* point at maximum weight */
  294.  
  295.     for ( i = 1; i < TABLESIZE; i++ )
  296.       if ( table [ i ].weight > table [ max_entry ].weight )
  297.     max_entry = i;
  298.  
  299.     if ( first_pass && table [ max_entry ].weight == 0 )
  300.     {
  301.     printf ( "\t\tNothing found.\n" );
  302.     break;
  303.     }
  304.  
  305.     if ( table [ max_entry ].weight )
  306.       {
  307.       unmap ( table [ max_entry ].word );
  308.       printf("\t\t%5d %s\n", table [ max_entry ].weight,
  309.         table [ max_entry ].word );
  310.       table [ max_entry ].weight = 0;    /* 'delete' from table */
  311.       }
  312.     else
  313.       break;
  314.  
  315.     first_pass = FALSE;
  316.     }
  317. }
  318.  
  319. /*------------------------------------------------------------------------*/
  320.  
  321. /* get trigram weights from nybble_table and bit_table into nn[][][] */
  322. get_weights()
  323.   {
  324.   register int i, j, k, m = 0, ptr = 0;
  325.   for ( i = 1; i <= 26; i++ )
  326.     for ( j = 1; j <= 26; j++ )
  327.       for ( k = 1; k <= 26; k++ )
  328.     {
  329.     /* beware of ++x side effects */
  330.     if ( TEST_BIT ( m ) )
  331.       {
  332.       nn [ i ] [ j ] [ k ] = READ_NYBBLE ( ptr );
  333.       ++ptr;
  334.       }
  335.     ++m;
  336.     }
  337.   }
  338.  
  339. /*-------------------------- END OF FILE---------------------------------*/
  340.