#include <stdio.h>

/* wordprob.c - calculate the probabilities of drawing words at random out
 *              of a bag of letter tiles.
 *
 * Copyright (C) 1993 by John J. Chew, III <jjchew@math.utoronto.ca>.
 * All Rights Reserved.
 *
 * <title>wordprob.c</title>
 *
 * $Header: wordprob.c,v 1.1 93/07/28 09:11:05 jjchew Locked $
 */

#undef DEBUG

#define MAX_BINGO_LENGTH 15

/* configurable */
unsigned char	*gBag = "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmm\
nnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz__";
unsigned char	gBlank = '_';

/* calculated */
int	gBagSize;
int	gBlankCount;
int	gFrequency[256];
double	gChooseSmall[MAX_BINGO_LENGTH+1][MAX_BINGO_LENGTH+1];
double	gChooseBag[MAX_BINGO_LENGTH+1];

/* general external variables */
char	*gProgramName;
enum { none, reciprocal, ppb, numerator } gResultMode = none;

/* functions in this file */
int	main();
void	init();
void	process();

int main(argc, argv) 
  int argc; 
  char **argv; 
  {
  int          ch;
  int          errflg = 0;
  extern int   optind;
  extern char *optarg;

  while ((ch = getopt(argc, argv, "B:bnr")) != EOF) switch(ch) {
    case 'B': 
      gBag = optarg;
      break;
    case 'b': 
      if (gResultMode != ppb && gResultMode != none) errflg++;
      else gResultMode = ppb;
      break;
    case 'n': 
      if (gResultMode != numerator && gResultMode != none) errflg++;
      else gResultMode = numerator;
      break;
    case 'r': 
      if (gResultMode != reciprocal && gResultMode != none) errflg++;
      else gResultMode = reciprocal;
      break;
    case '?':
    default:
      errflg++;
      break;
    }
  if (errflg) {
    fputs("Usage: wordprob [-b|-n|-r] [file...]\n", stderr);
    fputs("  -B bag  set non-standard bag (blank=_)\n", stderr);
    fputs("  -b      display parts per billion\n", stderr);
    fputs("  -n      display numerator only\n", stderr);
    fputs("  -r      display reciprocal of probability\n", stderr);
    exit(2);
    }
  if (gResultMode == none) gResultMode = reciprocal;

  init(&argc, &argv);
  if (optind == argc) process(stdin, "(stdin)");
  else for (; optind < argc; optind++) 
    process(fopen(argv[optind], "r"), argv[optind]); 
  return 0;
  }

void init(argcp, argvp) 
  int *argcp;
  char ***argvp;
  {
  double a, r;
  int    i, j;
  char   *cp;

  /* command-line argument processing */
  gProgramName = **argvp;

  /* bag analysis */
  gBagSize = strlen(gBag);
  for (cp=gBag; *cp; ) gFrequency[*cp++]++;
  gBlankCount = gFrequency[gBlank];
  if (gBlankCount != 2)
    {
    fprintf(stderr, "%s: current code supports only two-blank bags\n", 
      gProgramName);
    exit(1);
    }

  /* combinatorial precalculation */
  gChooseSmall[0][0] = gChooseBag[0] = a = 1.0;
  for (r=i=1; i<=MAX_BINGO_LENGTH; i++, r++) {
    gChooseBag[i] = a *= (gBagSize + 1.0 - r)/r;
    gChooseSmall[i][0] = gChooseSmall[i][i] = 1.0;
    for (j=1; j<MAX_BINGO_LENGTH; j++)
      gChooseSmall[i][j] = gChooseSmall[i-1][j-1]+gChooseSmall[i-1][j];
    }
  }

void process(aFilePointer, aFileName) 
  FILE *aFilePointer; 
  char *aFileName; 
  { 
  int		ch;
  int		charNumber = 0;
  int		frequency;
  int		i, j;
  int		lineNumber = 1;
  unsigned char	blankChars[MAX_BINGO_LENGTH];
  unsigned char	rackChars[MAX_BINGO_LENGTH];
  double	*rackChoices[MAX_BINGO_LENGTH];
  int		rackCounts[MAX_BINGO_LENGTH];
  int		rackLength = 0;
  enum { in, out } state = in;
  char          word[MAX_BINGO_LENGTH+1];

  if (NULL == aFilePointer) {
    fprintf(stderr, "%s: cannot open %s for input.\n", gProgramName, aFileName);
    perror(gProgramName);
    exit(1);
    }

  while (EOF != (ch = getc(aFilePointer))) {
    charNumber++;
    if (state == out) {  
      if (ch == '\n') {
	state = in;
	rackLength = 0;
	charNumber = 0;
	lineNumber++;
	}
      putchar(ch);
      }
    else if (0 == (frequency = gFrequency[(unsigned char)ch]) || ch == gBlank) {
      int    blanksDrawn;
      double thisChoice;
      double totalChoices = 0.0;

      /* no blanks */
      thisChoice = 1.0;
      for (i=0; i<rackLength; i++) thisChoice*=rackChoices[i][rackCounts[i]];
      totalChoices += thisChoice;

      for (blanksDrawn=1; blanksDrawn<gBlankCount; blanksDrawn++) {
	}

#ifdef DEBUG
      putchar('\n');
#endif
      /* one blank */
      for (i=0; i<rackLength; i++) {
	int j;
	rackCounts[i]--;
        thisChoice = gChooseSmall[gBlankCount][1];
        for (j=0;j<rackLength;j++) thisChoice*=rackChoices[j][rackCounts[j]];
        totalChoices += thisChoice;
#ifdef DEBUG
        printf("  with blank for '%c': %.0f\n", rackChars[i], thisChoice);
#endif
	rackCounts[i]++;
	}

      /* two blanks */
      for (i=0; i<rackLength; i++) {
	int j;
	rackCounts[i]--;
	for (j=i; j<rackLength; j++) if (rackCounts[j]) {
	  int k;
	  rackCounts[j]--;
          thisChoice = gChooseSmall[gBlankCount][2];
          for (k=0;k<rackLength;k++) thisChoice*=rackChoices[k][rackCounts[k]];
          totalChoices += thisChoice;
	  rackCounts[j]++;
#ifdef DEBUG
        printf("  with blank for '%c' and '%c': %.0f\n", 
	  rackChars[i], rackChars[j], thisChoice);
#endif
	  }
	rackCounts[i]++;
	}
      charNumber--;
      word[charNumber] = '\0';
      printf("%.0f\t%s",
	gResultMode == ppb 
	  ? (1e9*totalChoices)/gChooseBag[charNumber]
	  : gResultMode == numerator
	    ? totalChoices
	    : gChooseBag[charNumber]/totalChoices,
	  word);
/* printf("\t%.0f\t%.0f",totalChoices,gChooseBag[charNumber]/totalChoices); */

#ifdef DEBUG
      printf("  %f/%f = 1/%f\n", totalChoices, gChooseBag[charNumber],
	gChooseBag[charNumber]/totalChoices);
      for (i=0; i<rackLength; i++)
	{
	int j;
	printf("%d) '%c'*%d: ", i, rackChars[i], rackCounts[i]);
	for (j=0; j<=rackCounts[i]; j++)
	  printf("%4.0f", rackChoices[i][j]);
	putchar('\n');
	}
#endif
      state = out;
      ungetc(ch, aFilePointer);
      }
    else if (charNumber > MAX_BINGO_LENGTH) {
      putchar('\n'); fflush(stdout);
      fprintf(stderr, "%s: word too long in line %d of %s.\n",
	gProgramName, lineNumber, aFileName);
      exit(1);
      }
    else {
      word[charNumber-1] = ch;
      for (i=0; i<rackLength; i++) 
	if (ch == rackChars[i]) { ++rackCounts[i]; break; }
      if (i == rackLength) {
	rackLength++;
	rackChars[i] = ch;
	rackChoices[i] = &gChooseSmall[frequency][0];
	rackCounts[i] = 1;
	}
      }
  }
}