Skip to content

Instantly share code, notes, and snippets.

@Jahz19
Created March 9, 2017 22:51
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Jahz19/756850c86f95bf3e97fc369832b487b0 to your computer and use it in GitHub Desktop.
CodinGame - Ghost in the cell
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment