// This is a translation into C of the Visual Basic code at
// http://groups.yahoo.com/group/wordgame-programmers/message/183
// originally written by someone who would prefer to remain anonymous
// and translated by Graham Toal

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <values.h> /* For MAXLONG */

static int Debug_Probs=FALSE;

static int PutCount;
static int WantedCount;
static int BagCount;
static int RackCounts[256];
static int BagCountError;
static int BagCounts[256];
static int RackTiles;
static int WildCardTiles;
static int ResultRow;
static int PlacementCountsMin[120];
static int PlacementCountsMax[120];
static int Placements;

static double nCr (int n, int r)
{
   static double memo[101][8];
   static int initialised = FALSE;
   double _nCr;
   int i, rr;

   assert(n <= 100); assert(r <= 7);

   if (!initialised) {
     int nn, rr;
     for (rr = 0; rr <= 7; rr++) {
       for (nn = 0; nn <= 100; nn++) {
         memo[nn][rr] = (double) -1.0;
       }
     }
   }

   if (!(memo[n][r] < 0)) return memo[n][r];

   /* I expect storing precomputed values from nCr(0,0) up to nCr(100,7) */
   /* would be faster: a task for later */
   if (r > n)
      return 0.0;
   _nCr = 1.0;
   if ((r + r) <= n) {
      rr = r;
   } else {
      rr = n - r;
   }
   i = 1;
   for (;;) {
     if (i > rr) break;
     _nCr = _nCr * (double)n / (double)r;
     n = n - 1;
     r = r - 1;
     rr = r;
   }
   return (memo[n][r] = _nCr);
}

static double DoPlacements (int Tile)
{
   int n;
   double p;

   p = 0.0;
   /* do from minimum wanted count up to the maximum in the bag */
   n = PlacementCountsMin[Tile];
   while (n <= PlacementCountsMax[Tile]) {
      /* update the count of tiles in the rack */
      PutCount = PutCount + n;
      if (PutCount <= RackTiles) {
         if (Tile < Placements) {
            /* recursively place the next tile(s) */
            p = p + nCr (PlacementCountsMax[Tile], n) * DoPlacements (Tile + 1);
         } else {
            assert (PutCount >= WantedCount);
            /* the last wanted tile and the wildcard tiles */
            p = p + nCr (PlacementCountsMax[Tile], n) * nCr (WildCardTiles,
                                                          RackTiles -
                                                          PutCount);
         }

         PutCount = PutCount - n;
      } else {
         /* Too many tiles now so we exit early */
         PutCount = PutCount - n;
         break;
      }
      n += 1;
   }
   return p;
}

static double Prob (void)
{
   int n;

   assert (WantedCount <= RackTiles);
   PutCount = 0;
   Placements = 0;
   /* for (n = {blank, alltiles} ... could optimise */
   for (n = 0; n < 256; n++) {
      if (RackCounts[n] > 0) {
         Placements = Placements + 1;
         PlacementCountsMin[Placements] = RackCounts[n];
         PlacementCountsMax[Placements] = BagCounts[n];
      }
   }
   assert (Placements <= RackTiles);
   return DoPlacements (1);
}

static void GetCounts (char *Bag, char *Tiles)
{
   int n, x;

   BagCount = strlen (Bag);
   WantedCount = strlen (Tiles);
   WildCardTiles = BagCount;
   for (n = 0; n < 256; n++) {
      BagCounts[n] = 0;
      RackCounts[n] = 0;
   }
   for (n = 0; n < strlen (Bag); n++) {
      x = Bag[n];
      BagCounts[x] = BagCounts[x] + 1;
   }
   for (n = 0; n < strlen (Tiles); n++) {
      x = Tiles[n];
      RackCounts[x] = RackCounts[x] + 1;
      if (RackCounts[x] == 1) {
         /* exit if the wanted tile does not exist in the bag */
         if (BagCounts[x] == 0) {
            BagCountError = TRUE;
            fprintf(stderr, "BagCountError: %c - GetCounts(%s,%s)\n", x, Bag, Tiles);
            assert(BagCounts[x]);
            return;
         }
         /* any tiles we want must be removed from the selection of wildcard
            tiles */
         WildCardTiles = WildCardTiles - BagCounts[x];
      }
   }
}

double RackProbAndCount (char *Tiles, char *Bag, int RackSize, double *Count, double *Total)
{
   double _RackProb, RackProb2, max;

   if (Count != NULL) *Count = 0.0;
   if (Total != NULL) *Total = 0.0;
   BagCountError = FALSE;
   RackTiles = RackSize;
   GetCounts (Bag, Tiles);  /* error if any wanted tile in "Tiles" does not exist in "Bag" */
   if (BagCountError) {
     fprintf(stderr, "*** BagCountError\n");
     return 0.0;
   }
   if (RackTiles > BagCount) {
     fprintf(stderr, "*** RackTiles > BagCount\n");
     return 0.0;
   }
   _RackProb = Prob ();
   RackProb2 = _RackProb / (max = nCr (BagCount, RackTiles));
   if (Debug_Probs) printf("%s %s %d %1.10f (%0.0f ways out of %0.0f)\n", Tiles, Bag, RackSize, RackProb2, _RackProb, max);
   if (Count != NULL) *Count = _RackProb;
   if (Total != NULL) *Total = max;
   return (RackProb2);
}


double RackProb(char *Tiles, char *Bag, int RackSize)
{
  return RackProbAndCount (Tiles, Bag, RackSize, NULL, NULL);
}

double RackCount(char *Tiles, char *Bag, int RackSize) /* error if any wanted tile in "Tiles" does not exist in "Bag" */
{
  double Count;
  (void)RackProbAndCount (Tiles, Bag, RackSize, &Count, NULL);
  return Count;
}