CodinGame - Ghost in the cell

Player.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

class Player {

	// Misc stuff
	public static final boolean isDebugOn = true;

	// Game constants, write them here once for all. The match constants however should go in MatchConstants
	public static final int neutral = 0;
	public static final int me = 1;
	public static final int op = -1;
	public static final int nbStartingBombs = 2;
	public static final int factoryBombCoolDown = 5;
	public static final int sacrificeForIncrease = 10;
	public static final int noLink = -1;
	public static final int maxTurns = 200;
	public static final int minDirectDistanceBetweenFactories = 1;
	public static final int maxDirectDistanceBetweenFactories = 20;

	// Game variables
	public static int maxProd = 0;
	private static GameState previousGameState;
	private static boolean stopGame = false;

	// AIs
	public static AI ai = new HybridAI();

	public static void main(String args[]) {

		Scanner in = new Scanner(System.in);
		initMatch(in);

		// game loop
		while (true) {

			GameState gs = initRound(in);

			List<Action> actionList = ai.computeAction(gs);

			finalizeRound(actionList, gs);

			out(actionList);

		}
	}

	private static void initMatch(Scanner in) {

		debug("Starting the match !");
		ai.printAI();

		MatchConstants.factoryCount = in.nextInt(); // the number of factories
		Time.startRoundTimer();

		// Init the factory distances
		MatchConstants.factoryDirectDistances = new int[MatchConstants.factoryCount][MatchConstants.factoryCount];
		MatchConstants.factoryShortestDistances = new int[MatchConstants.factoryCount][MatchConstants.factoryCount];
		MatchConstants.factoryPath = new int[MatchConstants.factoryCount][MatchConstants.factoryCount];

		for (int[] row : MatchConstants.factoryDirectDistances) {
			Arrays.fill(row, noLink); // -1 by default
		}

		int distanceSum = 0;

		int linkCount = in.nextInt(); // the number of links between factories
		for (int i = 0; i < linkCount; i++) {
			int factory1 = in.nextInt();
			int factory2 = in.nextInt();
			int distance = in.nextInt();

			MatchConstants.factoryDirectDistances[factory1][factory2] = distance;
			MatchConstants.factoryDirectDistances[factory2][factory1] = distance;

			if (distance > MatchConstants.maxDirectDistanceBetweenFactoriesForThisMatch) {
				MatchConstants.maxDirectDistanceBetweenFactoriesForThisMatch = distance;
			}
			if (distance < MatchConstants.minDirectDistanceBetweenFactoriesForThisMatch) {
				MatchConstants.minDirectDistanceBetweenFactoriesForThisMatch = distance;
			}

			if (distance <= 3) {
				// Nothing shorter than direct. TODO: but it could be useful to not go direct
				MatchConstants.factoryShortestDistances[factory1][factory2] = distance;
				MatchConstants.factoryShortestDistances[factory2][factory1] = distance;
				MatchConstants.factoryPath[factory1][factory2] = factory2;
				MatchConstants.factoryPath[factory2][factory1] = factory1;
			}

			distanceSum += distance;
		}

		MatchConstants.averageDirectDistanceBetweenFactoriesForThisMatch = distanceSum / (double) linkCount;

		debug("Starting map tests");
		// testTheMap();

		// Now init the pathfinding
		debug("Starting initPathFinding");
		initPathFinding();
		initNeighs();

		Time.debugDuration("End initMatch");

	}

	public static void initNeighs() {

		MatchConstants.neighs = new List[MatchConstants.factoryCount];

		for (int i = 0; i < MatchConstants.factoryCount; i++) {

			MatchConstants.neighs[i] = new ArrayList<>();

			// Check if j is a neigh or not
			for (int j = 0; j < MatchConstants.factoryCount; j++) {

				if (i != j) {

					boolean isNeigh = true;
					int directD = MatchConstants.factoryDirectDistances[i][j];

					// It's a neigh if going through any other factory won't improve the distance
					for (int k = 0; k < MatchConstants.factoryCount; k++) {
						if (k != i && k != j && MatchConstants.factoryDirectDistances[i][k] + MatchConstants.factoryDirectDistances[k][j] <= directD) {
							isNeigh = false;
							break;
						}
					}

					if (isNeigh) {
						MatchConstants.neighs[i].add(j);
					}

				}
			}

			String neighList = "";
			for (Integer n : MatchConstants.neighs[i]) {
				neighList += n + " ";
			}

			debug("Neighs for " + i + ": " + neighList);

		}

	}

	public static void initPathFinding() {

		// Init diagonal
		for (int i = 0; i < MatchConstants.factoryCount; i++) {
			MatchConstants.factoryDirectDistances[i][i] = 0;
		}

		debug("Printing the factoryDirectDistances matrix:");
		for (int i = 0; i < MatchConstants.factoryDirectDistances.length; i++) {
			String row = "";
			for (int j = 0; j < MatchConstants.factoryDirectDistances.length; j++) {
				row += String.format("%02d", MatchConstants.factoryDirectDistances[i][j]) + " ";
			}
			debugForInput(row);
		}

		// Init everything to -1
		for (int i = 0; i < MatchConstants.factoryCount; i++) {
			Arrays.fill(MatchConstants.factoryShortestDistances[i], -1);
			Arrays.fill(MatchConstants.factoryPath[i], -1);
		}

		// Init diagonal
		for (int i = 0; i < MatchConstants.factoryCount; i++) {
			MatchConstants.factoryShortestDistances[i][i] = 0;
			MatchConstants.factoryPath[i][i] = -2;
		}

		if (MatchConstants.factoryCount < 13) {

			// Use algo
			List<Integer> availableIntermediates = new ArrayList<>();
			for (int i = 0; i < MatchConstants.factoryCount; i++) {
				availableIntermediates.add(i);
			}

			for (int i = 0; i < MatchConstants.factoryCount; i++) {
				for (int j = 0; j < MatchConstants.factoryCount; j++) {
					if (i != j) {

						if (MatchConstants.factoryDirectDistances[i][j] <= 3) {
							MatchConstants.factoryShortestDistances[i][j] = MatchConstants.factoryDirectDistances[i][j];
							MatchConstants.factoryPath[i][j] = j;
						} else {
							availableIntermediates.remove(new Integer(j));
							int[] shortestPathFromItoJ = getShortestPathFromTo(i, j, availableIntermediates);
							MatchConstants.factoryShortestDistances[i][j] = shortestPathFromItoJ[0];
							MatchConstants.factoryPath[i][j] = shortestPathFromItoJ[1];
							availableIntermediates.add(new Integer(j));
						}

					}

				}
			}

		} else {

			// Init only with direct stuff
			for (int i = 0; i < MatchConstants.factoryCount; i++) {
				for (int j = 0; j < MatchConstants.factoryCount; j++) {
					if (i != j) {
						MatchConstants.factoryShortestDistances[i][j] = MatchConstants.factoryDirectDistances[i][j];
						MatchConstants.factoryPath[i][j] = j;
					}
				}
			}

		}

		debug("Printing the factoryShortestDistances matrix:");
		for (int i = 0; i < MatchConstants.factoryShortestDistances.length; i++) {
			String row = "";
			for (int j = 0; j < MatchConstants.factoryShortestDistances.length; j++) {
				row += String.format("%02d", MatchConstants.factoryShortestDistances[i][j]) + " ";
			}
			debug(row);
		}

		debug("Printing the factoryPath matrix:");
		for (int i = 0; i < MatchConstants.factoryPath.length; i++) {
			String row = "";
			for (int j = 0; j < MatchConstants.factoryPath.length; j++) {
				row += String.format("%02d", MatchConstants.factoryPath[i][j]) + " ";
			}
			debug(row);
		}

		debug("End initPathFinding");

	}

	public static int[] getShortestPathFromTo(int i, int j, List<Integer> availableIntermediates) {

		// Init with direct access
		int[] result = new int[] { MatchConstants.factoryDirectDistances[i][j], j };
		List<Integer> newAvailableIntermediates = new ArrayList<>(availableIntermediates);
		newAvailableIntermediates.remove(new Integer(i));

		for (int k : newAvailableIntermediates) {
			if (MatchConstants.factoryDirectDistances[i][k] + 1 < result[0]) {
				int[] shortestPathFromKtoJ = getShortestPathFromTo(k, j, newAvailableIntermediates);
				if (shortestPathFromKtoJ[0] + MatchConstants.factoryDirectDistances[i][k] + 1 < result[0]) {
					result[0] = shortestPathFromKtoJ[0] + MatchConstants.factoryDirectDistances[i][k] + 1;
					result[1] = k;
				}
			}

		}

		return result;

	}

	public static enum EntityType {
		FACTORY, TROOP, BOMB
	}

	public static final Comparator<Troop> turnsToArriveComparator = new Comparator<Player.Troop>() {

		@Override
		public int compare(Troop o1, Troop o2) {

			if (o1.turnsToArrive > o2.turnsToArrive) {
				return 1;
			} else if (o1.turnsToArrive < o2.turnsToArrive) {
				return -1;
			}

			if (o1.id > o2.id) {
				return 1;
			}
			return -1;
		}

	};

	private static GameState initRound(Scanner in) {

		GameState result = null;

		int entityCount = in.nextInt(); // the number of entities (e.g. factories and troops)

		if (previousGameState == null) {
			result = new GameState(1, nbStartingBombs, nbStartingBombs, GameResult.UNKNOWN);
		} else {
			Time.startRoundTimer();
			result = new GameState(previousGameState.round + 1, previousGameState.myRemainingBombs, previousGameState.opRemainingBombs, GameResult.UNKNOWN);
		}

		for (int i = 0; i < entityCount; i++) {
			int entityId = in.nextInt();
			String entityType = in.next();
			int arg1 = in.nextInt();
			int arg2 = in.nextInt();
			int arg3 = in.nextInt();
			int arg4 = in.nextInt();
			int arg5 = in.nextInt();

			switch (EntityType.valueOf(entityType)) {
			case FACTORY:
				result.factories[entityId].owner = arg1;
				result.factories[entityId].cyborgCount = arg2;
				result.factories[entityId].topProd = arg3;
				result.factories[entityId].nbTurnsBeforeProduction = arg4;
				if (arg4 > 0) {
					result.factories[entityId].prod = 0;
				} else {
					result.factories[entityId].prod = arg3;
				}
				break;
			case TROOP:
				if (arg1 == 1) {
					result.factories[arg3].myTroops.add(new Troop(entityId, arg1, arg4, arg5));
				} else {
					result.factories[arg3].opTroops.add(new Troop(entityId, arg1, arg4, arg5));
				}
				break;
			case BOMB:
				Bomb bomb = new Bomb(entityId, arg1, arg3, arg4);
				result.factories[arg2].bombsSent.add(bomb);

				if (bomb.owner == me) {
					result.factories[bomb.targetId].bombsArriving.add(bomb);
				}

				if (previousGameState != null && !previousGameState.factories[arg2].bombsSent.contains(bomb)) {
					if (bomb.owner == op) {
						result.opRemainingBombs--;
					}
				}
				break;

			default:
				break;
			}

		}

		updateClosestOpFactory(result);
		sortTroops(result);
		updateMaxProd(result);

		if (isDebugOn) {
			// result.print();
		}

		return result;

	}

	private static void sortTroops(GameState result) {
		for (Factory factory : result.factories) {
			factory.myTroops.sort(turnsToArriveComparator);
			factory.opTroops.sort(turnsToArriveComparator);
		}

	}

	private static void updateClosestOpFactory(GameState result) {

		for (Factory factory : result.factories) {

			for (Factory factory2 : result.factories) {
				if (factory2.owner == op) {
					factory.closestOpFactoryDistance = Math.min(factory.closestOpFactoryDistance, MatchConstants.factoryDirectDistances[factory.id][factory2.id]);
				} else if (factory2.owner == me) {
					factory.closestMyFactoryDistance = Math.min(factory.closestMyFactoryDistance, MatchConstants.factoryDirectDistances[factory.id][factory2.id]);
				}
			}

		}

	}

	private static void updateMaxProd(GameState result) {
		for (Factory factory : result.factories) {
			if (factory.prod > maxProd) {
				maxProd = factory.prod;
			}
		}

	}

	private static void finalizeRound(List<Action> actionList, GameState gs) {

		if (!stopGame) {

			previousGameState = gs;
			Time.debugDuration("Total round duration");
		}

	}

	public static class Time {
		// Time constants
		private static final int maxRoundTime = 50; // 100 ms max to answer
		private static final int roundTimeMargin = 1;
		private static final int maxFirstRoundTime = 1000; // 1 s max to answer for first turn only
		private static final int firstRoundTimeMargin = 50;
		private static final int maxRoundTimeWithMargin = maxRoundTime - roundTimeMargin;
		private static final int maxFirstRoundTimeWithMargin = maxFirstRoundTime - firstRoundTimeMargin;
		public static boolean noTimeLimit = false;

		// Time variables
		private static long roundStartTime;

		public static void startRoundTimer() {
			roundStartTime = System.currentTimeMillis();
		}

		public static boolean isTimeLeft(boolean firstTurn) {
			return getRoundDuration() < maxRoundTimeWithMargin || (firstTurn && getRoundDuration() < maxFirstRoundTimeWithMargin) || noTimeLimit;
		}

		public static boolean isTimeLeft() {
			return isTimeLeft(false);
		}

		public static long getRoundDuration() {
			return System.currentTimeMillis() - roundStartTime;
		}

		public static void debugDuration(String message) {
			debug(message + ": " + getRoundDuration());

		}

	}

	private static void out(List<Action> actionList) {

		String separator = ";";

		if (stopGame) {
			System.out.println("Failure!");
		} else {

			String output = "";

			for (Action action : actionList) {
				switch (action.actionType) {
				case MOVE:
					output += action.actionType + " " + action.source + " " + action.destination + " " + action.cyborgCount + separator;
					break;
				case BOMB:
					output += action.actionType + " " + action.source + " " + action.destination + separator;
					break;
				case INC:
					output += action.actionType + " " + action.source + separator;
					break;
				case MSG:
					output += action.actionType + " " + action.message;
					break;
				case WAIT:
					output += action.actionType + separator;
					break;
				default:
					break;
				}
			}

			System.out.println(output);

		}

	}

	private static int getMirrorId(int id) {
		if (id == 0) {
			return 0;
		} else if (id % 2 == 0) {
			return id - 1;
		} else {
			return id + 1;
		}
	}

	private static void debug(String message) {
		if (isDebugOn) {
			System.err.println(message);
		}
	}

	private static void debugForced(String message) {
		System.err.println(message);
	}

	private static void debugFactoryList(String message, List<Factory> factoryList) {

		if (message != null) {
			debug(message);
		}

		for (Factory factory : factoryList) {
			debug(factory.toString());
		}

	}

	private static void debugActionsList(String message, List<Action> actionList) {

		if (message != null) {
			debug(message);
		}

		for (Action action : actionList) {
			debug(action.toString());
		}

	}

	private static final String debugStartLine = "\"";
	private static final String debugEndLine = "\",";
	public static final String debugSep = " ";

	// Debug for later input in tests
	public static void debugForInput(String message) {
		debug(debugStartLine + message + debugEndLine);
	}

	public enum ActionType {
		MOVE, WAIT, BOMB, MSG, INC
	}

	public static class Action {

		public ActionType actionType;

		public int source;
		public int destination;
		public int cyborgCount;

		public String message;

		private Action(ActionType actionType, int source, int destination, int cyborgCount, String message) {
			super();
			this.actionType = actionType;
			this.source = source;
			this.destination = destination;
			this.cyborgCount = cyborgCount;
			this.message = message;
		}

		public static Action getMoveAction(int source, int destination, int cyborgCount, GameState gs) {
			gs.factories[source].cyborgCount -= cyborgCount;
			gs.factories[destination].myTroops.add(new Troop(-1, me, cyborgCount, MatchConstants.factoryDirectDistances[source][destination]));
			return new Action(ActionType.MOVE, source, destination, cyborgCount, null);
		}

		public static Action getIncreaseAction(int factoryId, GameState gs) {
			gs.factories[factoryId].cyborgCount -= sacrificeForIncrease;
			return new Action(ActionType.INC, factoryId, -2, -2, null);
		}

		public static Action getBombAction(int source, int destination, GameState gs) {
			if (gs.myRemainingBombs > 0) {
				gs.myRemainingBombs--;
				return new Action(ActionType.BOMB, source, destination, -2, null);
			} else {
				debug("Attempting to launch a bomb but no stock");
				stopGame = true;
				return null;
			}
		}

		public static Action getWaitAction() {
			return new Action(ActionType.WAIT, -2, -2, -2, null);
		}

		public static Action getMessageAction(String message) {
			return new Action(ActionType.MSG, -2, -2, -2, message);
		}

		@Override
		public String toString() {
			return "Action " + actionType + " " + source + " " + destination + " " + cyborgCount + " " + message;
		}

	}

	// Stores stuff which is not going to change for the whole match, but could change from one match to another
	public static class MatchConstants {

		public static int factoryCount;
		public static int[][] factoryDirectDistances; // Stores the direct distance between i and j
		public static int maxDirectDistanceBetweenFactoriesForThisMatch = -1;
		public static int minDirectDistanceBetweenFactoriesForThisMatch = maxDirectDistanceBetweenFactories;
		public static double averageDirectDistanceBetweenFactoriesForThisMatch = -1;
		public static int[][] factoryShortestDistances; // Stores the shortest distance between i and j ( <= direct distance)
		public static int[][] factoryPath; // Stores the factory id to go when travelling from i to j (so usually j for a direct path, but not always)

		public static List<Integer>[] neighs;

		public static void print() {

			debugForInput("");
		}

	}

	public static class GameStateObject {

		public void print() {
			debugForInput(toString());
		}

	}

	public static class Entity extends GameStateObject {

		public int id;
		public EntityType type;
		public int owner;

		public Entity(int id, EntityType type, int owner) {
			super();
			this.id = id;
			this.type = type;
			this.owner = owner;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + id;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Entity other = (Entity) obj;
			if (id != other.id)
				return false;
			return true;
		}

	}

	public static class Factory extends Entity {

		public int prod;
		public int topProd;
		public int cyborgCount;
		public int nbTurnsBeforeProduction;
		public int closestMyFactoryDistance;
		public int closestOpFactoryDistance;
		public boolean tryingToCapture = false;

		public List<Troop> myTroops;
		public List<Troop> opTroops;

		public List<Bomb> bombsSent;
		public List<Bomb> bombsArriving;

		public Factory(int id, int prod, int owner, int cyborgCount, int nbTurnsBeforeProduction) {
			super(id, EntityType.FACTORY, owner);
			this.prod = prod;
			this.cyborgCount = cyborgCount;
			this.nbTurnsBeforeProduction = nbTurnsBeforeProduction;
			this.myTroops = new ArrayList<Player.Troop>();
			this.opTroops = new ArrayList<Player.Troop>();
			this.bombsSent = new ArrayList<Player.Bomb>();
			this.bombsArriving = new ArrayList<Player.Bomb>();
			closestMyFactoryDistance = 21;
			closestOpFactoryDistance = 21;
		}

		@Override
		public String toString() {
			return "Factory " + id + " " + prod + " " + topProd + " " + cyborgCount + " " + nbTurnsBeforeProduction + " " + closestMyFactoryDistance + " " + closestOpFactoryDistance + " " + myTroops
					+ " " + opTroops + " " + bombsSent;
		}

	}

	public static class Troop extends Entity {

		public int cyborgCount;
		public int turnsToArrive;

		public Troop(int id, int owner, int cyborgCount, int turnsToArrive) {
			super(id, EntityType.TROOP, owner);
			this.owner = owner;
			this.cyborgCount = cyborgCount;
			this.turnsToArrive = turnsToArrive;
		}

		@Override
		public String toString() {
			return "Troop " + id + " " + owner + " " + cyborgCount + " " + turnsToArrive;
		}

	}

	public static class Bomb extends Entity {

		public int targetId;
		public int turnsToArrive;
		public int turnsSinceLaunch;

		public Bomb(int id, int owner, int targetId, int turnsToArrive) {
			super(id, EntityType.BOMB, owner);
			this.targetId = targetId;
			this.turnsToArrive = turnsToArrive;
			this.turnsSinceLaunch = 0;
		}

		@Override
		public String toString() {
			return "Bomb " + id + " " + owner + " " + targetId + " " + turnsToArrive + " " + turnsSinceLaunch;
		}

	}

	public static enum GameResult {
		UNKNOWN, // Game not yet finished
		WON, // Game finished and won by us :)
		LOST, // Game finished and lost :(
		TIE // Game finished and tied
	}

	public static class GameState extends GameStateObject {

		public int round;

		public Factory[] factories;

		public int myRemainingBombs;
		public int opRemainingBombs;

		public GameResult gameResult;

		public GameState(int round, int myRemainingBombs, int opRemainingBombs, GameResult gameResult) {
			super();
			this.round = round;
			factories = new Factory[MatchConstants.factoryCount];
			for (int i = 0; i < factories.length; i++) {
				factories[i] = new Factory(i, -2, -2, -2, 0);
			}
			this.myRemainingBombs = myRemainingBombs;
			this.opRemainingBombs = opRemainingBombs;
			this.gameResult = gameResult;
		}

		public List<Factory> getPresentFactories(int owner) {

			List<Factory> result = new ArrayList<>();

			for (Factory factory : factories) {
				if (factory.owner == owner) {
					result.add(factory);
				}
			}

			return result;

		}

		public List<Factory> getAllNeighs(Factory factory) {

			List<Factory> neighs = new ArrayList<>();

			for (Integer i : MatchConstants.neighs[factory.id]) {
				neighs.add(factories[i]);
			}

			return neighs;

		}

		public List<Factory> getNeighsForOwner(int owner, Factory factory) {

			List<Factory> neighs = new ArrayList<>();

			for (Integer i : MatchConstants.neighs[factory.id]) {
				if (factories[i].owner == owner) {
					neighs.add(factories[i]);
				}
			}

			return neighs;

		}

		@Override
		public String toString() {
			return "GameState " + round + " " + myRemainingBombs + " " + opRemainingBombs + " " + gameResult;
		}

		@Override
		public void print() {
			debug(toString());
			for (Factory factory : factories) {
				debug(factory.toString());
			}
		}

	}

	public static abstract class AI {

		public abstract List<Action> compute(GameState gs);

		public abstract String getAIMessage();

		public void printAIParameters() {

		}

		public List<Action> computeAction(GameState gs) {
			printAIParameters();

			List<Action> result = compute(gs);

			if (result.isEmpty()) {
				result.add(Action.getWaitAction());
			}

			result.add(Action.getMessageAction(getAIMessage()));

			return result;
		}

		public void printAI() {
			debug("Using base AI: " + this.getClass().getName());
		}
	}

	public static class HybridAI extends AI {

		public static final AI firstTurnAI = new FirstTurnAI();
		public static final AI defendAI = new DefendAI();
		public static final AI progressAI = new ProgressAI();
		public static final AI captureAI = new CaptureAI();
		public static final AI bombAI = new BombAI();

		@Override
		public List<Action> compute(GameState gs) {
			List<Action> result = new ArrayList<>();

			if (gs.round == 1) {
				result = firstTurnAI.compute(gs);
			} else {

				List<Action> defendActions = defendAI.compute(gs);
				debugActionsList("Defend actions", defendActions);

				List<Action> progressActions = progressAI.compute(gs);
				debugActionsList("Progress actions", progressActions);

				List<Action> captureActions = captureAI.compute(gs);
				debugActionsList("Capture actions", captureActions);

				List<Action> bombActions = bombAI.compute(gs);
				debugActionsList("Bomb actions", bombActions);

				List<Action> avoidBombActions = captureAI.compute(gs);
				debugActionsList("Avoid bomb actions", captureActions);

				result.addAll(bombActions);
				result.addAll(defendActions);
				result.addAll(progressActions);
				result.addAll(captureActions);
				result.addAll(avoidBombActions);
			}

			return result;
		}

		@Override
		public String getAIMessage() {
			return "Hybrid";
		}

	}

	// Specific AI for first turn
	public static class FirstTurnAI extends AI {

		public static Factory myStartFactory;
		public static Factory opStartFactory;

		@Override
		public List<Action> compute(GameState gs) {

			List<Action> result = new ArrayList<>();

			myStartFactory = getStartFactory(me, gs);
			opStartFactory = getStartFactory(op, gs);

			// Then capture neutral stuff which can be captured
			List<Action> captureActions = getNeutralCaptureActions(gs);
			result.addAll(captureActions);

			List<Action> progressAction = new ProgressAI().compute(gs);
			result.addAll(progressAction);

			int bombTarget = getBombTarget(captureActions, -1, gs);
			if (bombTarget != -1) {
				result.add(Action.getBombAction(myStartFactory.id, bombTarget, gs));
				debug("Will bomb immediately " + bombTarget);
				int newBombTarget = getBombTarget(captureActions, bombTarget, gs);
				if (newBombTarget != -1) {
					result.add(Action.getBombAction(myStartFactory.id, newBombTarget, gs));
					debug("Will bomb immediately " + newBombTarget);
				}
			}

			return result;
		}

		private int getBombTarget(List<Action> minCaptureActions, int alreadyBombed, GameState gs) {
			int result = -1;
			int minBombDistance = 21;

			List<Factory> potentialTargets = new ArrayList<>();
			if (opStartFactory.prod == maxProd) {
				potentialTargets.add(opStartFactory);
			}

			for (Action action : minCaptureActions) {
				if (gs.factories[action.destination].prod == maxProd) {
					potentialTargets.add(gs.factories[getMirrorId(action.destination)]);
				}
			}

			if (alreadyBombed != -1) {
				potentialTargets.remove(gs.factories[alreadyBombed]);
			}

			debugFactoryList("Potential bomb targets", potentialTargets);

			for (Factory factory : potentialTargets) {
				int bombDistance = MatchConstants.factoryDirectDistances[myStartFactory.id][factory.id];
				int opDistance = MatchConstants.factoryShortestDistances[opStartFactory.id][factory.id];

				debug("bombDistance: " + bombDistance + " opDistance:" + opDistance);

				if (bombDistance >= opDistance && bombDistance < minBombDistance) {
					minBombDistance = bombDistance;
					result = factory.id;
				}

			}

			return result;
		}

		private List<Action> getNeutralCaptureActions(GameState gs) {

			List<Action> result = new ArrayList<>();

			// Get list of neutral producing factories which are closer from me than from the op
			List<Factory> neutralProducingFactories = new ArrayList<>();
			for (Factory factory : gs.factories) {
				if (factory.owner == neutral && factory.prod > 0
						&& MatchConstants.factoryDirectDistances[myStartFactory.id][factory.id] < MatchConstants.factoryDirectDistances[opStartFactory.id][factory.id]) {
					neutralProducingFactories.add(factory);
				}
			}

			neutralProducingFactories.sort(ProdThenDistanceComparator);
			Collections.reverse(neutralProducingFactories);
			debugFactoryList("Neutral prod factories sorted best to worse", neutralProducingFactories);

			for (Factory factory : neutralProducingFactories) {
				int neutrals = factory.cyborgCount;
				int prod = factory.prod;
				int myD = MatchConstants.factoryDirectDistances[myStartFactory.id][factory.id];
				int opD = MatchConstants.factoryDirectDistances[opStartFactory.id][factory.id];

				if (prod * (opD - myD) >= neutrals && myStartFactory.cyborgCount > neutrals) {
					result.add(Action.getMoveAction(myStartFactory.id, MatchConstants.factoryPath[myStartFactory.id][factory.id], neutrals + 1, gs));
				}

			}

			enrichCaptureActions(result, gs);
			debugActionsList("minCaptureActions after enrich", result);

			return result;
		}

		private void enrichCaptureActions(List<Action> minCaptureActions, GameState gs) {

			List<Action> actionsToEnrich = new ArrayList<>();

			for (Action action : minCaptureActions) {
				if (gs.factories[action.destination].closestOpFactoryDistance < myStartFactory.closestOpFactoryDistance) {
					actionsToEnrich.add(action);
				}
			}

			int totalActions = actionsToEnrich.size();
			if (totalActions != 0) {
				int remaingCyborgsToUse = myStartFactory.cyborgCount;
				int addCyborgs = remaingCyborgsToUse / totalActions;
				int supCyborgs = remaingCyborgsToUse % totalActions;

				for (Action action : actionsToEnrich) {
					action.cyborgCount += addCyborgs;
					if (supCyborgs > 0) {
						action.cyborgCount++;
						supCyborgs--;
					}
				}
			}

		}

		public static Comparator<Factory> ProdThenDistanceComparator = new Comparator<Player.Factory>() {

			@Override
			public int compare(Factory o1, Factory o2) {

				if (o1.id == o2.id) {
					return 0;
				}

				if (o1.prod > o2.prod) {
					return 1;
				} else if (o1.prod < o2.prod) {
					return -1;
				}

				if (MatchConstants.factoryDirectDistances[myStartFactory.id][o1.id] < MatchConstants.factoryDirectDistances[myStartFactory.id][o2.id]) {
					return 1;
				} else if (MatchConstants.factoryDirectDistances[myStartFactory.id][o1.id] > MatchConstants.factoryDirectDistances[myStartFactory.id][o2.id]) {
					return -1;
				}

				if (o1.id > o2.id) {
					return 1;
				}
				return -1;
			}

		};

		private Factory getStartFactory(int owner, GameState gs) {
			Factory result = null;

			for (Factory factory : gs.factories) {
				if (factory.owner == owner) {
					result = factory;
					break;
				}
			}

			return result;
		}

		@Override
		public String getAIMessage() {
			return "First turn";
		}

	}

	public static class Comp {

		// Factory comparators

		// Will sort from closest to farthest based on closestOpFactoryDistance
		public static final Comparator<Factory> opDistanceComparator = new Comparator<Player.Factory>() {

			@Override
			public int compare(Factory o1, Factory o2) {

				if (o1.closestOpFactoryDistance > o2.closestOpFactoryDistance) {
					return 1;
				} else if (o1.closestOpFactoryDistance < o2.closestOpFactoryDistance) {
					return -1;
				}

				if (o1.id > o2.id) {
					return 1;
				}
				return -1;
			}

		};

		// Will sort from closest to farthest based on closestMyFactoryDistance
		public static final Comparator<Factory> myDistanceComparator = new Comparator<Player.Factory>() {

			@Override
			public int compare(Factory o1, Factory o2) {

				if (o1.closestMyFactoryDistance > o2.closestMyFactoryDistance) {
					return 1;
				} else if (o1.closestMyFactoryDistance < o2.closestMyFactoryDistance) {
					return -1;
				}

				if (o1.id > o2.id) {
					return 1;
				}
				return -1;
			}

		};

		public static class MyDistanceComparator implements Comparator<Factory> {

			private Factory source;

			public MyDistanceComparator(Factory source) {
				super();
				this.source = source;
			}

			@Override
			public int compare(Factory o1, Factory o2) {
				if (MatchConstants.factoryDirectDistances[source.id][o1.id] > MatchConstants.factoryDirectDistances[source.id][o2.id]) {
					return 1;
				} else if (MatchConstants.factoryDirectDistances[source.id][o1.id] < MatchConstants.factoryDirectDistances[source.id][o2.id]) {
					return -1;
				}

				if (o1.id > o2.id) {
					return 1;
				}
				return -1;
			}

		}
	}

	public static class DefendAI extends AI {

		@Override
		public List<Action> compute(GameState gs) {

			return null; // Hint: this won't work :)
		}

		@Override
		public String getAIMessage() {
			return null;
		}

	}

	public static class ProgressAI extends AI {

		@Override
		public List<Action> compute(GameState gs) {

			List<Action> result = new ArrayList<>();

			List<Factory> myFactories = new ArrayList<>();
			for (Factory factory : gs.factories) {
				if (factory.owner == me && factory.cyborgCount > 0) {
					myFactories.add(factory);
				}
			}

			for (Factory factory : myFactories) {

				boolean onlyFriendlyAndNoProdNeigh = true;
				List<Factory> neighs = gs.getAllNeighs(factory);

				for (Factory neigh : neighs) {
					debug("Neigh " + neigh.id + " of " + factory.id);
					int sumArriving = getSumArriving(neigh);
					if (neigh.owner != me && neigh.topProd != 0 && neigh.cyborgCount >= sumArriving) {
						onlyFriendlyAndNoProdNeigh = false;
						debug("onlyFriendlyAndNoProdNeigh = false !");
						break;
					}
				}

				if (onlyFriendlyAndNoProdNeigh) {

					neighs.sort(Comp.opDistanceComparator);

					if (goForIncrease(factory, gs)) {
						if (factory.cyborgCount >= sacrificeForIncrease) {
							// Increase
							result.add(Action.getIncreaseAction(factory.id, gs));
							debug("Will increase " + factory.id);
						} else {
							// Keep them all for future increase
							factory.cyborgCount = 0;
						}
					} else {
						// We'll progress

						int bestDistance = 40;
						int bestProgressNeigh = -1;

						for (Factory neigh : neighs) {
							if (MatchConstants.factoryDirectDistances[factory.id][neigh.id] + neigh.closestOpFactoryDistance < bestDistance) {
								bestDistance = MatchConstants.factoryDirectDistances[factory.id][neigh.id] + neigh.closestOpFactoryDistance;
								bestProgressNeigh = neigh.id;
							}
						}

						if (bestProgressNeigh != -1) {
							// Send all
							result.add(Action.getMoveAction(factory.id, bestProgressNeigh, factory.cyborgCount, gs));
						}
					}

				}

			}

			return result;
		}

		private int getSumArriving(Factory neigh) {
			int sum = 0;
			for (Troop troop : neigh.myTroops) {
				sum += troop.cyborgCount;
			}
			return sum;
		}

		private boolean goForIncrease(Factory factory, GameState gs) {

			return (gs.round >= MatchConstants.maxDirectDistanceBetweenFactoriesForThisMatch + 2) && factory.topProd != 3;
		}

		@Override
		public String getAIMessage() {
			return null;
		}

	}

	public static class CaptureAI extends AI {

		@Override
		public List<Action> compute(GameState gs) {

			List<Action> result = new ArrayList<>();

			List<Factory> myFactories = new ArrayList<>();
			for (Factory factory : gs.factories) {
				if (factory.owner == me && factory.cyborgCount > 0) {
					myFactories.add(factory);
				}
			}

			List<Factory> allTargets = new ArrayList<>();
			List<Factory> neutralTargets = new ArrayList<>();
			List<Factory> opTargets = new ArrayList<>();

			for (Factory factory : myFactories) {
				for (Factory neigh : gs.getAllNeighs(factory)) {
					if (neigh.owner == op && neigh.topProd > 0 && neigh.nbTurnsBeforeProduction < MatchConstants.factoryDirectDistances[factory.id][neigh.id] && !bombConflict(factory, neigh)) {
						if (!allTargets.contains(neigh)) {
							allTargets.add(neigh);
						}
						if (!opTargets.contains(neigh)) {
							opTargets.add(neigh);
						}
					}
					if (neigh.owner == neutral && neigh.topProd > 0) {

						int sumGoing = 0;
						for (Troop troop : neigh.myTroops) {
							sumGoing += troop.cyborgCount;
						}

						if (sumGoing <= neigh.cyborgCount) {
							if (!allTargets.contains(neigh)) {
								allTargets.add(neigh);
							}
							if (!neutralTargets.contains(neigh)) {
								neutralTargets.add(neigh);
							}
						}

					}
				}
			}

			neutralTargets.sort(Comp.opDistanceComparator);

			for (Factory neutralTarget : neutralTargets) {

				List<Factory> myNeighs = gs.getNeighsForOwner(me, neutralTarget);
				myNeighs.sort(Comp.opDistanceComparator);
				Collections.reverse(myNeighs);

				for (Factory neigh : myNeighs) {
					if (neigh.cyborgCount > neutralTarget.cyborgCount) {
						// Send the minimum
						result.add(Action.getMoveAction(neigh.id, neutralTarget.id, neutralTarget.cyborgCount + 1, gs));
						neutralTarget.tryingToCapture = true;
						break;
					}
				}

			}

			opTargets.sort(Comp.myDistanceComparator);

			for (Factory opTarget : opTargets) {

				List<Factory> myNeighs = gs.getNeighsForOwner(me, opTarget);
				myNeighs.sort(Comp.myDistanceComparator);

				for (Factory neigh : myNeighs) {

					int maxOpCyborgsAtArrival = opTarget.cyborgCount + getOpProdAndArrivingTroopBy(opTarget, MatchConstants.factoryDirectDistances[neigh.id][opTarget.id] + 1);
					if (neigh.cyborgCount > maxOpCyborgsAtArrival || neigh.cyborgCount >= 40) {
						// Send all
						result.add(Action.getMoveAction(neigh.id, opTarget.id, neigh.cyborgCount, gs));
						opTarget.tryingToCapture = true;
						break;
					}
				}

			}

			return result;
		}

		private boolean bombConflict(Factory myFactory, Factory target) {
			boolean result = false;

			switch (target.bombsArriving.size()) {
			case 0:
				result = false; // No conflict
				break;
			case 1:
				result = MatchConstants.factoryDirectDistances[myFactory.id][target.id] < target.bombsArriving.get(0).turnsToArrive + factoryBombCoolDown;
				break;
			case 2:
				int maxTurnsToArrive = Math.max(target.bombsArriving.get(0).turnsToArrive, target.bombsArriving.get(1).turnsToArrive);
				result = MatchConstants.factoryDirectDistances[myFactory.id][target.id] < maxTurnsToArrive + factoryBombCoolDown;
				break;
			default:
				break;
			}

			return result;
		}

		private static int getOpProdAndArrivingTroopBy(Factory factory, int turnsToArrive) {
			int sum = Math.max(0, turnsToArrive - factory.nbTurnsBeforeProduction) * factory.topProd;

			for (Troop troop : factory.opTroops) {
				if (troop.turnsToArrive <= turnsToArrive) {
					sum += troop.cyborgCount;
				}
			}

			return sum;
		}

		@Override
		public String getAIMessage() {
			return null;
		}

	}

	public static class BombAI extends AI {

		@Override
		public List<Action> compute(GameState gs) {

			List<Action> result = new ArrayList<>();

			if (gs.myRemainingBombs > 0) {

				List<Factory> targets = new ArrayList<>();

				for (Factory factory : gs.factories) {
					if (factory.owner == op && !factory.tryingToCapture && factory.topProd == maxProd) {
						targets.add(factory);
					}
				}

				targets.sort(Comp.myDistanceComparator);
				debugFactoryList("Bomb targets", targets);

				Factory bestLauncher = null;
				Factory bestTarget = null;
				int bestArrival = 30;

				for (Factory target : targets) {

					List<Factory> myFactories = gs.getPresentFactories(me);
					myFactories.sort(new Comp.MyDistanceComparator(target));

					int arrival = 0;

					if (target.bombsArriving.isEmpty()) {
						arrival = MatchConstants.factoryDirectDistances[myFactories.get(0).id][target.id] + 1;
					} else {
						arrival = MatchConstants.factoryDirectDistances[myFactories.get(0).id][target.id] + factoryBombCoolDown
								- Math.min(factoryBombCoolDown, MatchConstants.factoryDirectDistances[myFactories.get(0).id][target.id] - target.bombsArriving.get(0).turnsToArrive);
					}

					if (arrival < bestArrival) {
						bestArrival = arrival;
						bestLauncher = myFactories.get(0);
						bestTarget = target;
					}

				}

				if (bestTarget != null && bestLauncher != null) {
					debug("Best bomb target: " + bestTarget.id + " from " + bestLauncher.id + " bestArrival: " + bestArrival + " d+1: "
							+ (MatchConstants.factoryDirectDistances[bestLauncher.id][bestTarget.id] + 1));
				}

				if (bestLauncher != null && bestTarget != null && bestArrival == MatchConstants.factoryDirectDistances[bestLauncher.id][bestTarget.id] + 1
						&& bestTarget.nbTurnsBeforeProduction <= bestArrival) {
					// Launch it
					result.add(Action.getBombAction(bestLauncher.id, bestTarget.id, gs));
				}
			}

			return result;
		}

		@Override
		public String getAIMessage() {
			return null;
		}

	}

}