/* PhoneWord.c - try to make words from a phone number.

                                Ron Charlton
                             9002 Balcor Circle
                             Knoxville, TN 37923
   
                             Phone: (615)694-0800
   
                              PLINK: R*CHARLTON
                           BINTNET: charltr@utkvx1

                                 05-Jul-90

This program is in the public domain.  It may be used for any purpose.

Algorithm:  Generate all of the permutations of the letters in a phone number
and test each one for its "trigram weight".  (A trigram is a group of three
letters, e.g., AAA, EWE, QQQ.)  Use a table of trigram weights (frequencies)
derived from a 38,500 word dictionary.  Calculate an n-letter string's
trigram weight as the sum of the weights of its (n - 2) trigrams.  A
trigram's weight is its frequency of occurrence in the dictionary.
Keep a table of the twenty highest weights while avoiding duplicates due to
multiple occurrences of a single letter.  Print out only the non-zero
entries in the table.  This all works because some trigrams (such as "ING")
are more likely than others (such as "QQQ").

history:
v1.2   converted to be the 'same' as Unjumble.c v1.14

*/

char version[] = "v1.2";

#include <stdio.h>
#include <ctype.h>

#define FALSE 0
#define TRUE (!FALSE)

#ifdef MCH_AMIGA
#define CSI 0x9b
#define CLS 0x0c
#endif

#define MAPVALUE ('a'-1)        /* 'A' for uppercase, 'a' for lowercase */

#define MAXDIGITS 7
#define MAXLEN MAXDIGITS		/* max. length of string */
#define TABLESIZE 20			/* size of table of guesses */

/* read a nybble from a table of nybbles (32-bit longs in table) */
#define READ_NYBBLE( nyb_number ) \
( (nybble_table [ nyb_number >> 3 ] >> ((nyb_number & 7L) << 2)) & 0xFL )

/* test bit n in table of 32-bit ints */
#define TEST_BIT( n ) \
	( bit_table [ n >> 5 ] & ( 1L << (n & 0x1FL) ) ? 1 : 0 )

/* the follow two lines are associated with tables.c */
extern int bit_table_size, nybble_table_size;
extern unsigned long bit_table[], nybble_table[];

/* structure array to hold candidate words and their weights */
struct {
    char word [ MAXLEN + 1 ];
    int weight;
       }  table [ TABLESIZE ];


unsigned char nn[27][27][27];	/* array of probabilities of trigrams */

int i [ MAXDIGITS ];
/* here are the letters on the phone dial (none for 0 & 1) */
char letters [][4] = { "@@@", "@@@", "ABC", "DEF", "GHI", "JKL", "MNO",
		       "PRS", "TUV", "WXY" };
char Dstr [ 255+1 ];			/* string from user */
char work [ MAXDIGITS+1 ];		/* build string to test here */

int min_weight; 		/* used in insert() for minimum weight */
int min_weight_ptr;		/* used in insert() to point at minimum */

/*------------------------------------------------------------------------*/

main()
{
int dig_pos, length, good;

intro();

get_weights();

do
  {
  good = TRUE;
  init_table();
  printf ( "\tEnter 2 to 7 digits (no 1 or 0) <RETURN> to quit): " );
  gets ( Dstr );
  length = strlen ( Dstr );
  if ( length == 0 ) exit ();
  if ( length > MAXDIGITS )
    {
    printf ( "\t\tEnter no more than %d digits.\n\n", MAXDIGITS );
    continue;
    }
    /* check for bad characters ( only 2-9 allowed ) */
  for ( dig_pos = 0; dig_pos < length; dig_pos++ )
    {
    if ( !isdigit ( Dstr [ dig_pos ] ) || Dstr [ dig_pos ] == '1' ||
		Dstr [ dig_pos ] == '0' )
      {
      printf ( "\t\tOnly digits 2-9 allowed.\n\n" );
      good = FALSE;
      break;
      }
    Dstr [ dig_pos ] -= '0';
    }
  if ( good )
    switch ( length )
      {
      case 1:
	printf ( "\t\tThat's too easy.\n\n" );
	break;
      case 2:
	do_two();
	break;
      case 3: 
      case 4:
      case 5:
      case 6:
      case 7:
	generate ( 0, length );		/* generate all of the possibilies */
	print_table();			/* display the results */
	break;
      default:
        break;
      }
  } while ( length > 0 );
}

/*------------------------------------------------------------------------*/

intro()
{
#ifdef MCH_AMIGA
printf ( "%c", CLS );			/* clear screen */
printf ( "%c0;33;40m", CSI );		/* color 3,0 */
#endif
printf ( "\n\t\t\t      PhoneWord %s\n\n", version );
printf (   "\t\t\t           by\n" );
printf (   "\t\t\t      Ron Charlton\n" );
printf (   "\t\t\t   9002 Balcor Circle\n" );
printf (   "\t\t\t   Knoxville, TN 37923\n" );
printf (   "\t\t\t    Plink: R*CHARLTON\n" );
printf (   "\t\t\t  BITNET: charltr@utkvx1\n\n" );
#ifdef MCH_AMIGA
printf ( "%c0;31;40m", CSI );		/* color 1,0 */
#endif

printf ( "\tPhoneWord tries to create words out of telephone numbers\n" );
printf ( "\tthat you enter.  It will print out up to twenty guesses in\n" );
printf ( "\torder with each guess' weight before it.  One and zero\n" );
printf ( "\tare not accepted.  Seven digits requires several seconds'\n");
printf ( "\tcalculation.  If there is no guess, then it is noted.\n\n" );
printf ( "\tIf your number has 1 or 0 in it you can enter the other\n" );
printf ( "\tdigits in several groups.  It is good to try different\n" );
printf ( "\tgroups of digits anyway, for example, if your number is\n" );
printf ( "\t234-5678, then try 234 & 5678; 2345 & 678; 23456 & 78;\n" );
printf ( "\t2345678, etc.\n\n" );
}

/*------------------------------------------------------------------------*/

do_two()
  /* do simple case of two digits */
  {
  int ii, jj;
  for ( ii = 0; ii < 3; ii++ )
    for ( jj = 0; jj < 3; jj++ )
      printf ( "\t\t%c%c\n", letters [ Dstr[0] ] [ii], letters [ Dstr[1] ] [jj]);
  }

/*------------------------------------------------------------------------*/
 
generate ( pos, len )
  /* generate the "words" recursively (creates "len" nested "for" loops) */
  int pos, len;
  {
  int s;
  if ( pos < len )
    for ( i [ pos ] = 0; i [ pos ] < 3; ++i[pos] )
      {
      generate ( pos+1, len );
      }
  else
    {
    /* build string and test it */
    for ( s = 0; s < len; s++ )
      work [ s ] = letters [ Dstr[s] ] [ i[s] ] - '@';
    work [ s ] = '\0';
    insert ( work );		   /* insert into table if weighty */
    }
  }

/*------------------------------------------------------------------------*/

/* find sum of weights of trigrams in a string. */
weigh ( str )
  char *str;
  {
  register int weight = 0, len, pos, triweight;
  if ( (len = strlen ( str ) ) >= 3 )
    for ( pos = 0; pos <= len - 3; pos++)
      {
      triweight = nn [ str [pos] ] [ str [pos+1] ] [ str [pos+2] ];
      if ( triweight > 0 )
	  weight += triweight;
      else
	  {
	  /* eliminate those with any trigram of 0 weight */
	  weight = 0;
	  break;
	  }
      }
  return ( weight );
  }

/*------------------------------------------------------------------------*/

/* convert array indices to alphabetic 1-->A, 2-->B ... 26-->Z */
unmap ( str )
  char *str;
  {
  while ( * str )
    *str++ += MAPVALUE;
  }

/*------------------------------------------------------------------------*/

/* initialize the guess table to empty */
init_table()
  {
  int i;
  min_weight = 0;
  min_weight_ptr = 0;
  for ( i = 0; i < TABLESIZE; i++)
    {
    table[i].weight = 0;
    table[i].word[0] = '\0';
    }
  }

/*------------------------------------------------------------------------*/

/* if this is a weighty word, insert it in the table */
insert ( str )
  char *str;
  {
  register int weight, i;
  
  weight = weigh ( str );
  if ( weight > min_weight ) /* does this word weigh more than table min.? */
    {
    for ( i = 0; i < TABLESIZE; i++ ) /* avoid duplicates (BIGgER BIgGER) */
      if ( ! strcmp ( table[i].word, str ) )
	return; 		  /* it's already in the table */

    /* put this one in table in place of old minimum */
    table [ min_weight_ptr ].weight = weight;
    strcpy ( table [ min_weight_ptr ].word, str );

    /* search for new minimum in the table */
    min_weight_ptr = 0;
    min_weight = table [ 0 ].weight;
    for ( i = 1; i < TABLESIZE; i++ )
      if ( table [ i ].weight < min_weight )
	{
	min_weight_ptr = i;
	min_weight = table [ i ].weight;
	}
    }
  }

/*------------------------------------------------------------------------*/

/* print the non-zero table entries in descending order. */
/* this is a bogus, but adequate, sort */
print_table()
  {
  int max_entry, i, first_pass = TRUE;

  for(;;)
    {
    max_entry = 0;			/* point at maximum weight */

    for ( i = 1; i < TABLESIZE; i++ )
      if ( table [ i ].weight > table [ max_entry ].weight )
	max_entry = i;

    if ( first_pass && table [ max_entry ].weight == 0 )
	{
	printf ( "\t\tNothing found.\n" );
	break;
	}

    if ( table [ max_entry ].weight )
      {
      unmap ( table [ max_entry ].word );
      printf("\t\t%5d %s\n", table [ max_entry ].weight,
		table [ max_entry ].word );
      table [ max_entry ].weight = 0;	/* 'delete' from table */
      }
    else
      break;

    first_pass = FALSE;
    }
}

/*------------------------------------------------------------------------*/

/* get trigram weights from nybble_table and bit_table into nn[][][] */
get_weights()
  {
  register int i, j, k, m = 0, ptr = 0;
  for ( i = 1; i <= 26; i++ )
    for ( j = 1; j <= 26; j++ )
      for ( k = 1; k <= 26; k++ )
	{
	/* beware of ++x side effects */
	if ( TEST_BIT ( m ) )
	  {
	  nn [ i ] [ j ] [ k ] = READ_NYBBLE ( ptr );
	  ++ptr;
	  }
	++m;
	}
  }

/*-------------------------- END OF FILE---------------------------------*/