static int do_history(void) {
	int best,best_length,i,j,num;

	num = my_history[0];
	best = best_length = 0;
	for (i = num - 1; i > best_length; --i) {
		for (j = 0; j < i 
		 && my_history[num - j] == my_history[i - j]
		 && opp_history[num - j] == opp_history[i - j]; ++j) ;
		if (j > best_length) {
			best_length = j;
			best = i;
		}
	}

	return best;
}

int historybot() {
	int best = do_history();
	if (0 == best) return biased_roshambo(1.0/3.0,1.0/3.0);
	return will_beat(opp_history[best + 1]);
}

int metabot() {
	int best = do_history();
	if (0 == best) return biased_roshambo(1.0/3.0,1.0/3.0);
	return will_beat(will_beat(my_history[best + 1]));
}

struct stats {
	int sum[3];
};

static void reset_stats(struct stats *st) {
	st->sum[0] = st->sum[1] = st->sum[2] = 0;
}

static void add_stats(struct stats *st,int i) {
	st->sum[i]++;
}

static int max_stats(const struct stats *st,int *score) {
	int i,j = -1;
	for (i = 0; i < 3; ++i)
		if (st->sum[i] > *score) {
			*score = st->sum[i];
			j = i;
		}

	return j;
}

static int tally_stats(const struct stats *st) {
	return st->sum[0] + st->sum[1] + st->sum[2];
}

struct predict {
	struct stats my,opp;
	int my_last,opp_last;
};

static void reset_predict(struct predict *pred) {
	reset_stats(&pred->my);
	reset_stats(&pred->opp);
	pred->my_last = pred->opp_last = -1;
}

/* last: opponent's last move (-1 if none)
 | opp:  algorithm's prediction of opponent's next move
 | my:   what the algorithm would predict for our next move */
static void do_predict(struct predict *pred,int last,int my,int opp) {
	if (-1 != last) {
		assert(pred->my_last != -1 && pred->opp_last != -1);
		add_stats(&pred->my,(3 + last - pred->my_last) % 3);
		add_stats(&pred->opp,(3 + last - pred->opp_last) % 3);
	}

	pred->my_last = my;
	pred->opp_last = opp;

	assert(tally_stats(&pred->my) == my_history[0]);
	assert(tally_stats(&pred->opp) == opp_history[0]);
}

static void scan_predict(struct predict *pred,int *best,int *move) {
	int i;
	i = max_stats(&pred->opp,best);
	if (-1 != i) *move = will_beat((pred->opp_last + i) % 3);
	i = max_stats(&pred->my,best);
	if (-1 != i) *move = will_beat((pred->my_last + i) % 3);
}

struct iocaine
{
	struct predict pr_history,pr_freq;
	struct stats my_stats,opp_stats;
};

static int iocaine(struct iocaine *i) {
	const int num = my_history[0];
	const int last = (num > 0) ? opp_history[num] : -1;
	const int guess = biased_roshambo(1.0/3.0,1.0/3.0);

	if (0 == num) {
		reset_predict(&i->pr_history);
		reset_predict(&i->pr_freq);
		reset_stats(&i->my_stats);
		reset_stats(&i->opp_stats);
	} else {
		add_stats(&i->my_stats,my_history[num]);
		add_stats(&i->opp_stats,opp_history[num]);
	}

	{
		const int best = do_history();
		if (0 == best)
			do_predict(&i->pr_history,last,guess,guess);
		else
			do_predict(&i->pr_history,last,
			           my_history[best + 1],opp_history[best + 1]);
	}

	{
		int my_best = -1,opp_best = -1;
		int my_freq = max_stats(&i->my_stats,&my_best);
		int opp_freq = max_stats(&i->opp_stats,&opp_best);
		do_predict(&i->pr_freq,last,
		           (-1 == my_freq) ? guess : my_freq,
		           (-1 == opp_freq) ? guess : opp_freq);
	}

	{
		int score = -1,move = -1;
		scan_predict(&i->pr_history,&score,&move);
		scan_predict(&i->pr_freq,&score,&move);
		assert(-1 != move);
		return move;
	}
}

int iocainebot(void)
{
	static struct iocaine p;
	return iocaine(&p);
}

int sicilian(void)
{
	static struct iocaine p;
	return will_beat(iocaine(&p));
}