/* POTM ENTRY: QuackTheDuck */ /* Wolfram Hinderer (Eulfe) */ /* Your email: bords@my-dejanews.com */ /* compile instructions: cc QuackTheDuck.c */ #include #include #include #define TRUE 1 #define FALSE 0 #define MAXGA 6 /* Maximal number of guesses that are collected before a guess is made. Only used in specialmode, i.e. after a guess with wordlen-1 hits. */ #define MAXWLEN 9 /* maximal lenght of word */ #define MAXGUESSES 101 /* Maximal number of guesses that are allowed. It's funny that Fred did not make this 100, but 101. I had planned to submit another entry using 101 guesses for every word, but I did not have the time to do it. */ FILE *f; /* Used for storing data between runs of the program. Stores the rank list afer the first run, which decompresses it. */ int wordlen; char rank[MAXWLEN-2][26][26][27]; /* rank[pos][c1][c2][] stores the rank list of characters on position pos+2, given that on positions pos and pos+1 there are the character c1 and c2, respectively. */ char rank1[26]; /* rank list of the first letters of words */ char rank2[26][27]; /* rank list of the second letters of words, given the first letter */ char arank[MAXWLEN-2][26][26][27]; char arank1[26]; char arank2[26][27]; /* the rank lists are saved in arank, arank1, arank2. rank, rank1 and rank2 are filled up from these. */ int guesses; /* number of guesses already made */ char s[MAXGUESSES][MAXWLEN]; /* these guesses */ /* 0..25 are used for storing of characters. Exception: finalguess */ char h[MAXGUESSES],m[MAXGUESSES],nh[MAXGUESSES],nm[MAXGUESSES]; /* Number of hits, misses, non-hits, non-misses of the guesses. Should probably be integers or shorts. */ char h1[MAXGUESSES],nh1[MAXGUESSES],nm1[MAXGUESSES]; /* Number of hits, non-hits, non-misses if the word in the array guess was the hidden word. Builds up as guess builds up. */ char charanz[MAXGUESSES][26]; /* charanz[g][c] is the number of letters c in guess number g */ int charinguess[26]; /* Number of character in (new) guess */ char guess[MAXWLEN],finalguess[MAXWLEN+1],guessarr[MAXGA][MAXWLEN]; /* new guess (building up), the guess that is written, array of possible guesses (in specialmode) */ int anzpossguesses; /* Number of possible guesses (in specialmode) */ int specialmode; /* TRUE iff a guess with wordlen-1 hits has been made. */ char specialword[MAXWLEN]; /* the guess with wordeln-1 hits */ int bestsum; /* When no possible guess is found in 10 seconds, I guess the following word: whenever a word is found, that is possible except for that it has not enough non-misses for one of the previous guesses, the "number of non-misses" minus the "number of non-misses if this word was the hidden word" is summed over all previous guesses. A word minimizing this sum is the output. */ int maxdepth; /* only letters with a rank not exceeding maxdepth are used */ char relaxed; /* If I can't find a possbile guess, then I relax the conditions, i.e. the rank lists are filled up with the missing letters. */ void relax() /* Fills up ranklists with missing letters. Called when no possible guess can be found. For example, if the hidden word was QQQQQQQ, the rank lists for "QQ" would be empty, and earlier or later the program would find out, that there is no guess possible. The ranklists then are filled up, and every combination will appear somewhere, and is thus possible. */ { int i,j,k,l,m; char d[26],d1[26]; for (i=0;i<26;i++) d1[arank1[i]] = i; /* d1 stores which rank each letter has in the rank list for the first letter */ for (i=0;i<26;i++) { memcpy(d,arank1,26); k=0; for (j=0;j<26;j++) if (arank2[i][j]>=0) d[d1[arank2[i][j]]]=-1; else{ for (;d[k]<0;k++); arank2[i][j] = d[k++]; } } for (i=0; i=0) d[d1[arank[i][j][k][l]]]=-1; else{ for (;d[m]<0;m++); arank[i][j][k][l] = d[m++]; } } /* The missing letters are added to the rank lists */ maxdepth=1; /* Start it all over */ relaxed=TRUE; /* Now we are in relaxed mode */ } void saveandexit() /* I finally found a guess. Save state in temporary file, print guess, exit */ { if (specialmode) /* If I have already found a word which right except for one letter, I do something special */ { int i,j,anzdca,aapg=anzpossguesses; char dca[MAXGA*2],notnew[MAXGA*2],c,nnpos[MAXGA]; for (i=0;i=4) || ((anzpossguesses==3) && (aapg>4))) /* It only makes sense to use special output if there are at least 4 different (new) letters in the possible guesses. Or if there are 3, but before uniquifying them there were more than 4. */ { finalguess[0] = dca[anzdca]+'A'; for (i=1; i 950) /* 9.5 seconds over, time to go! */ { int i,j=0; if (anzpossguesses==0) if (finalguess[0]==-1) /* time is over, but no guess found */ { for (j=0; j=0) guess[0]=rank1[j]; guess[wordlen-1] = guess[0]; for (j=0; j=0) guess[1]=rank2[guess[0]][j]; for (i=2; i=0) {guess[i] = rank[i-2][guess[i-2]][guess[i-1]][j];} for (j=0; j'Z') || (finalguess[j]<'A')) finalguess[j]-=26;} /* seems to be useful, as relaxed rank lists look to similar: I don't want to guess QQQQQQQQQ over and over again. */ /* if (maxdepth<25) maxdepth++; */ /* Not sure if this is useful, but seemed no longer necessary */ } saveandexit(); } } void doguess() /* Hey, I found a possible guess! What should I do with it? */ { int i,j; char newguess=TRUE; /* ^^^^^ this was missing in the submitted version */ /* I played around a little with restrictions on the first guesses: no repeated letters and so on. Not sure if it's useful. */ if ((guesses<1) && (wordlen<=9)) { for (i=0; i<26; i++) if (charinguess[i]>1) return; if (charinguess[guess[wordlen-1]]>0) return; if (charinguess[25]>0) return; } else if ((guesses>0) && (guesses<3) && (h[guesses-1]<2) && (wordlen<=9)) { for (i=0; i<26; i++) if (charinguess[i]>h[guesses-1]+guesses/2+1) return; if (charinguess[guess[wordlen-1]]>h[guesses-1]+guesses/2) return; } for (i=0; i= MAXGA) saveandexit(); /* more than 6 guesses are not needed */ } void generateguess2(int n) /* guess n-th letter (n>2) */ { int j,k; char r,possible; char ah1[MAXGUESSES],anh1[MAXGUESSES],anm1[MAXGUESSES]; /* store old (german: alt) arrays of information */ char *ch; ch = rank[n-2][guess[n-2]][guess[n-1]]; /* Here starts the rank list */ if (*ch<0) return; /* If no combination is possible: return immediately. (This might be possible because there are short words with funny endings that are not part of a triple in longer words.) I'm not sure if it's worth it. Saves time for copying the arrays. */ if ((n==3) /*|| (n==wordlen-2)*/) checktime(); memcpy(ah1,h1,guesses); memcpy(anm1,nm1,guesses); memcpy(anh1,nh1,guesses); while (0<= (r =*ch) ) { possible = TRUE; for (j=0; j < guesses; j++) { if (s[j][n] == r) { if ((++h1[j]) > h[j]) {possible = FALSE;break;}} /* If current letter (in rank list) would be a hit, increase number of hits of current guess for previous guess no. j, and compare it to the number of hits actually in guess no. j. */ else { if ((++nh1[j]) > nh[j]) {possible = FALSE;break;}} /* Do the some with non-hits... */ if (charinguess[r]==0) { if ((nm1[j]+=charanz[j][r])>nm[j]) {possible = FALSE;break;}} /* ...and with non-misses */ } if (possible) { int sum=0; guess[n] = r; /* So, the n-th letter of the new guess becomes the letter in the rank list */ if (n==wordlen-1){ /* Hey, the new guess is completed!*/ for (k=0; k < guesses; k++) sum+=nm[k]-nm1[k]; /* ...unless there are not enough non-misses */ if (sum==0) doguess(); /* Number of non-misses is ok */ else if (sumh[j]) possible = FALSE;} else { if ((++nh1[j])>nh[j]) possible = FALSE;} if (charinguess[r]==0) { if ((nm1[j]+=charanz[j][r])>nm[j]) possible = FALSE;} } if (possible) { guess[1] = r; charinguess[r]++; generateguess2(2); charinguess[r]--; } memcpy(h1,ah1,guesses); memcpy(nm1,anm1,guesses); memcpy(nh1,anh1,guesses); ch++; checktime(); } } void generateguess() /* Generate the first letter of a new guess. Similar to generateguess2 and generateguess1, but simpler, and with a few initializations. */ { int i,j; char r,possible; for (i=0; i<=25; charinguess[i++]=0); for (i=0;ih[j]) possible = FALSE;} else { h1[j]=0; nh1[j]=1; if (nh1[j]>nh[j]) possible=FALSE;} if ((nm1[j]=charanz[j][r]) > nm[j]) possible=FALSE; } if (possible) { guess[0] = r; charinguess[r]++; generateguess1(); charinguess[r]--; } } } } void answerguess(char s2[], int h2, int m2) /* The last guess, s2, had h2 hits and m2 misses. */ { int i; memcpy(s[guesses],s2,wordlen); h[guesses] = h2; nh[guesses] = wordlen-h2; /* hits and non-hits */ for (i=0; i<=25; i++) charanz[guesses][i] = 0; for (i=0; i='0') && (c<='9')) { scanf("%s",s1); } else { scanf("%s%d%d",s1,&hinp,&minp); } if (strlen(s1)==1) /* New game! Initialize everything., */ { wordlen = s1[0]-'0'; f = fopen("TEMP.QuackTheDuck1","w"); for (i=0; i < strlen(datastr); i++) { c4 = datastr[i]; if(c4==10)c4=datastr[++i]; c5 = datastr[++i]; if(c5==10)c5=datastr[++i]; if (c4==31) c4=34; else if (c4==30) c4=92; if (c5==31) c5=34; else if (c5==30) c5=92; n = ((long)c4-(long)32)*(long)(256-32) + (long)c5-32; c3 = (char)(n / (long)(36*36)); n = n % (36*36); c2 = (char)(n / (long)36); c1 = (char)(n % (long)36); if (c1>=26) c1 += '0'-26; else c1 += 'A'; if (c2>=26) c2 += '0'-26; else c2 += 'A'; if (c3>=26) c3 += '0'-26; else c3 += 'A'; fprintf(f,"%c%c%c",c1,c2,c3); } fprintf(f,"0\n"); fflush(f); close(f); f = fopen("TEMP.QuackTheDuck1","r"); /* here only used for an intermediate stage */ for (i=0;i<=25;arank1[i++]=-1); for (i=0;i<=25;i++) for(j=0;j<=26;arank2[i][j++]=-1); for (i=0; i='A') && (c<='Z')) { arank1[l++] = c-'A'; fscanf(f,"%c",&c); } k=-1; i=j=0; while (j==0){ if ((c>='0') && (c<='9')){ emptylines = 0; while ((c>='0') && (c<='9')){ emptylines = 10*emptylines+c-'0'; fscanf(f,"%c",&c);} l = 0; k += emptylines+1; j += k/26; k %= 26; i += j/26; j %= 26; } else{ arank2[k][l++] = c-'A'; fscanf(f,"%c",&c);} } j=0; while (i='0') && (c<='9')){ emptylines = 0; while ((c>='0') && (c<='9')) { emptylines = 10*emptylines+c-'0'; fscanf(f,"%c",&c); } l = 0; k += emptylines+1; j += k/26; k %= 26; i += j/26; j %= 26; } else{ arank[i][j][k][l++] = c-'A'; fscanf(f,"%c",&c); } } close(f); maxdepth = guesses = 0; specialmode = FALSE; relaxed = FALSE; } else /* If we are continuing, read data saved in the temporary file */ { f = fopen("TEMP.QuackTheDuck1","r"); fread(&wordlen,4,1,f); fread(&guesses,4,1,f); fread(arank1,26,1,f); fread(arank2,26*27,1,f); fread(arank,(MAXWLEN-2)*26*26*27,1,f); fread(&maxdepth,sizeof(maxdepth),1,f); fread(s,MAXGUESSES*MAXWLEN,1,f); fread(h,MAXGUESSES,1,f); fread(m,MAXGUESSES,1,f); fread(nh,MAXGUESSES,1,f); fread(nm,MAXGUESSES,1,f); fread(charanz,MAXGUESSES*26,1,f); fread(&specialmode,4,1,f); fread(specialword,wordlen,1,f); fread(&relaxed,sizeof(relaxed),1,f); close(f); for (i=0; i < wordlen; i++) s1[i] -= 'A'; if (guesses<=3) maxdepth=0; else maxdepth--; /* As the first guesses are treated specially, reset maxdepth. */ answerguess(s1,hinp,minp); /* create tables for the guess */ } memcpy(rank1,arank1,26); memcpy(rank2,arank2,26*27); memcpy(rank,arank,7*26*26*27); for (i=maxdepth+1;i<=25;rank1[i++]=-1); for (i=0;i<=25;i++) for(j=maxdepth+1;j<=25;rank2[i][j++]=-1); for (i=0; i