// 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 */
#define True (0==0)
#define False (0!=0)

static int Debug_Probs=True;

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)
{
   double _nCr;
   int i, rr;

   /* 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 (_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;
            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;

   BagCountError = False;
   RackTiles = RackSize;
   GetCounts (Bag, Tiles);
   if (BagCountError) return 0.0;
   if (RackTiles > BagCount) 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)
{
  double Count;
  (void)RackProbAndCount (Tiles, Bag, RackSize, &Count, NULL);
  return Count;
}

#define FullRack       "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmmnnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??"
#define FullRackMinusA "aaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmmnnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??"
#define HalfRack       "aaaaabcddeeeeeefghiiiiikllmnnnooooprrrsstttuuvwxy?"

int main(int argc, char **argv)
{
double p;

  Debug_Probs = True;
  p = RackCount("a", FullRack, 7);
  p = RackCount("e", FullRack, 7);
  p = RackCount("z", FullRack, 7);
  p = RackCount("aa", FullRack, 7);
  p = RackCount("az", FullRack, 7);
  p = RackCount("eia", FullRack, 7);
  p = RackCount("eia", FullRack, 6);
  p = RackCount("eia", FullRackMinusA, 7);
  p = RackCount("otarine", FullRack, 7);
  p = RackCount("eia", HalfRack, 7);
  p = RackCount("abcdefg", "abcdefgh", 7);
  p = RackCount("a", "abcdefgh", 7);
  p = RackCount("a", "aabcdefg", 7);
  p = RackCount("a", "aabcdefgh", 7);
  p = RackCount("a", "aabcdefghi", 7);
  p = RackCount("aa", "aabcdefg", 7);
  p = RackCount("ab", "aabcdefg", 7);
  p = RackCount("abc", "aabcdefg", 7);
  p = RackCount("abcd", "aabcdefg", 7);
  p = RackCount("abcde", "aabcdefg", 7);
  p = RackCount("abcdef", "aabcdefg", 7);
  p = RackCount("abcdefg", "aabcdefg", 7);
  p = RackCount("b", "aabcdefg", 7);
  p = RackCount("bc", "aabcdefg", 7);
  p = RackCount("bcd", "aabcdefg", 7);
  p = RackCount("bcde", "aabcdefg", 7);
  p = RackCount("bcdef", "aabcdefg", 7);
  p = RackCount("bcdefg", "aabcdefg", 7);
  p = RackCount("aabcdefg", "aabcdefg", 8);
  p = RackCount("abcdefg", "aabcdef", 7);
  p = RackCount("abcdefg", "abcdef", 7);
  p = RackCount("a", "abcdefg", 8);
  p = RackCount("i", "abcdefgh", 7);
  p = RackCount("muzjiks", FullRack, 7);
  p = RackCount("zy??yva", FullRack, 7);
  p = RackCount("sting", FullRack, 7);
  p = RackCount("retina", FullRack, 7);

  Debug_Probs = False;
  fprintf(stdout, "The probability of drawing ...\n");
  p = RackProb("a", FullRack, 7);
  fprintf(stdout,
    "at least 1 'a' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
    p, 1.0/p); 
  p = RackProb("e", FullRack, 7);
  fprintf(stdout,
    "at least 1 'e' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
    p, 1.0/p);
  p = RackProb("z", FullRack, 7);
  fprintf(stdout,
    "the only 'z' when picking 7 from from 100 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("aa", FullRack, 7);
  fprintf(stdout,
    "'aa' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("az", FullRack, 7);
  fprintf(stdout,
    "'az' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("eia", FullRack, 7);
  fprintf(stdout,
    "'eia' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("eia", FullRack, 6);
  fprintf(stdout,
    "'eia' when picking 6 from 100 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("eia", FullRack+1, 7);
  fprintf(stdout,
    "'eia' when picking 7 from 99 tiles = %1.9f (1 in %1.2f) approx\n",
     p, 1.0/p);
  p = RackProb("aeinort", FullRack, 7);
  fprintf(stdout,
    "exactly 'aeinort' when picking 7 from 100 tiles = %1.9f (1 in %1.2f)\n",
    p, 1.0/p);
  p = RackProb("eia", HalfRack, 7);
  fprintf(stdout,
    "'eia' when picking 7 from 50 tiles = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);

  p = RackProb("ab", "abab", 2);
  fprintf(stdout,
    "'ab' when picking 2 from 'abab' = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);
  p = RackProb("ab", "ab", 2);
  fprintf(stdout,
    "'ab' when picking 2 from 'ab' = %1.9f (1 in %1.2f)\n",
     p, 1.0/p);


  exit(0);
}