#include
#include
/* Calculate Combinations(N, R) without using
factorials; 100% accurate for normal numbers
but suffers some minor rounding errors only
in cases where the more obvious algorithm would
have exceeded integer capacity anyway, or would
have forced the use of floating point (which I like
to avoid if possible).
Yes, I did come up with this myself from
first principles, though I have no doubt it
has been thought of before. It's probably a
standard example in every book of integer
numerical algorithms. I was sort of thinking
of Bresenhams algorithm for drawing lines
in a raster when I invented it.
It does fail silently in the case when the
final answer still exceeds the largest
unsigned long integer. Tough.
*/
/* TESTING BUG */
#define Combs(R, N) XCombs(N, R, __LINE__)
static unsigned long XCombs(int R, int N, int L)
{
unsigned long i = 1L;
int r = R;
if (R > N) {
fprintf(stderr, "Who called Combs(%d, %d) at line %0d ?\n", R, N, L);
exit(1);
}
while (((unsigned long)R > 1) || (r > 0)) {
while (r-- > 0) {
i *= (unsigned long)N--;
/* fprintf(stderr, "* %ld => %lu\n", N+1, i); */
if ((N > 0) && (i >= (0x7fffffffUL / (unsigned long)N))) break; /* no more room */
}
while ((unsigned long)R > 1) {
i /= (unsigned long)R--;
/* fprintf(stderr, "/ %ld => %lu\n", R+1, i); */
if ((N > 0) && (i < (0x7fffffffUL / (unsigned long)N))) break; /* room for another */
}
}
return(i);
}
#ifdef NEVER
/*
The answer is not right. Here is the problem:
>calculate the number of different ways you could form the 3-letter
>combination in question with the letters in the Scrabble set - in the case
>of EIA, it would be 12 x 9 x 9. Then,
>you'd multiply that number by the number of ways that you could put
>together the other four tiles, which is "97 choose 4"
Problem: the other 97 tiles include instances of E, I and A, so you count
most instances twice.
The correct answer is the sum of certain coefficients of terms in a
multivariate polynomial expansion. Specifically,
Expand
(1 + A)**9 x (1 + E)**12 x (1 + I)**9 x (1 + X)**(100 - 12 - 9 - 9)
Then add up the coefficients of any term having a factor of AEI and having
total degree 7. (Do you see why this is so?)
I don't have a routine that computes exactly this function. But I know what
you are driving towards (a one-ply static lookahead that uses complete move
generation instead of simulation). (BTW: Maven contains such a method, but it
is only useful in the pre-endgame.) So I can see why you need it.
I will contribute some related code, which you can modify to your purposes.
The following routine generates all racks that can be made out of a given
group of unseen tiles.
*/
#endif
/* Worker routine. See external interface for explanation of arguments. */
/*
Pascal's Triangle is another name for the set of all C(N,K) numbers.
PascalsTriangle[N][K] == C(N, K).
*/
int PascalsTriangle[100][100];
int Pascal(int N, int R) {
int C;
if ((C = PascalsTriangle[N][R]) < 0) {
PascalsTriangle[N][R] = C = Combs(N, R);
} else {
}
return(C);
}
void userack(char *rack, int weight)
{
fprintf(stderr, "rack: '%s' weight: %d\n", rack, weight);
}
static void enumerate_them(
int drawsize,
const int *UnseenCounts,
char *q,
char *DistinctTiles,
int k,
void (*f)(char *, int)
) {
int i;
if (k > drawsize) return;
if (k == drawsize) {
int weight = 1;
char *p;
char *r;
/* Make a string and back up to the beginning. */
*q = 0;
q -= drawsize;
/* Figure out the weight of this case. */
for (p = q, r = p - 1; *p; p++)
if (*p != *(p+1)) {
weight *= Pascal(UnseenCounts[*p], p - r);
r = p;
}
(*f)(q, weight);
return;
}
if (*DistinctTiles == 0) return;
/* Put down each possible number of this tile, and enumerate. */
i = 0;
do {
enumerate_them(drawsize,
UnseenCounts, q, DistinctTiles+1, k, f);
*q++ = *DistinctTiles;
k++;
} while (i++ < UnseenCounts[*DistinctTiles]);
}
/*
// UnseenCounts is a count of each type of tile. PossibleTiles should be the
// aphabet plus blank, but Maven is language-independent so it needs this arg.
// (*f)() is a function that will receive each rack generated, and Data is a block
// of arbitrary data that is passed into (*f)().
*/
void EnumerateRacks(
int drawsize,
char *PossibleTiles,
char *tilesleft,
void (*f)(char *, int)
) {
int UnseenCounts[256];
/* Enumerate the distinct tiles in unseen_array. */
char DistinctTiles[256], *p, *q;
char word_buffer[32];
int ch;
for (ch = 0; ch < 256; ch++) UnseenCounts[ch] = 0;
for (p = tilesleft; *p != '\0'; p++) UnseenCounts[(int)(*p)&255] += 1;
for (p = PossibleTiles, q = DistinctTiles; *p != '\0'; p++) {
if (UnseenCounts[(int)(*p)&255] != 0) *q++ = *p;
}
*q = 0;
enumerate_them(
drawsize, UnseenCounts, word_buffer, DistinctTiles, 0, f);
}
#ifdef NEVER
/*
One trick you can use: Set the UnseenCounts for AEI to their frequency in the
bag, and the count for a fictitious tile (e.g. '*') to the count of all other
tiles combined. Another: set the worker routine to return if it passes 'A'
without placing at least as many 'A' tiles as you need. Another: Don't call
(*f), but instead return the accumulated weight. That should do it.
Disclaimer: this code is contributed "as is" and I don't support it.
Brian
*/
#endif
/* #define FULLRACK "aaaaaaaaabbccddddeeeeeeeeeeeeffggghhiiiiiiiiijkllllmm\
nnnnnnooooooooppqrrrrrrssssttttttuuuuvvwwxyyz??"
*/
#define FULLRACK "abcdefgh"
int main(int argc, char **argv)
{
int i, j;
for (i = 0; i < 100; i++) {
for (j = 0; j < 100; j++) {
PascalsTriangle[i][j] = -1; /* Undef */
}
}
EnumerateRacks(
7,
"abcdefg",
FULLRACK,
userack);
fprintf(stderr, "There are %ld draws of %d tiles from a rack of %d\n",
Combs(strlen(FULLRACK), 7), 7, strlen(FULLRACK));
fflush(stderr);
return(0);
exit(0);
}