original.java

import static java.lang.Math.abs;
import static java.lang.Math.round;
import static java.lang.Math.signum;
import static java.lang.Math.sqrt;

import java.io.ByteArrayInputStream;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;

/**
 * Grab Snaffles and try to throw them through the opponent's goal! Move towards
 * a Snaffle and use your team id to determine where you need to throw it.
 **/
class Player {

	static GameState expectedGameState = new GameState();
	static GameState gameState = new GameState();

	static long turnStart;

	// static AI ai = new BasicAI();
	// static AI ai = new MoveOnlyAI();
	// static AI ai = new GeneticAI();
	static AI ai = new MCAI();
	static boolean firstTurnDone = false;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);

		// if 0 you need to score on the right of the map, if 1 you need to
		// score on the left
		int myTeamId = captureScannerInput(in);
		gameState.myTeamId = myTeamId;
		Cache.initEntities();
		// System.err.println("Game netities init done");

		// game loop
		while (true) {
			Cache.newTurn();
			long start = System.currentTimeMillis();
			turnStart = start;
			gameState.clear();
			initGameState(gameState, in);
			// System.err.println("GameState init done after " +
			// (System.currentTimeMillis() - start));
			// System.err.println("Game state init " + gameState);
			// System.err.println("Expected game state " + expectedGameState);
			// System.err.println("Expected game state " +
			// expectedGameState.myWizards);

			// Validate scanner
			// String scannerInputCopy = scannerInput;
			// Scanner scannerTest = new Scanner(new ByteArrayInputStream(
			// scannerInputCopy.getBytes(StandardCharsets.UTF_8)));
			// initGameState(gameState, scannerTest);
			// System.err.println(scannerInput);

			// Don't compare the first turn
			// start = System.currentTimeMillis();
			if (expectedGameState.myWizards.length != 0 && expectedGameState.myWizards[0] != null) {
				// System.err.println("Asserting");
				// GameState.assertEquals(gameState, expectedGameState);
				// System.err.println("Asserted everything went well");
				gameState.copyTransientValuesFrom(expectedGameState);
			}
			expectedGameState.clear();
			gameState.updateCounters();
			// System.err.println("Carry over from last after " +
			// (System.currentTimeMillis() - start));
			// System.err.println("Game state after init: " + gameState);

			// System.err.println("Computing actions " + gameState);
			// start = System.currentTimeMillis();
			Action[] actions = ai.computeActions(gameState);
			// System.err.println("Output gamestate after AI actions: " +
			// gameState);
			// System.err.println("Computing actions after " +
			// (System.currentTimeMillis() - start));

			Action[] opponentActions = null;
			// System.err.println(
			// "actions computed " + Arrays.toString(actions) + " after " +
			// (System.currentTimeMillis() - start));

			// for (Action action : actions) {
			// if (action.x < 0 || action.y < 0) {
			// System.err.println("Negative action before simulating next state
			// " + action);
			// throw new RuntimeException();
			// }
			// }

			expectedGameState.cloneFrom(gameState);
			GameEngine.simulateNextTurn(gameState, expectedGameState, actions, opponentActions);

			// System.err.println(expectedGameState.exportState());
			// System.err.println(expectedGameState);
			// System.err.println("Simulation done after " +
			// (System.currentTimeMillis() - start));
			// System.err.println(expectedGameState);

			System.err.println(Arrays.toString(expectedGameState.myWizards));
			for (Action action : actions) {
				// if (action.x < 0 || action.y < 0) {
				// System.err.println("Negative action before sending it " +
				// action);
				// throw new RuntimeException();
				// }
				// System.err.println(action.execute());
				System.out.println(action.execute());
			}
			firstTurnDone = true;
			Cache.endTurn();
		}
	}

	static void initGameState(GameState gameState, Scanner in) {
		initScanner();
		int entities = captureScannerInput(in); // number of entities still in
												// game
		gameState.setEntities(entities);
		for (int i = 0; i < entities; i++) {
			int entityId = captureScannerInput(in); // entity identifier
			Entity entity = null;
			String entityType = captureScannerStringInput(in);
			switch (entityType) {
			case "WIZARD":
				entity = gameState.getWizard(entityId);
				((Wizard) entity).friendly = true;
				break;
			case "OPPONENT_WIZARD":
				entity = gameState.getOpponentWizard(entityId);
				break;
			case "SNAFFLE":
				entity = gameState.getSnaffle(entityId);
				break;
			case "BLUDGER":
				entity = gameState.getBludger(entityId);
				break;
			default:
				break;
			}
			entity.entityId = entityId;

			entity.x = captureScannerInput(in); // position
			entity.y = captureScannerInput(in); // position
			entity.vx = captureScannerInput(in); // velocity
			entity.vy = captureScannerInput(in); // velocity
			// System.err.println("Init entity: " + entity);

			int state = captureScannerInput(in);
			if (entity instanceof Wizard) {
				// 1 if the wizard is holding a Snaffle, 0 otherwise
				((Wizard) entity).isHolding = state == 1;
				// System.err.println("Is holding? " + state + " " + entity);
			}
		}
		gameState.finalizeInit();
		// System.err.println("Input init");
		System.err.println(scannerInput);
	}

	static String scannerInput = "";

	private static void initScanner() {
		scannerInput = "";
	}

	private static String captureScannerStringInput(Scanner in) {
		String next = in.next();
		scannerInput += next + " ";
		return next;
	}

	private static int captureScannerInput(Scanner in) {
		int nextInt = in.nextInt();
		scannerInput += nextInt + " ";
		return nextInt;
	}

}

// =================================
// State
// =================================
class Cache {
	static int POINT_POOL_SIZE = 500000;
	static int ACTION_POOL_SIZE = 200000;
	static int WIZARD_POOL_SIZE = 200000;
	static int SNAFFLE_POOL_SIZE = 100000;
	static int BLUDGER_POOL_SIZE = 20000;
	static int MAP_POINT_POOL_SIZE = 100000;
	static int GAME_STATE_POOL_SIZE = 100000;

	static final Wizard[] wizardPool = new Wizard[WIZARD_POOL_SIZE];
	static final Snaffle[] snafflePool = new Snaffle[SNAFFLE_POOL_SIZE];
	static final Bludger[] bludgerPool = new Bludger[BLUDGER_POOL_SIZE];

	static final Point[] pointPool = new Point[POINT_POOL_SIZE];
	static final GameState[] gameStatePool = new GameState[GAME_STATE_POOL_SIZE];
	static final Action[] actionPool = new Action[ACTION_POOL_SIZE];
	static final MapPoint[] mapPointPool = new MapPoint[MAP_POINT_POOL_SIZE];

	static int wizardIndex, snaffleIndex, bludgerIndex, pointIndex, gameStateIndex, actionIndex, mapPointIndex;
	static int totalGameStateLoops, totalActionLoops, totalPointLoops, totalWizardLoops, totalSnaffleLoops,
			totalBludgerLoops, totalMapPointsLoops;

	static int gameStateClones, collisions, collisionTest, evals;

	static long lastCollision, totalCollisionTime, lastEval, totalEvalTime;

	static void initEntities() {
		for (int i = 0; i < WIZARD_POOL_SIZE; i++) {
			wizardPool[i] = new Wizard();
		}
		for (int i = 0; i < SNAFFLE_POOL_SIZE; i++) {
			snafflePool[i] = new Snaffle();
		}
		for (int i = 0; i < BLUDGER_POOL_SIZE; i++) {
			bludgerPool[i] = new Bludger();
		}
		for (int i = 0; i < POINT_POOL_SIZE; i++) {
			pointPool[i] = new Point();
		}
		for (int i = 0; i < GAME_STATE_POOL_SIZE; i++) {
			gameStatePool[i] = new GameState();
		}
		for (int i = 0; i < ACTION_POOL_SIZE; i++) {
			actionPool[i] = new Action();
		}
		for (int i = 0; i < MAP_POINT_POOL_SIZE; i++) {
			mapPointPool[i] = new MapPoint();
		}
	}

	public static void newTurn() {
		gameStateIndex = 0;
		totalGameStateLoops = 0;
		actionIndex = 0;
		totalActionLoops = 0;
		pointIndex = 0;
		totalPointLoops = 0;
		wizardIndex = 0;
		totalWizardLoops = 0;
		snaffleIndex = 0;
		totalSnaffleLoops = 0;
		bludgerIndex = 0;
		totalBludgerLoops = 0;
		mapPointIndex = 0;
		totalMapPointsLoops = 0;

		gameStateClones = 0;
		collisions = 0;
		collisionTest = 0;
		lastCollision = 0;
		totalCollisionTime = 0;
		lastEval = 0;
		totalEvalTime = 0;
	}

	public static void endTurn() {
		// System.err.println("Used " + (gameStateIndex + 10000 *
		// totalGameStateLoops) + " game states");
		// System.err.println("Used " + (actionIndex + ACTION_POOL_SIZE *
		// totalActionLoops) + " actions");
		// System.err.println("Used " + (pointIndex + POINT_POOL_SIZE *
		// totalPointLoops) + " points");
		// System.err.println("Used " + (wizardIndex + WIZARD_POOL_SIZE *
		// totalWizardLoops) + " wizards");
		// System.err.println("Used " + (snaffleIndex + SNAFFLE_POOL_SIZE *
		// totalSnaffleLoops) + " snaffles");
		// System.err.println("Used " + (bludgerIndex + BLUDGER_POOL_SIZE *
		// totalBludgerLoops) + " bludgers");
		// System.err.println("Used " + (mapPointIndex + MAP_POINT_POOL_SIZE *
		// totalMapPointsLoops) + " map points");

		// System.err.println("Cloned " + gameStateClones + " gamestates");

		// System.err.println("Had " + collisions + " collisions");
		// System.err.println("Tested for " + collisionTest + " collision
		// tests");
		// System.err.println("Spend " + totalCollisionTime / 1000000 + "ms
		// testing for collisions");
		// System.err.println(
		// "\tWhich is " + 1.0 * totalCollisionTime / 1000 / collisionTest + "
		// microseconds per collision test");
		//
		// System.err.println("Evaluated " + evals + " game states");
		// System.err.println("Spend " + totalEvalTime / 1000000 + "ms
		// evaluating game states");
		// System.err.println("\tWhich is " + 1.0 * totalEvalTime / 1000 / evals
		// + " microseconds per eval");
	}

	// TODO: remova the monitoring elements, as it takes some computing time
	static Wizard newWizard() {
		return new Wizard();
		// wizardIndex++;
		// if (wizardIndex >= WIZARD_POOL_SIZE) {
		// wizardIndex = wizardIndex - WIZARD_POOL_SIZE;
		// // totalWizardLoops++;
		// }
		// return wizardPool[wizardIndex].clear();
	}

	static Snaffle newSnaffle() {
		return new Snaffle();
		// snaffleIndex++;
		// if (snaffleIndex >= SNAFFLE_POOL_SIZE) {
		// snaffleIndex = snaffleIndex - SNAFFLE_POOL_SIZE;
		// // totalSnaffleLoops++;
		// }
		// return snafflePool[snaffleIndex].clear();
	}

	static Bludger newBludger() {
		return new Bludger();
		// return bludgerPool[bludgerIndex++ % 1000].clear();
		// bludgerIndex++;
		// if (bludgerIndex >= BLUDGER_POOL_SIZE) {
		// bludgerIndex = bludgerIndex - BLUDGER_POOL_SIZE;
		// // totalBludgerLoops++;
		// }
		// return bludgerPool[bludgerIndex].clear();
	}

	static Point newPoint() {
		return new Point();
		// return pointPool[pointIndex++ % 10000].clear();
		// pointIndex++;
		// if (pointIndex >= POINT_POOL_SIZE) {
		// pointIndex = pointIndex - POINT_POOL_SIZE;
		// // Rmoving monitoring counters goes down from 21 ms to 14 ms to
		// // instantiate 5M points
		// // totalPointLoops++;
		// }
		//
		// // Not calling .clear() means getting from 39 to 21 ms to instantiate
		// 5M
		// // points
		// return pointPool[pointIndex];
	}

	static GameState newGameState() {
		return new GameState();
		// 93ms to get 1M game states
		// gameStateIndex++;
		// if (gameStateIndex >= GAME_STATE_POOL_SIZE) {
		// gameStateIndex = gameStateIndex - GAME_STATE_POOL_SIZE;
		// // totalGameStateLoops++;
		// }
		// // We only need to clear the snaffles, as they are the only entities
		// // that can disappear. Down to 63 ms for 1M states
		// return gameStatePool[gameStateIndex].clear();
	}

	static Action newAction() {
		return new Action();
		// actionIndex++;
		// if (actionIndex >= ACTION_POOL_SIZE) {
		// actionIndex = actionIndex - ACTION_POOL_SIZE;
		// // totalActionLoops++;
		// }
		// return actionPool[actionIndex].clear();
	}

	public static Solution newSolution() {
		return new Solution();
	}

	public static Step newStep() {
		return new Step();
	}

	public static MapPoint newMapPoint() {
		return new MapPoint();
		// mapPointIndex++;
		// if (mapPointIndex >= MAP_POINT_POOL_SIZE) {
		// mapPointIndex = mapPointIndex - MAP_POINT_POOL_SIZE;
		// // totalMapPointsLoops++;
		// }
		// // We only need to clear the snaffles, as they are the only entities
		// // that can disappear. Down to 63 ms for 1M states
		// return mapPointPool[mapPointIndex];
	}

	// public static void logClone() {
	// gameStateClones++;
	// }
	//
	// public static void logCollision() {
	// collisions++;
	// }
	//
	// public static void logCollisionTest() {
	// collisionTest++;
	// lastCollision = System.nanoTime();
	// }
	//
	// public static void logCollisionEnd() {
	// totalCollisionTime += System.nanoTime() - lastCollision;
	// }
	//
	// public static void logEval() {
	// evals++;
	// lastEval = System.nanoTime();
	// }
	//
	// public static void logEvalEnd() {
	// totalEvalTime += System.nanoTime() - lastEval;
	// }
}

class GameState {

	int initialTotalEntities = -1;
	int myTeamId;
	Wizard[] myWizards = new Wizard[2];
	Wizard[] opponentWizards = new Wizard[2];
	Snaffle[] snaffles = new Snaffle[7];
	Bludger[] bludgers = new Bludger[2];
	Pole[] poles = new Pole[4];

	int myMagic, opponentMagic;
	int myScore, opponentScore;

	boolean invalid;

	GameState clear() {
		// myWizards = new Wizard[2];
		// opponentWizards = new Wizard[2];
		for (int i = 0; i < 7; i++) {
			snaffles[i] = null;
		}
		for (int i = 0; i < 4; i++) {
			Pole pole = new Pole();
			pole.entityId = -10;
			pole.x = (i == 0 || i == 1) ? 0 : 16000;
			pole.y = (i == 0 || i == 2) ? 1750 : 5750;
			poles[i] = pole;
		}
		// snaffles = new Snaffle[7];
		// bludgers = new Bludger[2];
		// myMagic = 0;
		// opponentMagic = 0;
		// myScore = 0;
		// opponentScore = 0;
		return this;
	}

	public void setEntities(int entities) {
		if (initialTotalEntities == -1) {
			initialTotalEntities = entities;
		}
	}

	public void finalizeInit() {
		for (int i = 0; i < 2; i++) {
			if (myWizards[i].isHolding) {
				for (Snaffle snaffle : snaffles) {
					if (snaffle == null) continue;
					if (snaffle.x == myWizards[i].x && snaffle.y == myWizards[i].y) {
						snaffle.grabbedBy = myWizards[i].entityId;
						break;
					}
				}
			}
		}

		for (int i = 0; i < 2; i++) {
			if (opponentWizards[i].isHolding) {
				for (Snaffle snaffle : snaffles) {
					if (snaffle == null) continue;
					if (snaffle.x == opponentWizards[i].x && snaffle.y == opponentWizards[i].y) {
						snaffle.grabbedBy = opponentWizards[i].entityId;
						break;
					}
				}
			}
		}

	}

	public String exportState() {
		String result = "";
		int entities = 0;
		for (int i = 0; i < 2; i++) {
			result += myWizards[i].entityId + " WIZARD " + myWizards[i].x + " " + myWizards[i].y + " "
					+ myWizards[i].vx + " " + myWizards[i].vy + " " + (myWizards[i].isHolding ? 1 : 0) + " ";
			entities++;
		}
		for (int i = 0; i < 2; i++) {
			result += opponentWizards[i].entityId + " OPPONENT_WIZARD " + opponentWizards[i].x + " "
					+ opponentWizards[i].y + " " + opponentWizards[i].vx + " " + opponentWizards[i].vy + " "
					+ (opponentWizards[i].isHolding ? 1 : 0) + " ";
			entities++;
		}
		for (int i = 0; i < 7; i++) {
			if (snaffles[i] != null) {
				result += snaffles[i].entityId + " SNAFFLE " + snaffles[i].x + " " + snaffles[i].y + " "
						+ snaffles[i].vx + " " + snaffles[i].vy + " ";
				entities++;
			}
		}
		for (int i = 0; i < 2; i++) {
			result += bludgers[i].entityId + " SNAFFLE " + bludgers[i].x + " " + bludgers[i].y + " " + bludgers[i].vx
					+ " " + bludgers[i].vy + " ";
			entities++;
		}
		result = entities + " " + result;
		return result;
	}

	GameState fullClear() {
		for (int i = 0; i < 2; i++) {
			myWizards[i] = null;
		}
		for (int i = 0; i < 2; i++) {
			opponentWizards[i] = null;
		}
		for (int i = 0; i < 7; i++) {
			snaffles[i] = null;
		}
		for (int i = 0; i < 2; i++) {
			bludgers[i] = null;
		}
		myMagic = 0;
		opponentMagic = 0;
		myScore = 0;
		opponentScore = 0;
		return this;
	}

	public void updateCounters() {
		for (int i = 0; i < myWizards.length; i++) {
			myWizards[i].countdownBeforeNextHold--;
		}
		for (int i = 0; i < opponentWizards.length; i++) {
			opponentWizards[i].countdownBeforeNextHold--;
		}
	}

	public void copyTransientValuesFrom(GameState expectedGameState) {
		for (int i = 0; i < bludgers.length; i++) {
			bludgers[i].lastCollidedWizard = expectedGameState.bludgers[i].lastCollidedWizard;
		}
		for (int i = 0; i < myWizards.length; i++) {
			myWizards[i].countdownBeforeNextHold = expectedGameState.myWizards[i].countdownBeforeNextHold;
		}
		for (int i = 0; i < opponentWizards.length; i++) {
			opponentWizards[i].countdownBeforeNextHold = expectedGameState.opponentWizards[i].countdownBeforeNextHold;
		}
		// for (int i = 0; i < snaffles.length; i++) {
		// if (snaffles[i] == null || expectedGameState.snaffles[i] == null) {
		// continue;
		// }
		// snaffles[i].grabbedBy = expectedGameState.snaffles[i].grabbedBy;
		// }
		myMagic = expectedGameState.myMagic;
		opponentMagic = expectedGameState.opponentMagic;
		myScore = expectedGameState.myScore;
		opponentScore = expectedGameState.opponentScore;
	}

	public Entity findEntity(int id) {
		for (int i = 0; i < 2; i++) {
			if (myWizards[i].entityId == id) return myWizards[i];
		}
		for (int i = 0; i < 2; i++) {
			if (opponentWizards[i].entityId == id) return opponentWizards[i];
		}
		for (int i = 0; i < 7; i++) {
			if (snaffles[i] == null) continue;
			if (snaffles[i].entityId == id) return snaffles[i];
		}
		for (int i = 0; i < 2; i++) {
			if (bludgers[i].entityId == id) return bludgers[i];
		}
		return null;
	}

	public Wizard getWizard(int entityId) {
		Wizard wizard = Cache.newWizard();
		for (int i = 0; i < 2; i++) {
			if (myWizards[i] == null) {
				myWizards[i] = wizard;
				break;
			}
		}
		return wizard;
	}

	public Wizard getOpponentWizard(int entityId) {
		Wizard wizard = Cache.newWizard();
		for (int i = 0; i < 2; i++) {
			if (opponentWizards[i] == null) {
				opponentWizards[i] = wizard;
				break;
			}
		}
		return wizard;
	}

	public Snaffle getSnaffle(int entityId) {
		Snaffle snaffle = Cache.newSnaffle();
		for (int i = 0; i < snaffles.length; i++) {
			if (snaffles[i] == null) {
				snaffles[i] = snaffle;
				break;
			}
		}
		return snaffle;
	}

	public Bludger getBludger(int entityId) {
		Bludger bludger = Cache.newBludger();
		for (int i = 0; i < 2; i++) {
			if (bludgers[i] == null) {
				bludgers[i] = bludger;
				break;
			}
		}
		return bludger;
	}

	public static void assertEquals(GameState gameState, GameState expectedGameState) {
		if (!Arrays.equals(gameState.myWizards, expectedGameState.myWizards)) {
			System.err.println("Wizards (actual/simulated): " + Arrays.toString(gameState.myWizards) + " // "
					+ Arrays.toString(expectedGameState.myWizards));
			throw new AssertionError();
		}
		if (!Arrays.equals(gameState.opponentWizards, expectedGameState.opponentWizards)) {
			System.err.println("Opponent Wizards (actual/simulated): " + Arrays.toString(gameState.opponentWizards)
					+ " // " + Arrays.toString(expectedGameState.opponentWizards));
			throw new AssertionError();
		}
		if (!Arrays.equals(gameState.bludgers, expectedGameState.bludgers)) {
			System.err.println("Bludgers (actual/simulated): " + Arrays.toString(gameState.bludgers) + " // "
					+ Arrays.toString(expectedGameState.bludgers));
			throw new AssertionError();
		}
		if (!Arrays.equals(gameState.snaffles, expectedGameState.snaffles)) {
			System.err.println("Snaffles (actual/simulated): " + Arrays.toString(gameState.snaffles) + " // "
					+ Arrays.toString(expectedGameState.snaffles));
			throw new AssertionError();
		}
	}

	// 221 ms to clone 1M game states
	public void cloneFrom(GameState gameState) {
		// Cache.logClone();

		clear();
		myTeamId = gameState.myTeamId;
		for (int i = 0; i < 2; i++) {
			myWizards[i] = gameState.myWizards[i].clone();
		}
		for (int i = 0; i < 2; i++) {
			opponentWizards[i] = gameState.opponentWizards[i].clone();
		}
		for (int i = 0; i < 2; i++) {
			bludgers[i] = gameState.bludgers[i].clone();
		}
		for (int i = 0; i < gameState.snaffles.length; i++) {
			if (gameState.snaffles[i] == null) {
				continue;
			}
			snaffles[i] = gameState.snaffles[i].clone();
		}
		myScore = gameState.myScore;
		opponentScore = gameState.opponentScore;
		myMagic = gameState.myMagic;
		opponentMagic = gameState.opponentMagic;
	}

	public void remove(Snaffle item) {
		for (int i = 0; i < snaffles.length; i++) {
			if (snaffles[i] == null) {
				continue;
			}
			if (snaffles[i].entityId == item.entityId) {
				snaffles[i] = null;
			}
		}
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.hashCode(bludgers);
		result = prime * result + (invalid ? 1231 : 1237);
		result = prime * result + myMagic;
		result = prime * result + myScore;
		result = prime * result + myTeamId;
		result = prime * result + Arrays.hashCode(myWizards);
		result = prime * result + opponentMagic;
		result = prime * result + opponentScore;
		result = prime * result + Arrays.hashCode(opponentWizards);
		result = prime * result + Arrays.hashCode(snaffles);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) return true;
		if (obj == null) return false;
		if (getClass() != obj.getClass()) return false;
		GameState other = (GameState) obj;
		if (!Arrays.equals(bludgers, other.bludgers)) return false;
		if (invalid != other.invalid) return false;
		if (myMagic != other.myMagic) return false;
		if (myScore != other.myScore) return false;
		if (myTeamId != other.myTeamId) return false;
		if (!Arrays.equals(myWizards, other.myWizards)) return false;
		if (opponentMagic != other.opponentMagic) return false;
		if (opponentScore != other.opponentScore) return false;
		if (!Arrays.equals(opponentWizards, other.opponentWizards)) return false;
		if (!Arrays.equals(snaffles, other.snaffles)) return false;
		return true;
	}

	@Override
	public String toString() {
		return "GameState [myTeamId=" + myTeamId + ", myWizards=" + Arrays.toString(myWizards) + ", opponentWizards="
				+ Arrays.toString(opponentWizards) + ", snaffles=" + Arrays.toString(snaffles) + ", bludgers="
				+ Arrays.toString(bludgers) + ", myMagic=" + myMagic + ", opponentMagic=" + opponentMagic
				+ ", myScore=" + myScore + ", opponentScore=" + opponentScore + ", invalid=" + invalid + "]";
	}

}

class Action {

	String type;
	float x, y;
	int power;
	// String debug;
	public String debug;

	public Action() {
	}

	public Action clear() {
		type = null;
		x = 0;
		y = 0;
		power = 0;
		return this;
	}

	public Action(String type, float x, float y, int power) {
		super();
		this.type = type;
		this.x = x;
		this.y = y;
		this.power = power;
	}

	public String execute() {
		return type + " " + Utils.roundAwayFromZero(x) + " " + Utils.roundAwayFromZero(y) + " " + power;
	}

	public static Action buildMove(Point position, int power) {
		Action action = Cache.newAction();
		action.type = "MOVE";
		action.x = position.x;
		action.y = position.y;
		action.power = power;
		return action;
	}

	public static Action buildThrow(Point opponentGoal, int power) {
		Action action = Cache.newAction();
		action.type = "THROW";
		action.x = opponentGoal.x;
		action.y = opponentGoal.y;
		action.power = power;
		return action;
	}

	@Override
	public Action clone() {
		Action clone = Cache.newAction();
		clone.type = type;
		clone.x = x;
		clone.y = y;
		clone.power = power;
		return clone;
	}

	@Override
	public String toString() {
		return "Action [type=" + type + ", x=" + x + ", y=" + y + ", power=" + power + ", debug=" + debug + "]";
	}

}

// =================================
// Entities
// =================================
class Point {
	protected float x, y;

	public Point() {
		super();
	}

	public Point(float x, float y) {
		super();
		this.x = x;
		this.y = y;
	}

	public Point clear() {
		x = 0;
		y = 0;
		return this;
	}

	public float distance2(Point target) {
		return (x - target.x) * (x - target.x) + (y - target.y) * (y - target.y);
	}

	float distance(Point p) {
		return (float) Math.sqrt(distance2(p));
	}

	Point closest(Point a, Point b) {
		float da = b.y - a.y;
		float db = a.x - b.x;
		float c1 = da * a.x + db * a.y;
		float c2 = -db * x + da * y;
		float det = da * da + db * db;

		Point point = Cache.newPoint();
		if (det != 0) {
			point.x = (da * c1 - db * c2) / det;
			point.y = (da * c2 + db * c1) / det;
		}
		else {
			// Le point est déjà sur la droite
			point.x = x;
			point.y = y;
		}

		return point;
	}

	@Override
	public Point clone() {
		Point clone = Cache.newPoint();
		clone.x = x;
		clone.y = y;
		return clone;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Float.floatToIntBits(x);
		result = prime * result + Float.floatToIntBits(y);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) { return true; }
		if (obj == null) { return false; }
		if (getClass() != obj.getClass()) { return false; }
		Point other = (Point) obj;
		if (Float.floatToIntBits(x) != Float.floatToIntBits(other.x)) { return false; }
		if (Float.floatToIntBits(y) != Float.floatToIntBits(other.y)) { return false; }
		return true;
	}

	@Override
	public String toString() {
		return "Point [x=" + x + ", y=" + y + "]";
	}
}

abstract class Entity extends Point {

	protected int entityId;
	protected float vx, vy;

	protected final float friction, mass, radius;
	private String debug;

	// String debug;

	public Entity(float friction, float mass, float radius) {
		super();
		this.friction = friction;
		this.mass = mass;
		this.radius = radius;
	}

	@Override
	public Entity clear() {
		super.clear();
		entityId = -1;
		vx = 0;
		vy = 0;
		// debug = null;
		return this;
	}

	void applyNewSpeed(Point p, float thrust) {
		applyNewSpeed(p.x, p.y, thrust);
	}

	public void applyNewSpeed(float px, float py, float thrust) {
		float vectX = px - x;
		float vectY = py - y;

		float norm = (float) Math.sqrt(vectX * vectX + vectY * vectY);
		float normVectX = vectX / norm;
		float normVectY = vectY / norm;
		// System.err.println("Applying new speed " + normVectX * thrust + " " +
		// normVectY * thrust);

		vx += normVectX * thrust / mass;
		vy += normVectY * thrust / mass;
	}

	void move(float t) {
		x += vx * t;
		y += vy * t;
	}

	void end() {
		x = Utils.roundAwayFromZero(x);
		y = Utils.roundAwayFromZero(y);
		vx = Utils.roundAwayFromZero(vx * friction);
		vy = Utils.roundAwayFromZero(vy * friction);
	}

	// void play(Point p, int thrust) {
	// applyNewSpeed(p, thrust);
	// // this.rotate(p);
	// // this.boost(thrust);
	// move(1.0f);
	// end();
	// }

	Collision collision(Entity u) {
		// Cache.logCollisionTest();
		float dist = distance2(u);

		// Somme des rayons au carré
		float sr = (radius + u.radius) * (radius + u.radius);

		// Wizard and Snaffles don't collide when the Wizard doesn't hold a
		// Snaffle
		if (this instanceof Wizard && u instanceof Snaffle) {
			if (!((Wizard) this).isHolding && ((Snaffle) u).grabbedBy == -1) {
				sr = (radius - 1) * (radius - 1);
			}
			else {
				return null;
			}
		}
		if (u instanceof Wizard && this instanceof Snaffle) {
			if (!((Wizard) u).isHolding && ((Snaffle) this).grabbedBy == -1) {
				sr = (u.radius - 1) * (u.radius - 1);
			}
			else {
				return null;
			}
		}

		// On prend tout au carré pour éviter d'avoir à appeler un sqrt
		// inutilement. C'est mieux pour les performances
		if (dist < sr) {
			// Les objets sont déjà l'un sur l'autre. On a donc une collision
			// immédiate
			// Cache.logCollisionEnd();
			return new Collision(this, u, 0.0f);
		}

		// Optimisation. Les objets ont la même vitesse ils ne pourront jamais
		// se rentrer dedans
		if (vx == u.vx && vy == u.vy) {
			// Cache.logCollisionEnd();
			return null;
		}

		// On se met dans le référentiel de u. u est donc immobile et se trouve
		// sur le point (0,0) après ça
		// Our coordinates in u's referential
		float x = this.x - u.x;
		float y = this.y - u.y;
		Point myp = Cache.newPoint();
		myp.x = x;
		myp.y = y;

		// Our speed in u's referential
		float vx = this.vx - u.vx;
		float vy = this.vy - u.vy;

		// u's coordinates in its own ref
		Point up = Cache.newPoint();
		up.x = 0;
		up.y = 0;

		// On cherche le point le plus proche de u (qui est donc en (0,0)) sur
		// la droite décrite par notre vecteur de vitesse
		Point point = Cache.newPoint();
		point.x = x + vx;
		point.y = y + vy;
		Point p = up.closest(myp, point);

		// Distance au carré entre u et le point le plus proche sur la droite
		// décrite par notre vecteur de vitesse
		float pdist = up.distance2(p);

		// Distance au carré entre nous et ce point
		float mypdist = myp.distance2(p);

		// Si la distance entre u et cette droite est inférieur à la somme des
		// rayons, alors il y a possibilité de collision
		Collision result = null;
		if (pdist < sr) {
			// Our speed - we move along that droite
			float length = (float) sqrt(vx * vx + vy * vy);

			// On déplace le point sur la droite pour trouver le point d'impact
			// C'est l'autre côté du triangle rectangle formé par l'hypothénuse
			// sr et pdist. Il représente la distance entre le point le plus
			// proche de la droite (p) et le point où se produira effectivement
			// l'impact
			float backdist = (float) sqrt(sr - pdist);

			// On recalcule la position du point où se passe effectivement
			// l'impact
			p.x = p.x - backdist * (vx / length);
			p.y = p.y - backdist * (vy / length);

			// Si le point s'est éloigné de nous par rapport à avant, c'est que
			// notre vitesse ne va pas dans le bon sens
			if (myp.distance2(p) > mypdist) {
				// Cache.logCollisionEnd();
				return null;
			}

			pdist = p.distance(myp);

			// Le point d'impact est plus loin que ce qu'on peut parcourir en un
			// seul tour
			if (pdist > length) {
				// Cache.logCollisionEnd();
				return null;
			}

			// Temps nécessaire pour atteindre le point d'impact
			float t = pdist / length;

			result = new Collision(this, u, t);
			// System.err.println("Returing new collision between " + this + "
			// and " + u + ": " + collision);
		}

		// Cache.logCollisionEnd();
		return result;
	}

	public Collision edgeCollision() {
		Entity u = getClosestEdgePoint();
		// System.err.println("Closest edge for " + this + " is " + u);
		return collision(u);
	}

	private MapPoint getClosestEdgePoint() {
		float closestX, closestY;
		if (y < 7500 - y) {
			closestY = 0;
		}
		else {
			closestY = 7500;
		}

		if (x < 16000 - x) {
			closestX = 0;
		}
		else {
			closestX = 16000;
		}

		MapPoint point = Cache.newMapPoint();
		point.entityId = -2;
		if (closestX <= closestY) {
			point.x = x;
			point.y = closestY;
			point.vx = vx;
			point.vy = 0;
		}
		else {
			point.x = closestX;
			point.y = y;
			point.vy = vy;
			point.vx = 0;
		}
		return point;
	}

	void bounce(Entity u) {

		// Wizard and Snaffles don't collide when the Wizard doesn't hold a
		// Snaffle
		if (this instanceof Wizard && u instanceof Snaffle) {
			if (!((Wizard) this).isHolding && ((Wizard) this).countdownBeforeNextHold <= 0) {
				((Snaffle) u).becomesGrabbedBy(this);
			}
			return;
		}
		else if (u instanceof Wizard && this instanceof Snaffle) {
			if (!((Wizard) u).isHolding && ((Wizard) u).countdownBeforeNextHold <= 0) {
				((Snaffle) this).becomesGrabbedBy(u);
			}
			return;
		}
		else if (u instanceof MapPoint && this instanceof Snaffle) {
			// System.err.println("Goal? " + ((MapPoint) u).isGoal() + " " + u);
			if (((MapPoint) u).isGoal()) {
				((Snaffle) this).scoredBy = ((MapPoint) u).getScorer();
				return;
			}
		}

		if (u instanceof MapPoint) {
			// System.err.println("Initiating collision with edge " + this);
			if (u.y == 0 || u.y == 7500) {
				vy = -vy;
			}
			else {
				vx = -vx;
			}
			this.debug = "Will collide with edge " + u;
			// System.err.println("Collision done with edge, " + this + " // " +
			// u);
			return;
		}

		// Bludgers - store last attacked wizard to avoid a rebounce
		// TODO: if Wizard is holding a Snaffle and gets recked, update Snaffle
		// position too
		if (this instanceof Bludger && u instanceof Wizard) {
			// System.err.println("Bouncing bludget && wizard " + this + "//" +
			// u);
			((Bludger) this).lastCollidedWizard = u.entityId;
			u.debug = "Will collide with Bludger " + this.entityId;
		}
		else if (this instanceof Wizard && u instanceof Bludger) {
			// System.err.println("Bouncing bludget && wizard " + this + "//" +
			// u);
			((Bludger) u).lastCollidedWizard = entityId;
			this.debug = "Will collide with Bludger " + u.entityId;
		}

		// System.err.println("Bouncing between " + this + " and " + u);
		float m1 = mass;
		float m2 = u.mass;

		float mcoeff = (m1 + m2) / (m1 * m2);

		float nx = x - u.x;
		float ny = y - u.y;
		// System.err.println("\tnew coords in u's ref: " + nx + ", " + ny);

		// Distance au carré entre les 2 entities. TODO: Pourrait être calculée
		// simplement comme la somme des carrés des rayons des deux entités
		float nxnysquare = nx * nx + ny * ny;
		// System.err.println("\tdistance between entities: " +
		// sqrt(nxnysquare));

		float dvx = vx - u.vx;
		float dvy = vy - u.vy;
		// System.err.println("\tnew speed in u's ref: " + dvx + ", " + dvy);

		// fx et fy sont les composantes du vecteur d'impact. product est juste
		// la pour optimiser
		float product = nx * dvx + ny * dvy;
		float fx = nx * product / (nxnysquare * mcoeff);
		float fy = ny * product / (nxnysquare * mcoeff);
		// System.err.println("\tvecteur d'impact: " + fx + ", " + fy);

		// On applique une fois le vecteur d'impact à chaque entité
		// proportionnellement à sa masse
		vx -= fx / m1;
		vy -= fy / m1;
		// System.err.println("\tNew vx for us: " + vx + ", " + vy);
		u.vx += fx / m2;
		u.vy += fy / m2;
		// System.err.println("\tNew vx for u: " + u.vx + ", " + u.vy);

		// Si la norme du vecteur d'impact est inférieur à 100, on change sa
		// norme pour le mettre à 100, sauf si on collisionne avec un bord
		// TODO: map edge collisions
		float impulse = (float) sqrt(fx * fx + fy * fy);
		// System.err.println("Impulse: " + impulse);
		if (impulse < GameEngine.MINIMUM_COLLISION_VELOCITY && !(u instanceof MapPoint)) {
			fx = fx * GameEngine.MINIMUM_COLLISION_VELOCITY / impulse;
			fy = fy * GameEngine.MINIMUM_COLLISION_VELOCITY / impulse;
			// System.err.println("Multiplying by coeff: " +
			// GameEngine.MINIMUM_COLLISION_VELOCITY / impulse);
		}

		// On applique une deuxième fois le vecteur d'impact à chaque entity
		// proportionnellement à sa masse
		// TODO: pourquoi ? Globalement je comprends pas l'application des
		// vecteurs vitesses de l'algo, à creuser sur comment marchent les
		// collisions elastiques
		vx -= fx / m1;
		vy -= fy / m1;
		// System.err.println("\tFinal new vx for us: " + vx + ", " + vy);
		u.vx += fx / m2;
		u.vy += fy / m2;
		// System.err.println("\tFinal new vx for u: " + u.vx + ", " + u.vy);
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = super.hashCode();
		result = prime * result + entityId;
		result = prime * result + Float.floatToIntBits(vx);
		result = prime * result + Float.floatToIntBits(vy);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) { return true; }
		if (!super.equals(obj)) { return false; }
		if (getClass() != obj.getClass()) { return false; }
		Entity other = (Entity) obj;
		if (entityId != other.entityId) { return false; }
		if (Float.floatToIntBits(vx) != Float.floatToIntBits(other.vx)) { return false; }
		if (Float.floatToIntBits(vy) != Float.floatToIntBits(other.vy)) { return false; }
		return super.equals(obj);
	}

	@Override
	public String toString() {
		return "Entity [entityId=" + entityId + ", vx=" + vx + ", vy=" + vy + ", friction=" + friction + ", mass="
				+ mass + ", radius=" + radius + ", debug=" + debug + "] " + super.toString();
	}

}

class Wizard extends Entity {
	boolean friendly;
	boolean isHolding;
	// int grabbedSnaffle = -1;
	int countdownBeforeNextHold;
	public String debug;

	public Wizard() {
		super(0.75f, 1f, 400f);
	}

	@Override
	public Wizard clear() {
		super.clear();
		friendly = false;
		isHolding = false;
		countdownBeforeNextHold = 0;
		// grabbedSnaffle = -
		return this;
	}

	protected Snaffle findClosestFreeSnaffle(GameState gameState) {
		Snaffle result = null;
		double distance = Double.MAX_VALUE;

		for (Snaffle snaffle : gameState.snaffles) {
			if (snaffle == null) {
				continue;
			}
			boolean snaffleHeld = snaffle.grabbedBy != -1;
			;
			if (!snaffleHeld) {
				double distanceToWizard = distance2(snaffle);
				if (distanceToWizard < distance) {
					result = snaffle;
					distance = distanceToWizard;
				}
			}
		}
		// System.err.println("Closest snaffle to wizard " + result + " " + this
		// + " " + gameState.snaffles);

		return result;
	}

	protected double distanceToClosestFreeSnaffle(GameState gameState) {
		double distance = Double.MAX_VALUE;

		for (Snaffle snaffle : gameState.snaffles) {
			if (snaffle == null) continue;
			boolean snaffleHeld = snaffle.grabbedBy != -1;
			if (snaffleHeld) continue;

			double distanceToWizard = distance2(snaffle);
			if (distanceToWizard < distance) {
				distance = distanceToWizard;
			}
		}
		// System.err.println("Closest snaffle to wizard " + result + " " + this
		// + " " + gameState.snaffles);

		return distance;
	}

	@Override
	public Wizard clone() {
		Wizard clone = Cache.newWizard();
		clone.x = x;
		clone.y = y;
		clone.entityId = entityId;
		clone.vx = vx;
		clone.vy = vy;
		clone.friendly = friendly;
		clone.isHolding = isHolding;
		clone.countdownBeforeNextHold = countdownBeforeNextHold;
		clone.debug = debug;
		return clone;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = super.hashCode();
		result = prime * result + (friendly ? 1231 : 1237);
		// result = prime * result + (isHolding ? 1231 : 1237);
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) { return true; }
		if (!super.equals(obj)) { return false; }
		if (getClass() != obj.getClass()) { return false; }
		Wizard other = (Wizard) obj;
		if (friendly != other.friendly) { return false; }
		// if (isHolding != other.isHolding) { return false; }
		return super.equals(obj);
	}

	@Override
	public String toString() {
		return "Wizard [friendly=" + friendly + ", isHolding=" + isHolding + ", countdownBeforeNextHold="
				+ countdownBeforeNextHold + ", debug=" + debug + "] " + super.toString();
	}

	public Snaffle findHeldSnaffle(GameState gameState) {
		for (Snaffle snaffle : gameState.snaffles) {
			if (snaffle == null) {
				continue;
			}
			if (snaffle.grabbedBy == this.entityId) { return snaffle; }
		}
		return null;
	}
}

class MapPoint extends Entity {

	public MapPoint() {
		super(Float.MAX_VALUE / 2, Float.MAX_VALUE / 2, 0);
	}

	public int getScorer() {
		return x == 0 ? 1 : 0;
	}

	public boolean isGoal() {
		if (x == 0 || x == 16000) { return y > 1900 && y < 5600; }
		return false;
	}

	@Override
	public String toString() {
		return "MapPoint [] " + super.toString();
	}
}

class Pole extends Entity {

	public Pole() {
		super(Float.MAX_VALUE / 2, Float.MAX_VALUE / 2, 300);
	}

	@Override
	public String toString() {
		return "Pole [] " + super.toString();
	}

}

class Snaffle extends Entity {

	public int scoredBy = -1;
	public int grabbedBy = -1;

	public Snaffle() {
		super(0.75f, 0.5f, 150f);
	}

	@Override
	public Snaffle clear() {
		super.clear();
		scoredBy = -1;
		grabbedBy = -1;
		return this;
	}

	public void becomesGrabbedBy(Entity entity) {
		x = entity.x;
		y = entity.y;
		vx = entity.vx;
		vy = entity.vy;
		((Wizard) entity).isHolding = true;
		((Wizard) entity).debug = "" + entityId;
		((Wizard) entity).countdownBeforeNextHold = 3;
		// debug = "grabbed by " + entity;
		grabbedBy = entity.entityId;
		// entity.debug = toString();
		// System.err.println("Grabbed by! " + this + " " + entity);
	}

	@Override
	void move(float t) {
		// if (!grabbed) {
		x += vx * t;
		y += vy * t;
		// }
	}

	@Override
	public Snaffle clone() {
		Snaffle clone = Cache.newSnaffle();
		clone.x = x;
		clone.y = y;
		clone.entityId = entityId;
		clone.vx = vx;
		clone.vy = vy;
		clone.scoredBy = scoredBy;
		// clone.debug = debug;
		clone.grabbedBy = grabbedBy;
		return clone;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = super.hashCode();
		// result = prime * result + (grabbed ? 1231 : 1237);
		result = prime * result + scoredBy;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj) return true;
		if (!super.equals(obj)) return false;
		if (getClass() != obj.getClass()) return false;
		Snaffle other = (Snaffle) obj;
		// if (grabbed != other.grabbed) return false;
		if (scoredBy != other.scoredBy) return false;
		return true;
	}

	@Override
	public String toString() {
		return "Snaffle [scoredBy=" + scoredBy + ", grabbedBy=" + grabbedBy + "] " + super.toString();
	}

}

class Bludger extends Entity {

	int lastCollidedWizard = -1;

	public Bludger() {
		super(0.9f, 8f, 200f);
	}

	@Override
	public Bludger clear() {
		super.clear();
		lastCollidedWizard = -1;
		return this;
	}

	public Wizard findClosestWizard(GameState gameState) {
		Wizard result = null;
		double distance = Double.MAX_VALUE;

		for (Wizard wizard : gameState.myWizards) {
			if (lastCollidedWizard == wizard.entityId) {
				continue;
			}
			double distanceToWizard = distance2(wizard);
			if (distanceToWizard < distance) {
				result = wizard;
				distance = distanceToWizard;
			}
		}
		for (Wizard wizard : gameState.opponentWizards) {
			if (lastCollidedWizard == wizard.entityId) {
				continue;
			}
			double distanceToWizard = distance2(wizard);
			if (distanceToWizard < distance) {
				result = wizard;
				distance = distanceToWizard;
			}
		}

		return result;
	}

	@Override
	public Bludger clone() {
		Bludger clone = Cache.newBludger();
		clone.x = x;
		clone.y = y;
		// clone.angle = angle;
		clone.entityId = entityId;
		clone.vx = vx;
		clone.vy = vy;
		clone.lastCollidedWizard = lastCollidedWizard;
		return clone;
	}

	@Override
	public String toString() {
		return "Bludger [lastCollidedWizard=" + lastCollidedWizard + "] " + super.toString();
	}

}

class Collision {
	Entity a, b;
	float t;
	float timeInProcess;

	public Collision(Entity a, Entity b, float t) {
		super();
		this.a = a;
		this.b = b;
		this.t = t;
	}

	@Override
	public String toString() {
		return "Collision [a=" + a + ", b=" + b + ", t=" + t + ", timeInProcess=" + timeInProcess + "]";
	}

}

// =================================
// Utils
// =================================
class Utils {
	public static int roundAwayFromZero(float f) {
		// System.err.println("Rounding " + f + " to " + (int) (signum(f) *
		// round(abs(f))));
		return (int) (signum(f) * round(abs(f)));
	}
}

// =================================
// AI
// =================================
abstract class AI {
	public abstract Action[] computeActions(GameState gameState);

	static Point goal0 = new Point(16000, 3750);
	static Point goal1 = new Point(0, 3750);

	protected Point findOpponentGoal(int myTeamId) {
		switch (myTeamId) {
		case 0:
			return goal0;
		case 1:
			return goal1;
		default:
			return null;
		}
	}
}

class MCAI extends AI {

	private static final Random RANDOM = new Random();

	static int TIME_FOR_OWN_SIM = 55;
	static int TIME_FOR_OPP_SIM = 10;
	static int TIME_FOR_OWN_SIM_FIRST_TURN = 55;
	static int SOLUTIONS_POOL_SIZE = 50000;

	static int LOOK_AHEAD = 3;

	static Solution[] solutions = new Solution[SOLUTIONS_POOL_SIZE];

	static boolean SHOULD_CARRY_OVER = false;
	static int CARRIED_OVER = 20;
	static int CLONES = 5;
	static Solution[] carriedOver = new Solution[CARRIED_OVER];

	@Override
	public Action[] computeActions(GameState gameState) {

		solutions = new Solution[SOLUTIONS_POOL_SIZE];

		// TODO: compute best opponentActions
		Action[] opponentActions = null;
		// while (System.currentTimeMillis() - start < TIME_FOR_OPP_SIM) {
		//
		// }
		// start = System.currentTimeMillis();

		Action[] chosenActions = new Action[2];

		int index = 0;

		// System.err.println("Starting MCAI after " +
		// (System.currentTimeMillis() - Player.turnStart));
		System.err.println("Starting carrying over from previous " + (System.currentTimeMillis() - Player.turnStart));

		int carriedOverIndex = 0;

		while (SHOULD_CARRY_OVER && index < CARRIED_OVER && carriedOver[carriedOverIndex] != null) {

			Solution carriedOverSolution = carriedOver[carriedOverIndex++];

			GameState initialState = Cache.newGameState();
			initialState.cloneFrom(gameState);

			GameState finalState = Cache.newGameState();
			finalState.cloneFrom(initialState);

			for (int i = 0; i < MCAI.LOOK_AHEAD - 1; i++) {
				Action[] actions = carriedOverSolution.steps[i].actions;
				GameEngine.simulateNextTurn(initialState, finalState, actions, opponentActions);
				initialState = finalState;
			}

			for (int k = 0; k < CLONES; k++) {
				GameState newFinalState = Cache.newGameState();
				newFinalState.cloneFrom(initialState);

				Solution offspring = carriedOverSolution.clone();

				Action[] actions = buildRandomActions(initialState);
				// System.err.println("Actions " + Arrays.toString(actions));
				GameEngine.simulateNextTurn(initialState, newFinalState, actions, opponentActions);
				initialState = newFinalState;
				offspring.steps[MCAI.LOOK_AHEAD - 1].actions = actions;
				offspring.steps[MCAI.LOOK_AHEAD - 1].score = evaluateFinalPosition(newFinalState);

				offspring.computeScore();

				solutions[index] = offspring;
				index++;
			}
		}

		System.err.println("Starting MCAI proper after " + (System.currentTimeMillis() - Player.turnStart));

		float simTime = Player.firstTurnDone ? TIME_FOR_OWN_SIM : TIME_FOR_OWN_SIM_FIRST_TURN;
		System.err.println("sim time " + simTime);
		try {
			while (System.currentTimeMillis() - Player.turnStart < simTime) {

				// Build a solution that has valid steps
				GameState cloneState = Cache.newGameState();
				cloneState.cloneFrom(gameState);

				GameState finalState = Cache.newGameState();
				finalState.cloneFrom(cloneState);

				Solution solution = buildSolution(cloneState, finalState, opponentActions);

				GameState debugState = Cache.newGameState();
				debugState.cloneFrom(finalState);
				solution.expectedEndState = debugState;

				// Store that solution
				solutions[index++] = solution;
			}
		}
		catch (Exception e) {
			System.err.println(index + " solutions");
			throw e;
		}

		System.err.println("Ended MCAI after " + (System.currentTimeMillis() - Player.turnStart));

		// Sort solutions
		Arrays.sort(solutions, new Comparator<Solution>() {
			@Override
			public int compare(Solution o1, Solution o2) {

				if (o1 == null) { return 1; }
				if (o2 == null) { return -1; }
				if (o2.score == o1.score) { return 0; }
				return o2.score > o1.score ? 1 : -1;
			}
		});

		// Take the best one
		int i = 0;
		Solution best = null;
		try {
			do {
				best = solutions[i];
				chosenActions[0] = solutions[i].steps[0].actions[0];
				chosenActions[1] = solutions[i].steps[0].actions[1];

				if (i > 10) {
					System.err.println("First 10 solutions are invalid, issue with the simulation");
					System.err.println(Arrays.toString(gameState.myWizards));
					System.err.println(solutions[0].steps[0].actions[0]);
					System.err.println(solutions[0].steps[0].actions[1]);
					System.err.println(gameState);
					throw new RuntimeException();
				}
			}
			while (!solutions[i++].steps[0].isValid(gameState));
		}
		catch (Exception e) {
			System.err.println("Breaking at step " + i);
			System.err.println(solutions[0].steps[0].actions[0]);
			System.err.println(solutions[0].steps[0].actions[1]);
			throw e;
		}

		// System.err.println("Best solution will lead us to game state in " +
		// LOOK_AHEAD + " turns");
		// System.err.println(best.expectedEndState);
		// System.err.println(best);

		i = 0;
		if (SHOULD_CARRY_OVER) {
			index = 0;
			while (i < CARRIED_OVER) {
				if (solutions[index].steps[0].isValid(gameState)) {
					for (int j = 0; j < MCAI.LOOK_AHEAD - 1; j++) {
						solutions[index].steps[j] = solutions[index].steps[j + 1];
					}
					carriedOver[i] = solutions[index];
					i++;
				}
				index++;
			}
		}

		System.err.println("Did " + index + " solutions after " + (System.currentTimeMillis() - Player.turnStart));

		return chosenActions;
	}

	private Solution buildSolution(GameState initialState, GameState finalState, Action[] opponentActions) {
		Solution solution = Cache.newSolution();

		for (int i = 0; i < LOOK_AHEAD; i++) {
			Action[] actions = buildRandomActions(initialState);
			// System.err.println("Actions " + Arrays.toString(actions));
			GameEngine.simulateNextTurn(initialState, finalState, actions, opponentActions);
			initialState = finalState;
			solution.steps[i].actions = actions;
			solution.steps[i].score = evaluateFinalPosition(finalState);
			initialState = finalState;
		}

		solution.computeScore();

		return solution;
	}

	private Action[] buildRandomActions(GameState initialState) {
		Action[] actions = new Action[2];

		for (int i = 0; i < 2; i++) {
			Action action = Cache.newAction();
			action.debug = "" + initialState.myWizards[i].isHolding;
			// 0 is MOVE, 1 is THROW
			if (initialState.myWizards[i].isHolding) {
				Snaffle held = initialState.myWizards[i].findHeldSnaffle(initialState);
				if (held == null) {
					System.err.println("Deciding on a throw while wizard is not holding!");
					System.err.println(initialState);
					throw new RuntimeException();
				}
				action.type = "THROW";
				action.power = 500;// Math.min(500, 400 + RANDOM.nextInt(300));
				// Always throw forward
				if (initialState.myTeamId == 0) {
					action.x = initialState.myWizards[i].x + RANDOM.nextInt(16000);
				}
				else {
					action.x = RANDOM.nextInt((int) initialState.myWizards[i].x);
				}
				action.y = RANDOM.nextInt(7501);
				// action.x = RANDOM.nextInt(16001);
				// action.y = RANDOM.nextInt(7501);
				// Point opponentGoal = findOpponentGoal(initialState.myTeamId);
				// action.x = opponentGoal.x;
				// action.y = opponentGoal.y;
			}
			else {
				Snaffle held = initialState.myWizards[i].findHeldSnaffle(initialState);
				if (held != null) {
					System.err.println("Holding a snaffle, shuold throw instead!");
					System.err.println(initialState);
					throw new RuntimeException();
				}
				action.type = "MOVE";
				action.power = 150; // Math.min(150, 120 + RANDOM.nextInt(100));
				action.x = RANDOM.nextInt(16001);
				action.y = RANDOM.nextInt(7501);
			}
			actions[i] = action;
		}
		return actions;
	}

	static float SCORE_WEIGHT = 1000;
	static float CLOSEST_DIST_WEIGHT = 1.5f;
	static float GLOBAL_DIST_TO_SNAFFLES_WEIGTH = 1f;
	static float HOLDING_WEIGHT = 5;
	static float WIN_LOSS_WEIGHT = 100000;
	static float SPREAD_WEIGHT = 0.3f;
	static float SPEED_WEIGHT = 0;
	static float SNAFFLE_DIST_TO_GOAL_WEIGHT = 0;

	static float MAX_DISTANCE = (float) 16000 * 16000 + 7500 * 7500;
	static float WIZARD_TO_SNAFFLE_MIN_DIST = 400;

	private float evaluateFinalPosition(GameState finalState) {
		// Cache.logEval();
		float score = 0;

		int numberOfSnaffles = finalState.initialTotalEntities == 11 ? 7 : 5;

		// Direct win/loss
		if ((finalState.initialTotalEntities == 11 && finalState.myScore == 4)
				|| (finalState.initialTotalEntities == 9 && finalState.myScore == 3)) {
			score += WIN_LOSS_WEIGHT;
		}
		else if ((finalState.initialTotalEntities == 11 && finalState.opponentScore == 4)
				|| (finalState.initialTotalEntities == 9 && finalState.opponentScore == 3)) {
			score -= WIN_LOSS_WEIGHT;
		}

		score += SCORE_WEIGHT * finalState.myScore;
		score -= SCORE_WEIGHT * finalState.opponentScore;

		// Add the distance of ourselves to the snaffles
		for (Wizard wizard : finalState.myWizards) {
			if (wizard.isHolding) {
				score += HOLDING_WEIGHT;
			}
			else {
				float dist = (float) wizard.distanceToClosestFreeSnaffle(finalState);
				float normalizedDist = (dist - WIZARD_TO_SNAFFLE_MIN_DIST) / MAX_DISTANCE;
				score += CLOSEST_DIST_WEIGHT * (1 - normalizedDist);
			}
		}

		// We want to be spread out to cover more ground instead of being all
		// together
		float wizardSpread = finalState.myWizards[0].distance2(finalState.myWizards[1]);
		score += SPREAD_WEIGHT * wizardSpread / MAX_DISTANCE;

//		float totalSpeed = 0;
//		float totalDistanceToSnaffles = 0;
//		for (Wizard wizard : finalState.myWizards) {
//			totalSpeed += sqrt(wizard.vx * wizard.vx + wizard.vy * wizard.vy);
//			for (Snaffle snaffle : finalState.snaffles) {
//				if (snaffle == null) continue;
//				totalDistanceToSnaffles += wizard.distance(snaffle);
//			}
//		}
//		score += SPEED_WEIGHT * totalSpeed / 2;
//		score -= GLOBAL_DIST_TO_SNAFFLES_WEIGTH * totalDistanceToSnaffles / (MAX_DISTANCE * 2 * numberOfSnaffles);

		// Then basic heuristic: sum snaffle distance to the center of our
		// opponent's goal
		// TODO: account for distance to the goal itself, not only the center
		float totalDistanceToMyGoal = 0;
		for (Snaffle snaffle : finalState.snaffles) {
			if (snaffle == null) {
				continue;
			}
			Point myGoal = findOpponentGoal(finalState.myTeamId == 0 ? 1 : 0);
			totalDistanceToMyGoal += snaffle.distance(myGoal);
		}
		score += SNAFFLE_DIST_TO_GOAL_WEIGHT * totalDistanceToMyGoal / (MAX_DISTANCE * numberOfSnaffles);
		// Cache.logEvalEnd();

		return score;
	}
}

class Solution {
	GameState expectedEndState;
	float score;
	Step[] steps = new Step[MCAI.LOOK_AHEAD];

	public Solution() {
		for (int i = 0; i < MCAI.LOOK_AHEAD; i++) {
			steps[i] = Cache.newStep();
		}
	}

	public void computeScore() {
		for (int i = 0; i < MCAI.LOOK_AHEAD; i++) {
			score += (1 - i * 0.15) * steps[i].score;
		}
	}

	@Override
	public Solution clone() {
		Solution clone = Cache.newSolution();
		clone.score = 0;
		for (int i = 0; i < MCAI.LOOK_AHEAD; i++) {
			clone.steps[i] = Cache.newStep();
			clone.steps[i].actions[0] = steps[i].actions[0].clone();
			clone.steps[i].actions[1] = steps[i].actions[1].clone();
		}
		return clone;
	}

	@Override
	public String toString() {
		return "Solution [score=" + score + ", steps=" + Arrays.toString(steps) + "]";
	}
}

class Step {
	public float score;
	Action[] actions = new Action[2];

	public boolean isValid(GameState gameState) {
		for (int i = 0; i < 2; i++) {
			if (actions[i].type == "MOVE" && gameState.myWizards[i].isHolding == true) { return false; }
			if (actions[i].type == "THROW" && gameState.myWizards[i].isHolding == false) { return false; }
		}
		return true;
	}

	@Override
	public String toString() {
		return "Step [score=" + score + ", actions=" + Arrays.toString(actions) + "]";
	}

}

// =================================
// Game Engine
// =================================
class GameEngine {

	static final int MINIMUM_COLLISION_VELOCITY = 100;

	// static final int MAX_COLLISION_SIM_TIME = 5;

	public static void simulateNextTurn(GameState gameState, GameState expectedGameState, Action[] wizardActions,
			Action[] opponentActions) {
		Entity[] simulatedEntities = new Entity[17];
		int counter = 0;
		for (int i = 0; i < 2; i++) {
			simulatedEntities[counter++] = expectedGameState.myWizards[i];
		}
		for (int i = 0; i < 2; i++) {
			simulatedEntities[counter++] = expectedGameState.opponentWizards[i];
		}
		for (int i = 0; i < 2; i++) {
			simulatedEntities[counter++] = expectedGameState.bludgers[i];
		}
		for (int i = 0; i < 7; i++) {
			simulatedEntities[counter++] = expectedGameState.snaffles[i];
		}
		// for (int i = 0; i < 4; i++) {
		// simulatedEntities[counter++] = expectedGameState.poles[i];
		// }

		simulateOurWizards(gameState, expectedGameState, wizardActions);
		// if (expectedGameState.invalid) { return; }
		simulateBludgers(gameState, expectedGameState);
		// System.err.println("Simulating plays for entities " +
		// simulatedEntities);
		play(simulatedEntities);
		// simulateCollisions(gameState, expectedGameState);
		updateScore(expectedGameState, gameState);
	}

	private static void updateScore(GameState expectedGameState, GameState gameState) {
		for (int i = 0; i < expectedGameState.snaffles.length; i++) {
			Snaffle snaffle = expectedGameState.snaffles[i];
			if (snaffle == null) {
				continue;
			}

			if (snaffle.scoredBy == 0) {
				if (expectedGameState.myTeamId == 0) {
					// System.err.println("We scored a goal! ");
					expectedGameState.myScore++;
					// You can have goals without anyone holding the snaffle
					if (expectedGameState.snaffles[i].grabbedBy != -1) {
						((Wizard) expectedGameState.findEntity(expectedGameState.snaffles[i].grabbedBy)).isHolding = false;
					}
					expectedGameState.snaffles[i] = null;
					gameState.remove(snaffle);
				}
				else if (expectedGameState.myTeamId == 1) {
					// System.err.println("They scored a goal! ");
					expectedGameState.opponentScore++;
					if (expectedGameState.snaffles[i].grabbedBy != -1) {
						((Wizard) expectedGameState.findEntity(expectedGameState.snaffles[i].grabbedBy)).isHolding = false;
					}
					expectedGameState.snaffles[i] = null;
					gameState.remove(snaffle);
				}
			}
			else if (snaffle.scoredBy == 1) {
				if (expectedGameState.myTeamId == 1) {
					// System.err.println("We scored a goal! ");
					expectedGameState.myScore++;
					if (expectedGameState.snaffles[i].grabbedBy != -1) {
						((Wizard) expectedGameState.findEntity(expectedGameState.snaffles[i].grabbedBy)).isHolding = false;
					}
					expectedGameState.snaffles[i] = null;
					gameState.remove(snaffle);
				}
				else if (expectedGameState.myTeamId == 0) {
					// System.err.println("They scored a goal! ");
					expectedGameState.opponentScore++;
					if (expectedGameState.snaffles[i].grabbedBy != -1) {
						((Wizard) expectedGameState.findEntity(expectedGameState.snaffles[i].grabbedBy)).isHolding = false;
					}
					expectedGameState.snaffles[i] = null;
					gameState.remove(snaffle);
				}
			}
		}
	}

	private static void simulateOurWizards(GameState gameState, GameState expectedGameState, Action[] actions) {
		for (int i = 0; i < 2; i++) {
			Action action = actions[i];
			if ("MOVE".equals(action.type)) {
				expectedGameState.myWizards[i].applyNewSpeed(action.x, action.y, action.power);
			}
			else if ("THROW".equals(action.type)) {
				Snaffle held = expectedGameState.myWizards[i].findHeldSnaffle(expectedGameState);
				// System.err.println("Applying new speed to thrown snaffle " +
				// held + " " + action);
				// TODO: incorrect simulation?
				// if (held == null) {
				// // System.err.println("WARN: incorrect simulation with
				// // original action");
				// actions[i].type = "MOVE";
				// actions[i].power = Math.min(150, actions[i].power);
				// expectedGameState.myWizards[i].applyNewSpeed(action.x,
				// action.y, action.power);
				// return;
				// }
				try {
					held.applyNewSpeed(action.x, action.y, action.power);
				}
				catch (Exception e) {
					System.err.println("No snaffle to throw! ");
					System.err.println(expectedGameState);
					throw e;
				}
				held.grabbedBy = -1;
				expectedGameState.myWizards[i].isHolding = false;
				// System.err.println("New snaffle " + held);
				// expectedGameState.myWizards[i].applyNewSpeed(action.position,
				// action.power);
			}
		}
	}

	private static void simulateBludgers(GameState gameState, GameState expectedGameState) {
		for (Bludger bludger : expectedGameState.bludgers) {
			// Bludger moves where the wizard was at the beginning of the turn
			Wizard closestWizard = bludger.findClosestWizard(gameState);
			// System.err.println("Simulating bludger move " + bludger + "
			// towards " + closestWizard);
			bludger.applyNewSpeed(closestWizard, 1000);
		}
	}

	// TODO still issues when there are many collisions in a single step (like
	// when a buldger sends a wizard against the edge, it rebounds on the
	// buldget, etc)
	private static void play(Entity[] entities) {
		// Il faut conserver le temps où on en est dans le tour. Le but est
		// d'arriver à 1.0
		float t = 0.0f;
		// long start = System.currentTimeMillis();

		Collision[] previousCollisions = new Collision[20];
		// Collision previousCollision = null;
		int collisions = 0;
		// TODO: reasonable? Try to avoid multi hits
		while (t < 1.0) {
			Collision firstCollision = null;

			// On cherche toutes les collisions qui vont arriver pendant ce tour
			// et on garde celle qui arrive en premier
			for (int i = 0; i < entities.length; i++) {
				if (entities[i] == null) {
					continue;
				}
				// Collision avec une autre entité ?
				for (int j = i + 1; j < entities.length; j++) {
					if (entities[j] == null) {
						continue;
					}

					Collision col = entities[i].collision(entities[j]);

					// Si la collision arrive plus tôt que celle qu'on, alors on
					// la garde
					if (col != null && col.t + t < 1.0 && !hasPreviousCollision(previousCollisions, col)
							&& (firstCollision == null || col.t < firstCollision.t)) {
						// System.err.println("Keeping collision over " + col +
						// " // " + firstCollision);
						firstCollision = col;
						firstCollision.timeInProcess = t;
					}
				}
			}

			for (int i = 0; i < entities.length; i++) {
				if (entities[i] == null) {
					continue;
				}
				Collision col = entities[i].edgeCollision();
				if (col != null && col.t + t < 1.0 && !hasPreviousCollision(previousCollisions, col)
						&& (firstCollision == null || col.t < firstCollision.t)) {
					// System.err.println("Edge collision! " + col);
					// System.err.println("Keeping collision over " + col + " //
					// " + firstCollision);
					firstCollision = col;
					firstCollision.timeInProcess = t;
				}
			}

			if (firstCollision != null) {
				// Cache.logCollision();
				// System.err.println("Collision! " + firstCollision);
				// System.err.println(Arrays.toString(previousCollisions));

				// On bouge les entities du temps qu'il faut pour arriver sur
				// l'instant `t` de la collision
				for (int i = 0; i < entities.length; ++i) {
					if (entities[i] == null) {
						continue;
					}
					// System.err.println("moving entities by " +
					// firstCollision.t);
					entities[i].move(firstCollision.t);
				}

				// On joue la collision
				firstCollision.a.bounce(firstCollision.b);

				t += firstCollision.t;
				// System.err.println("setting t: " + t + " " +
				// firstCollision.t);

				for (int i = 0; i < previousCollisions.length; i++) {
					if (previousCollisions[i] == null) {
						previousCollisions[i] = firstCollision;
						break;
					}
				}
				// previousCollision = firstCollision;
				collisions++;
			}
			else {
				// Aucune collision, on peut juste déplacer les entities jusqu'à
				// la fin du tour
				for (int i = 0; i < entities.length; ++i) {
					if (entities[i] == null) {
						continue;
					}
					// System.err.println("moving entities by " + (1.0f - t));
					entities[i].move(1.0f - t);
				}

				// Fin du tour
				t = 1.0f;
			}
		}

		// On arrondi les positions et on tronque les vitesses pour tout le
		// monde
		for (int i = 0; i < entities.length; ++i) {
			if (entities[i] == null) {
				continue;
			}
			// System.err.println("Rounding values for " + entities[i]);
			entities[i].end();
			// System.err.println("\tWhich gives " + entities[i]);
		}
	}

	private static boolean hasPreviousCollision(Collision col, Collision collision) {
		if (col == null) { return false; }
		// System.err.println("\tComparing " + col + " and " + collision);
		if (abs(collision.t) == 0 && col.a.entityId == collision.a.entityId && col.b.entityId == collision.b.entityId) { return true; }
		return false;
	}

	private static boolean hasPreviousCollision(Collision[] previousCollisions, Collision collision) {
		for (Collision col : previousCollisions) {
			if (col == null) {
				continue;
			}
			// System.err.println("\tComparing " + col + " and " + collision);
			if (abs(collision.t) < 0.01 && col.a.entityId == collision.a.entityId
					&& col.b.entityId == collision.b.entityId) { return true; }
		}
		return false;
	}
}