#include "combo.h"
#include <vector>
#include <algorithm>
using namespace std;
void dfs1(string & seq, string & s, int max_len, int n, vector<vector<bool> > & dp) {
int len = (int)s.size(), sum = 0;
for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0);
vector<char> chars = {'A', 'B', 'X', 'Y'};
if((int)seq.size() + len > 4 * n) return;
if(len == max_len) { seq += s; return; }
int checked = 0;
for(int i = 0; i < 4 && checked < sum - 1; i++) if(dp[len][i]) {
s.push_back(chars[i]);
dfs1(seq, s, max_len, n, dp);
s.pop_back();
checked++;
}
}
void dfs2(int & seq_len, int len, int max_len, int n, vector<vector<bool> > & dp, int coins) {
bool right = len < coins, first_incorrect = len == coins;
int sum = 0;
for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0);
if(seq_len + len > 4 * n) return;
if(len == max_len) { seq_len += len; return; }
if(right) {
int checked = 0, i = 0;
for(; i < 4 && checked < sum - 1; i++) if(dp[len][i]) {
checked++;
}
for(; i < 4; i++) {
// we were right here without using this one
// so it must be false
dp[len][i] = false;
}
} else if(first_incorrect) {
int checked = 0, i = 0;
for(; i < 4 && checked < sum - 1; i++) if(dp[len][i]) {
dp[len][i] = false;
checked++;
}
}
// we simulate the search
int checked = 0;
for(int i = 0; i < 4 && checked < sum - 1; i++) if(dp[len][i]) {
dfs2(seq_len, len + 1, max_len, n, dp, coins);
checked++;
}
}
char guess_next(string & s, int n, vector<vector<bool> > & dp) {
int len = s.size(), sum = 0;
for(int i = 0; i < 4; i++) sum += (dp[len][i] ? 1 : 0);
vector<char> chars = {'A', 'B', 'X', 'Y'};
int checked = 0;
for(int i = 0; i < 4; i++) if(dp[len][i]) {
char c = chars[i];
if(checked == sum - 1) return c;
int max_len = max(len + 20, n);
string seq = "";
string s = "";
int seq_len = 0;
dfs1(seq, s, max_len, n, dp);
while(seq.size() < 4 * n) seq += c;
int coins = press(seq);
dfs2(seq_len, 0, max_len, n, dp, coins);
if(len == 0 && coins > 0) {
for(int j = 1; j < n; j++) {
dp[j][i] = false;
}
}
if(coins > len) return chars[i];
}
}
string guess_sequence(int n) {
string s = "";
vector<vector<bool> > dp(n, vector<bool>(4, true));
for(int i = 0; i < n; i++) {
s += guess_next(s, n, dp);
}
return s;
}
