// 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); }