/**
* Fill in one symbol at the time. To guess the placements of next symbol X,
* take each prefix of the existing string and pad it with X's to length n.
*
* Queries: n x sigma
*
* Author: Catalin Francu
**/
#include <string.h>
#define MAX_N 5000
char q[MAX_N + 1];
char qc[MAX_N + 1]; /* copy of c */
int answer[MAX_N + 1];
int query(char *q);
char* guess(int n, int s) {
q[0] = '\0';
int qlen = 0;
for (int c = 'a'; c < 'a' + s; c++) {
strcpy(qc, q);
for (int i = qlen; i < n; i++) {
q[i] = c;
}
q[n] = 0;
for (int i = qlen; i >= 0; i--) {
q[i] = c;
answer[i] = query(q) - i; /* count only the c's, not the prefix */
}
/* rebuild q from qc interleaved with occurrences of c */
int newlen = 0;
for (int i = 0; i <= qlen; i++) {
for (int j = 0; j < answer[i] - answer[i + 1]; j++) {
q[newlen++] = c;
}
if (i < qlen) {
q[newlen++] = qc[i];
}
}
q[newlen] = 0;
qlen = newlen;
}
return q;
}
