/*
 * Copyright (c) 2010 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 */

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <list>
#include <map>
#include <set>
#include <string>

#include "board.h"

#ifdef DEBUG
static const char *rname[] = { "LOSS", "UNDECIDED", "DRAW", "WIN" };
FILE *logfile = NULL;
#endif

struct Move {
	Move(int planet, int turns, int ships, int value) :
	    planet(planet), turns(turns), ships(ships), value(value) {}
	bool operator<(const Move &o) const {
		if (value != o.value)
			return value > o.value;
		if (ships != o.ships)
			return ships < o.ships;
		if (turns != o.turns)
			return turns < o.turns;
		return planet < o.planet;
	}
	int planet;
	int turns;
	int ships;
	int value;
};

struct Order {
	Order(int src, int dst, int ships) : src(src), dst(dst), ships(ships) {}
	int src;
	int dst;
	int ships;
};

static bool
movesPossible(const Board &board, const map<int, int> &spares, const set<Move> &moves,
    unsigned long timeout, list<Order> &orders, int &value)
{
	map<int, int> s = spares, t = spares;

	orders.clear();
	value = 0;
	if (moves.empty())
		return true;
	if (spares.empty())
		return false;
	for (set<Move>::const_iterator i = moves.begin(); i != moves.end(); ++i)
		for (map<int, int>::const_iterator j = spares.begin();
		    j != spares.end(); ++j)
			if (board.distance(j->first, i->planet) == i->turns)
				s[j->first] -= i->ships;
	for (set<Move>::const_iterator i = moves.begin(); i != moves.end(); ++i) {
		int need = i->ships;
		while (need > 0) {
			if (usec() > timeout) {
				debug("WARNING: movesPossible() timed out\n");
				return false;
			}
			int best = -1, max = -999999;
			for (map<int, int>::const_iterator j = spares.begin();
			    j != spares.end(); ++j) {
				if (board.distance(j->first, i->planet) == i->turns &&
				    t[j->first] > 0 && s[j->first] > max) {
					max = s[j->first];
					best = j->first;
				}
			}
			if (best < 0)
				break;
			int take = need <= t[best] ? need : t[best];
			orders.insert(orders.end(), Order(best, i->planet, take));
			t[best] -= take;
			need -= take;
		}
		if (need > 0)
			return false;
		value += i->value;
	}
	return true;
}

static bool
movesPossible(const Board &board, const map<int, int> &spares, const set<Move> &moves)
{
	list<Order> orders;
	int value;

	return movesPossible(board, spares, moves, usec() + 10000, orders, value);
}

static double
powerSet(const Board &board, const map<int, int> &spares, const set<Move> &moves,
    unsigned long timeout, list<Order> &orders, int &value)
{
	const unsigned len = (unsigned)moves.size();
	const unsigned long end = 1UL << len;
	if (!len)
		return 100.0;
	if (len > 63) {
		debug("ERROR: powerSet() moves.size() %d\n", (int)moves.size());
		return 0.0;
	}
	debug("powerSet: %u moves, %lu combinations\n", len, end);
	for (unsigned long u = 1; u < end; ++u) {
		set<Move> m;
		set<Move>::const_iterator j = moves.begin();
		for (unsigned i = 0; i < len; ++i) {
			if (u & (1UL << i))
				m.insert(*j);
			j++;
		}
		list<Order> o;
		int v;
		if (movesPossible(board, spares, m, timeout, o, v) && v > value) {
			value = v;
			orders = o;
		}
		if (usec() > timeout) {
			double d = (double)u * 100.0 / (double)end;
			debug("WARNING: powerSet() timed out after "
			    "%lu of %lu (%.2lf%%)\n", u, end, d);
			return d;
		}
	}
	return 100.0;
}

static pair<int, int>
minDistance(const Board &board, int planet, int player)
{
	pair<int, int> min(999999, 0);
	int d;

	const vector<Planet> &planets = board.getPlanets();
	for (vector<Planet>::const_iterator i = planets.begin();
	    i != planets.end(); ++i)
		if (i->getId() != planet &&
		    i->getOwner() == player &&
		    i->getShips() > 0 &&
		    (d = board.distance(i->getId(), planet)) < min.first)
			min = make_pair(d, i->getId());
	return min;
}

static int
distanceToClosestEnemy(const Board &board, int planet)
{
	int min = 999999;
	const vector<Planet> &planets = board.getPlanets();

	for (vector<Planet>::const_iterator i = planets.begin();
	    i != planets.end(); ++i) {
		if (i->getOwner() == 2) {
			int d = board.distance(planet, i->getId());
			if (d < min)
				min = d;
		}
	}
	return min;
}

static map<int, int>
findSpares(const Board &board)
{
	const vector<Planet> &planets = board.getPlanets();
	map<int, int> spares;

	// where do i have spare ships? i.e. ships on planets that i can send
	// without losing the planet in the future
	for (vector<Planet>::const_iterator i = planets.begin();
	    i != planets.end(); ++i) {
		if (i->getOwner() != 1)
			continue;
		int low = i->getShips();
		// find lowest number of ships at any time between now and future
		Board f(board);
		while (!f.getFleets().empty() && low > 0) {
			f.nextTurn();
			if (f.getPlanets()[i->getId()].getOwner() != 1) {
				low = 0;
				break;
			}
			if (f.getPlanets()[i->getId()].getShips() < low)
				low = f.getPlanets()[i->getId()].getShips();
		}
		if (low > 0)
			spares[i->getId()] = low;
	}
	return spares;
}

void
Board::makeTurn()
{
	unsigned long t0 = usec();
	RESULT r;
	int p[3] = { 0, 0, 0 };
	int s[3] = { 0, 0, 0 };
	int f[2] = { 0, 0 };
	int g[2] = { 0, 0 };
	int x = 0;
	for (vector<Planet>::const_iterator i = planets.begin();
	    i != planets.end(); ++i) {
		p[i->getOwner()]++;
		s[i->getOwner()] += i->getShips();
		if (i->getOwner())
			g[i->getOwner() - 1] += i->getGrowth();
		if (i->getOwner() == 1)
			x += i->getShips();
	}
	for (vector<Fleet>::const_iterator i = fleets.begin();
	    i != fleets.end(); ++i) {
		f[i->getOwner() - 1]++;
		s[i->getOwner()] += i->getShips();
	}
	debug("========== BEGIN TURN ==========\n");
	debug("%d/%d/%d planets, %d/%d/%d ships, %d/%d growth, %d/%d fleets\n",
	    p[1], p[2], p[0], s[1], s[2], s[0], g[0], g[1], f[0], f[1]);
	r = rate();
	if (r != UNDECIDED) {
		debug("current rating is %s\n", rname[r]);
	}
	if (!s[1] /* XXX || (!p[1] && !p[0])*/ || !x) {
		debug("No ships available, can't issue any orders\n");
		return;
	}

	Board future(*this);
	while (!future.fleets.empty())
		future.nextTurn();
	r = future.rate();
	if (r != UNDECIDED) {
		debug("future rating is %s\n", rname[r]);
	}

	// find spare ships
	map<int, int> spares = findSpares(*this);
	debug("spares:");
	for (map<int, int>::iterator i = spares.begin(); i != spares.end(); ++i)
		debug(" %d:%d", i->first, i->second);
	debug("\n");

	// produce move candidates
	set<Move> moves;
	for (vector<Planet>::const_iterator i = planets.begin();
	    i != planets.end(); ++i) {
		int need, gain;

		if (usec() - t0 > 300000) {
			debug("WARNING: producing candidates took %lu us\n",
		 	    usec() - t0);
			break;
		}
		switch (i->getOwner() * 10 + future.planets[i->getId()].getOwner()) {
		case 0: { // N->N consider attacking neutral planet not yet under attack
			if (!p[1] || !p[2])
				break;
			pair<int, int> m1 = minDistance(*this, i->getId(), 1),
			    m2 = minDistance(*this, i->getId(), 2);
			// XXX consider m1 == m2
			for (int turn = m1.first; turn < m2.first; ++turn) {
				gain = (m2.first - turn) * i->getGrowth();
				if (gain < i->getShips())
					break;
				need = i->getShips() + 1;

				Move move(i->getId(), turn, need, gain);
				set<Move> single;
				single.insert(move);
				if (movesPossible(*this, spares, single)) {
					debug("  first-strike attacking neutral planet "
					    "%d with %d ships\n", i->getId(), need);
					moves.insert(move);
					break;
				}
			}
			break;
		}
		case 2: { // N->2 consider attacking neutral planet under opponent attack
			// when does opponent first own the planet?
			Board f(*this);
			int n = 0;
			while (f.planets[i->getId()].getOwner() == 0 && n < 50) {
				f.nextTurn();
				n++;
			}
			if (n == 50) {
				debug("ERROR: n == 50 (case 2)\n");
				break;
			}
			// don't prevent the attack from succeeding,
			// instead, attack the opponent in the NEXT turn!
			f.nextTurn();
			need = f.planets[i->getId()].getShips() + 1;
			gain = 2 * i->getGrowth();
			debug("  second-strike attacking neutral planet "
			    "%d with %d ships\n", i->getId(), need);
			moves.insert(Move(i->getId(), n + 1, need, gain));
			break;
		}
		case 12: { // 1->2 consider defending own planet under opponent attack
			// when does opponent first own the planet?
			Board f(*this);
			int n = 0;
			while (f.planets[i->getId()].getOwner() == 1 && n < 50) {
				f.nextTurn();
				n++;
			}
			if (n == 50) {
				debug("ERROR: n == 50 (case 12)\n");
				break;
			}
			// how many additional ships do i need to prevent that attack?
			need = f.planets[i->getId()].getShips();
			gain = i->getGrowth();
			debug("  defending planet %d in %d turns with %d ships\n",
			    i->getId(), n, need);
			moves.insert(Move(i->getId(), n, need, gain));
			break;
		}
		case 22: { // 2->2 consider attacking enemy planet
			if (!p[1])
				break;
			pair<int, int> m1 = minDistance(*this, i->getId(), 1), m2;
			if (p[2] > 1)
				m2 = minDistance(*this, i->getId(), 2);
			else
				m2 = make_pair(m1.first, i->getId());
			if (m1.first > 100) {
				debug("ERROR: m1.first %d > 100\n", m1.first);
				break;
			}
			Board f(*this);
			int turn = 0;
//			while (true) {
			while (turn <= m2.first) {
				f.nextTurn();
				turn++;
				if (turn < m1.first)
					continue;
				need = f.planets[i->getId()].getShips() + 1;
//				gain = 2 * i->getGrowth();
				gain = turn < m2.first ? 2 * i->getGrowth() : 0;

				Move move(i->getId(), turn, need, gain);
				set<Move> single;
				single.insert(move);
				if (movesPossible(*this, spares, single)) {
					debug("  attack enemy planet %d with %d ships\n",
					    i->getId(), need);
					moves.insert(move);
					break;
				}
			}
			break;
		}
		case 11: { // 1->1 consider reinforcing supply lines
			if (i->getShips() < 50)
				break;
			int ds = distanceToClosestEnemy(*this, i->getId());
			int min = 999999;
			int dst = -1;
			for (vector<Planet>::const_iterator j = planets.begin();
			    j != planets.end(); ++j) {
				if (j->getId() == i->getId() ||
				    future.planets[j->getId()].getOwner() != 1)
					continue;
				int dd = distanceToClosestEnemy(*this, j->getId());
				if (dd < min) {
					min = dd;
					dst = j->getId();
				}
			}
			if (dst < 0)
				break;
			if (min >= ds)
				break;
			need = i->getShips() / 5;
			gain = 1;
			debug("  reinforcing enemy-facing planet %d with %d ships\n",
			    dst, need);
			moves.insert(Move(dst, distance(i->getId(), dst), need, gain));
			break;
		}
		default: // N->1, 1->1, 2->1 do nothing
			break;
		}
	}

	// attack enemy where distance is minimal
	if (p[1] && p[2]/* && s[1] > 2 * s[2] && s[1] > 1000 && g[0] >= g[1]*/) {
		int min = 999999;
		int src = -1, dst = -1;
		for (vector<Planet>::const_iterator i = planets.begin();
		    i != planets.end(); ++i) {
			if (i->getOwner() != 1)
				continue;
			for (vector<Planet>::const_iterator j = planets.begin();
			    j != planets.end(); ++j) {
				if (j->getOwner() != 2)
					continue;
				int d = distance(i->getId(), j->getId());
				if (d < min) {
					min = d;
					src = i->getId();
					dst = j->getId();
				}
			}
		}
		if (src < 0 || dst < 0 || min < 1 || min > 999) {
			debug("ERROR: attack min: src %d, dst %d, min %d\n",
			    src, dst, min);
		} else {
			if (planets[src].getShips() >= 5/*50*/) {
				Board f(*this);
				for (int turn = 0; turn < min; ++turn)
					f.nextTurn();
				int need = planets[src].getShips() / 5;
				if (f.planets[dst].getOwner() == 2 &&
				    f.planets[dst].getShips() + 1 > need &&
				    f.planets[dst].getShips() + 1 <
				    planets[src].getShips())
					need = f.planets[dst].getShips() + 1;
				int gain = 1;
				if (f.planets[dst].getOwner() == 2 &&
				    f.planets[dst].getShips() < need)
					gain = planets[dst].getGrowth();
				debug("  ATTACKING enemy on %d with "
				    "%d ships with gain %d\n", dst, need, gain);
				moves.insert(Move(dst, min, need, gain));
			}
		}
	}

	if (moves.size() > 63) {
		debug("WARNING: truncating candidate moves from %d to 63\n",
		    (int)moves.size());
		set<Move> t;
		set<Move>::iterator i = moves.begin();
		for (int j = 0; j < 63; ++j)
			t.insert(*i++);
		moves = t;
	}

	unsigned long passed = usec() - t0;
	unsigned long timeout = passed < 900000 ? 900000 - passed : 0;
	debug("calling powerSet() after %lu us with timeout %lu us\n", passed, timeout);
	int max = -999999;
	list<Order> best;
	double d = powerSet(*this, spares, moves, usec() + timeout, best, max);
	debug("powerSet() %lu us, %.2lf complete", usec() - t0, d);
	if (best.size()) {
		debug(", max %d, best %d:", max, best.size());
		for (list<Order>::iterator j = best.begin(); j != best.end(); ++j) {
			debug(" %d,%d,%d", j->src, j->dst, j->ships);
		}
		debug("\n");
	} else
		debug(", empty\n");

	for (list<Order>::iterator j = best.begin(); j != best.end(); ++j) {
		#ifdef DEBUG
		if (issueOrder(1, j->src, j->dst, j->ships)) {
			debug("ERROR: issueOrder(src %d, dst %d, ships %d) failed!",
			    j->src, j->dst, j->ships);
		} else
		#endif
			printf("%d %d %d\n", j->src, j->dst, j->ships);
	}

	debug("========== END TURN (%lu us) ==========\n", usec() - t0);
}

int
main(int argc, char *argv[]) {
	int r;
	fd_set readfds;
	struct timeval tv;
	char buf[8192];
	string s;
	#ifdef DEBUG
	unsigned count = 0;
	unsigned long t;
	#endif

	#ifdef DEBUG
	if (!(logfile = fopen("MyBot.log", "w"))) {
		debug("fopen: %s\n", strerror(errno));
		return 1;
	}
	#endif
	srand(time(NULL));
	if (!((r = fcntl(STDIN_FILENO, F_GETFL)) & O_NONBLOCK))
		fcntl(STDIN_FILENO, r | O_NONBLOCK);

	while (true) {
		FD_ZERO(&readfds);
		FD_SET(STDIN_FILENO, &readfds);
		tv.tv_sec = 0;
		tv.tv_usec = 10; /* XXX */
		r = select(STDIN_FILENO + 1, &readfds, 0, 0, &tv);
		if (r < 0) {
			if (errno != EINTR) {
				debug("main: select: %s\n", strerror(errno));
				break;
			}
			continue;
		}
		if (r == 0)
			continue;
		r = read(STDIN_FILENO, buf, sizeof(buf) - 1);
		if (r < 0) {
			if (errno != EINTR) {
				debug("main: read: %s\n", strerror(errno));
				break;
			}
			continue;
		}
		if (r == 0) {
			debug("main: stdin EOF\n");
			break;
		}
		buf[r] = 0;
		s += buf;
		if (s.length() < 3 || s.substr(s.length() - 3) != "go\n")
			continue;
		s.resize(s.length() - 3);

		#ifdef DEBUG
		t = usec();
		#endif

		Board board(s.c_str());
		board.makeTurn();
		printf("go\n");
		fflush(stdout);

		#ifdef DEBUG
		t = usec() - t;
//		if (t < (count++ ? 1000000 : 3000000)) {
		count++;
		if (t < 1000000) {
			debug("main: reply %u sent in %lu us\n",
			    count, t);
		} else {
			debug("==========================================\n");
			debug("!!! ERROR: TIME LIMIT EXCEEDED: %lu us !!!\n", t);
			debug("==========================================\n");
		}
		#endif
		s.clear();
	}
	#ifdef DEBUG
	fflush(logfile);
	fclose(logfile);
	#endif
	return 0;
}