/**
* Like cf-n-sigma-2.c, but processes characters in increasing order of
* frequency. The worst case requires n * sigma / 2 queries.
*
* Author: Catalin Francu
**/
#include <string.h>
#define MAX_N 5000
#define MAX_SIGMA 26
char q[MAX_N + 1];
int f[MAX_SIGMA];
int n, s;
int query(char *q);
void shiftRight(char *s) {
char save = *s;
do {
int tmp = save;
save = *(s + 1);
*(s + 1) = tmp;
s++;
} while (*s != '\0');
}
void shiftLeft(char *s) {
do {
*(s - 1) = *s;
s++;
} while (*(s - 1) != '\0');
}
/* find the next smallest frequency */
char findNext() {
int pos = 0;
for (int i = 1; i < s; i++) {
if (f[i] < f[pos]) {
pos = i;
}
}
f[pos] = n + 1; /* so it is never found again */
return 'a' + pos;
}
char* guess(int localN, int localS) {
n = localN;
s = localS;
/* run s-1 queries to determine element frequencies */
/* the last frequency is computed by difference */
q[n] = '\0';
f[0] = n;
for (int i = 1; i < s; i++) {
memset(q, 'a' + i, n);
f[i] = query(q);
f[0] -= f[i];
}
q[0] = '\0';
int c = findNext(); /* current symbol being inserted */
int answer = 0;
int pos = 0;
int len = 0; /* length of current string */
while (answer < n) {
/* roll back the last change and move on if answer != len */
if (answer != len) {
shiftLeft(q + pos);
len--;
if (q[pos - 1] == '\0') {
/* move on to the next symbol */
c = findNext();
pos = 0;
}
/* otherwise leave pos unchanged, which skips one symbol < c */
}
/* insert another copy of c at position pos */
shiftRight(q + pos);
q[pos++] = c;
len++;
answer = query(q);
}
return q;
}
