#define bitmask unsigned int #define MAXMASKS 4 #define maskwidth (8*sizeof(bitmask)) #define STACKMAX 32 typedef bitmask bitsig[MAXMASKS+1]; int freqs[27]; bitsig uflosig; bitsig bagsig; bitsig bagsigcopy; int letmask[27]; int letbit[27]; int letwidth[27]; int lastmask; void die (char *ermsg); int fieldwidth(int num) { int tot = 0; while (num != 0) { tot += 1; num = num >> 1; } return(tot+1); } void choosefields(int *freqs) { int letter; int curmask = 0, curbit = 0; int width; for (letter = 0; letter < 27; letter++) if (freqs[letter] != 0) { width = fieldwidth(freqs[letter]); if (curbit+width > maskwidth) { if (++curmask >= MAXMASKS) die("Sorry: Phrase too long to handle.\n"); curbit = 0; } letmask[letter] = curmask; letbit[letter] = curbit; letwidth[letter] = width; curbit += width; /*fprintf(errfile,"Field %c: w=%d\n", letter+'a',width);*/ } if (curmask > lastmask) lastmask = curmask; /* fprintf(errfile,"1:lastmask=%d\n",lastmask);*/ } void makefreqs(char *str, int *freq) /* NEEDS WORK FOR I18N */ { char c; int i; for (i = 0; i < 27 /* 26 english letters + blank */; i++) freq[i] = 0; while ((c = *str++) != '\0') { assert((c == '?') || isalpha(c)); if (c == '?') { // the wild card comes after Z freq[26] += 1; } else { if (('A' <= c) && (c <= 'Z')) c += 32; c -= 'a'; if ((c >= 0) && (c < 26)) freq[c] += 1; } } } void printone(bitmask b) { int i; for (i = 31; i >= 0; --i) { fprintf(errfile, "%c", ((b>>i)&1) + '0'); } } void printmask(char c, bitmask *sig) { fprintf(errfile,"%c", c); printone(sig[0]); if (lastmask > 0) printone(sig[1]); if (lastmask == 2) printone(sig[2]); fprintf(errfile," (%d)\n", lastmask); } void makeonesig(register char *str, bitmask sig[]) { char c; sig[0] = sig[1] = sig[2] = 0; while ((c = *str++) != '\0') { if (c == '?') c = 'z'+1; // the wild card comes after Z else c |= 32; // English set only. Make lower c -= 'a'; // 0..26 (a-z, blank) sig[letmask[c]] += 1<<letbit[c]; } } void makeuf(int freqs[], int letmask[], int letbit[], int letwidth[]) { int l; int bnum, bwidth; for (l = 0; l <= MAXMASKS; l++) uflosig[l] = 0; for (l = 0; l < 27; l++) if (freqs[l] != 0) { bnum = letbit[l]; bwidth = letwidth[l]; uflosig[letmask[l]] += (1L << (bnum+bwidth-1)); } } void die (char *ermsg) { fprintf(errfile, ermsg); exit(0); } // 0: no match // 1: play == rack // 2: all tiles in play are in rack with some left over int COMPATIBLE(bitsig playsig, bitsig racksig) /* Can we make this play using this rack? */ { bitmask *curnode = racksig; bitsig newsig; bitmask newmask; bitmask *cursig = playsig; int bitsleft, matched; char *sp; char errbuff[1024]; #define DOMASK(MASK) { \ newmask = curnode[MASK] - cursig[MASK]; \ if ((newmask & uflosig[MASK])) {matched = FALSE; break;} /* FROM SWITCH */ \ newsig[MASK] = newmask; \ bitsleft = bitsleft | newmask; \ /*fprintf(errfile,"curnode: %08X - cursig: %08X, bitsleft: %08X, newsig%0d: %08X, uflosig: %08X\n",*/ \ /* curnode[MASK], cursig[MASK], bitsleft, MASK, newmask, uflosig[MASK]);*/ \ } bitsleft = 0; matched = TRUE; sp = errbuff; *sp = '\0'; switch (lastmask) { /* DOMASK issues a "break" from the switch if not compatible */ case 2: DOMASK(2) /* 3 calls to DOMASK allows up to 48 different letters */ case 1: DOMASK(1) /* because I think one language has 33 letters */ case 0: DOMASK(0) /* and 2 calls are not enough */ } // fprintf(errfile, "%s", errbuff); if (matched) { if (!bitsleft) { /* exact match. Remove lower-scoring item */ //fprintf(errfile, "Exact (Bingo) match!:\n"); return(1); } else { /* we can make this play and have some tiles left over */ //fprintf(errfile, "Subset match:\n"); return(2); } } else { /* otherwise we could not make this play */ //fprintf(errfile, "No match:\n"); return(0); } }