#include <stdio.h> /*#define register*/ //#define int long #define maxtext 2200000 #define maxwords 200000 #define bitmask unsigned int #define MAXMASKS 4 #define maskwidth (8*sizeof(bitmask)) #define STACKMAX 32 typedef bitmask bitsig[MAXMASKS+1]; int freqs[26]; bitsig uflosig; bitsig bagsig; int letmask[26]; int letbit[26]; int letwidth[26]; int lastmask; int numwords; char *textnext; bitmask *wordsigs; char *anawords[STACKMAX]; char **anaptr; int anacount=0; int targetwords=2; 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 < 26; 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(stderr,"Field %c: w=%d\n", letter+'a',width);*/ } if (curmask > lastmask) lastmask = curmask; /* fprintf(stderr,"1:lastmask=%d\n",lastmask);*/ } void makefreqs(char *str, int *freq) { char c; int i; for (i = 0; i < 26; i++) freq[i] = 0; /* printf("makefreqs: %s\n", str); */ while ((c = *str++) != '\0') { 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(stderr, "%c", ((b>>i)&1) + '0'); } } void printmask(char c, bitmask *sig) { return; fprintf(stderr,"%c", c); printone(sig[0]); if (lastmask > 0) printone(sig[1]); if (lastmask == 2) printone(sig[2]); fprintf(stderr," (%d)\n", lastmask); } void makeonesig(register char *str, bitmask sig[]) { register int l; int sfreqs[26]; register bitmask fr; makefreqs(str, sfreqs); /* printf("Makeonesig: %s - lastmask = %d, &sig[0] = %08X\n", str, lastmask, &sig[0]); */ for (l = 0; l <= lastmask; l++) sig[l] = 0; /* printf("Makeonesig #2: %s\n", str); */ for (l = 0; l < 26; l++) { /* printf("Makeonesig #3: %s\n", str); */ if (sfreqs[l]) { fr = ((bitmask) sfreqs[l]) << letbit[l]; /* printf("Makeonesig #4: %s\n", str); */ sig[letmask[l]] += fr; /* printf("Makeonesig #5: %s\n", str); */ } } /* fprintf(stderr,"%s:\n", str);*/ printmask('?',sig); } 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 < 26; l++) if (freqs[l] != 0) { bnum = letbit[l]; bwidth = letwidth[l]; uflosig[letmask[l]] += (1L << (bnum+bwidth-1)); } } #define DOMASK(MASK) { \ /*fprintf(stderr,"node%d: %08X, sig: %08X\n", MASK, curnode[MASK], cursig[MASK]);*/ \ newmask = curnode[MASK] - cursig[MASK]; \ if ((newmask & uflosig[MASK])) break; \ newsig[MASK] = newmask; \ bitsleft = bitsleft | newmask; \ /*fprintf(stderr,"bitsleft: %08X, newsig%d: %08X\n", bitsleft, MASK, newmask);*/ \ } void die (char *ermsg) { fprintf(stderr, ermsg); exit(0); } typedef struct playfm { char place[8]; char pos[4]; char dirn; int score; int freq; int cumfreq; bitsig sig; } playfm; void confidence(int percentile, playfm *play, int nextfree, int cumfreq) { int i, target = cumfreq * percentile / 100; for (i = 0; i < nextfree; i++) { if (play[i].cumfreq >= target) { fprintf(stdout, "My opponent's move is unlikely to score above %d," " at a %d%% confidence level "//"(cumfreq%d] = %d)\n" "\n", play[i].score, //, i, play[i].cumfreqpercentile ); return; } } fprintf(stdout, "I'm stymied as to what the %d%% confidence level should be!\n", percentile); } int main(int argc, char **argv) { int c; int i, len, compatible; char inittarget[64]; char *target; char *textbuffer; char **wordlist; int wfreqs[26]; playfm play[10000]; char forms[1024]; char bag[128]; int nextfree = 0; int cumfreq = 0; int each, rc; rc = fscanf(stdin, "%s", bag); fprintf(stdout, "Bag: %s\n", bag); wordsigs = (bitmask *)malloc(sizeof(bitmask) * maxwords); makefreqs(bag, freqs); choosefields(freqs); makeonesig(bag, bagsig); makeuf(freqs, letmask, letbit, letwidth); for (;;) { rc = fscanf(stdin, "%s %s %s %s %d %d", &play[nextfree].place, &play[nextfree].pos, &play[nextfree].dirn, forms, &play[nextfree].score, &play[nextfree].freq ); if (rc != 6) break; makeonesig(play[nextfree].place, play[nextfree].sig); nextfree += 1; } for (each = nextfree-1; each >= 0; each--) { for (i = 0; i < each; i++) { bitmask *curnode; bitsig newsig; bitmask newmask; bitmask *cursig; int bitsleft; if (play[i].freq != 0) { /* Not already removed */ curnode = play[each].sig; cursig = play[i].sig; /* TO ADD (in DOMASK): bitsleft newmask curnode cursig newsig */ bitsleft = 0; switch (lastmask) { /* DOMASK issues a "break" from the switch if not compatible */ case 2: DOMASK(2) case 1: DOMASK(1) case 0: DOMASK(0) } if (!bitsleft) { /* exact match? */ // fprintf(stdout, "Broken match!: %s in %s\n", play[i].place, play[each].place); } else { // fprintf(stdout, "Subset match: %s (%d) in %s (%d)\n", // play[i].place, i, // play[each].place, each); /* Remove the lower-scoring item from the list! */ play[i].freq = 0; } } } } cumfreq = 0; for (each = 0; each < nextfree; each++) { cumfreq += play[each].freq; play[each].cumfreq = cumfreq; } fprintf(stdout, "%d plays analysed.\n", nextfree); fprintf(stdout, "Total no of draws = %d\n", cumfreq); confidence(0, play, nextfree, cumfreq); confidence(10, play, nextfree, cumfreq); confidence(50, play, nextfree, cumfreq); confidence(90, play, nextfree, cumfreq); confidence(100, play, nextfree, cumfreq); exit(0); return(0); }