Cloud Contest 2 - bot by dalex

import org.json.JSONArray;
import org.json.JSONObject;

import java.net.Socket;

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

import static java.lang.Math.*;

public class Main {

    class Point {

        public int x, y;

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

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + x;
            result = prime * result + 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 (x != other.x)
                return false;
            if (y != other.y)
                return false;
            return true;
        }

        @Override
        public String toString() {
            return String.format("(%d %d)", x, y);
        }

    }

    class Bot {
        String botName;
        String playerName;
        int x, y;
        int hp;
        int respawnTime;
        List<Point> canShoot;
        boolean alive;

        public Bot(String botName, String playerName, int x, int y, int hp, int respawnTime, List<Point> canShoot) {
            this.botName = botName;
            this.playerName = playerName;
            this.x = x;
            this.y = y;
            this.hp = hp;
            this.respawnTime = respawnTime;
            this.canShoot = canShoot;
            this.alive = hp > 0;
        }

        @Override
        public String toString() {
            return String.format("[%s : (%d %d), (%d)]", botName, x, y, hp);
        }

        boolean canMove(int direction) {
            if (direction < 0 || 4 <= direction) {
                throw new RuntimeException("wrong direction for bot");
            }
            int nx = x + dx[direction];
            int ny = y + dy[direction];
            if (good(nx, ny)) {
                if (a[nx][ny] == '0') {
                    return true;
                }
            }
            return false;
        }

    }

    public static void main(String[] args) throws Exception {
        while (true) {
            new Main().run();
        }
    }

    public void run() throws Exception {
        socket = new Socket(URL, PORT);
        in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
        out = new PrintWriter(socket.getOutputStream());
        textLog = new PrintWriter("log.txt");
        try {
            work();
        } catch (Exception e) {
        } finally {
            in.close();
            out.close();
            socket.close();
        }
    }

    void debug(Object... objs) {
        System.out.println(Arrays.deepToString(objs));
        System.out.flush();
    }

    void log(Object... objs) {
        System.out.println(Arrays.deepToString(objs));
        System.out.flush();
    }

    final String URL = "10.0.0.10";
    final int PORT = 8000;
    final String USER_TOKEN = "a5eed58c4350afc48efd5ffa";
    //final String GAME_TOKEN = "9487765b575d49bd34816a02";
    //final String GAME_TOKEN = "d838685afbff0639fdae8ae8";
    //final String GAME_TOKEN = "34d9a705d95c8c444ff9331f";
    //final String GAME_TOKEN = "c3b117d5f5d02d9d3ad92c23";
    //final String GAME_TOKEN = "f35819a583024b85206bea31";
    //final String GAME_TOKEN = "4e49ecd210fbd45d5793848d";

    //final String GAME_TOKEN = "f16d691906ed1f8800b11e7d";
    //final String GAME_TOKEN = "1ede95a61a262930384e0502";
    final String GAME_TOKEN = "fb4d81f113bb41130850b10a";

    final int[] dx = {0, 1, 0, -1};
    final int[] dy = {1, 0, -1, 0};
    final char[] dc = "rdlu".toCharArray();

    char getCommand(int direction) {
        //return "drul".charAt(direction);
        return dc[direction];
    }

    boolean good(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    boolean good(Point p) {
        return good(p.x, p.y);
    }

    Socket socket;
    BufferedReader in;
    PrintWriter out;
    PrintWriter textLog;

//-------------------------------------------------------------------------------------------

    final int INF = 1000 * 1000;
    final Random rnd = new Random();

    int n, m, moveNumber;

    List<Bot> myBots;
    List<Bot> enemyBots;

    Map<String, Integer> scores;
    List<String> playerNames;

    String myName;

    char[][] a;

    Map<String, Point> fireMap;
    Map<String, Character> moveMap;

    void makeFire() {
        //debug(myBots);
        //debug(enemyBots);
        boolean[][] graph = new boolean[myBots.size()][enemyBots.size()];
        int[] enemyHp = new int[enemyBots.size()];
        int[] dmg = new int[enemyBots.size()];
        int ai = 0;
        for (Bot myBot : myBots) {
            int bi = 0;
            for (Bot enemyBot : enemyBots) {
                enemyHp[bi] = enemyBot.hp;
                int bx = enemyBot.x;
                int by = enemyBot.y;
                Point bPoint = new Point(bx, by);
                if (myBot.canShoot.contains(bPoint)) {
                    graph[ai][bi] = true;
                }
                bi++;
            }
            ai++;
        }
        int[] target = new int[myBots.size()];
        Arrays.fill(target, -1);
        for (int bi = 0; bi < enemyBots.size(); bi++) {
            if (enemyHp[bi] - dmg[bi] == 1) {
                for (int i = 0; i < myBots.size(); i++) {
                    if (target[i] == -1 && graph[i][bi]) {
                        target[i] = bi;
                        dmg[bi]++;
                        break;
                    }
                }
            }
        }
        for (int bi = 0; bi < enemyBots.size(); bi++) {
            if (enemyHp[bi] - dmg[bi] == 2) {
                for (int i = 0; i < myBots.size(); i++) {
                    if (target[i] == -1 && graph[i][bi]) {
                        for (int j = i+1; j < myBots.size(); j++) {
                            if (target[j] == -1 && graph[j][bi]) {
                                target[i] = bi;
                                target[j] = bi;
                                dmg[bi] += 2;
                                break;
                            }
                        }
                    }
                }
            }
        }
        for (int bi = 0; bi < enemyBots.size(); bi++) {
            if (enemyHp[bi] - dmg[bi] == 3) {
                for (int i = 0; i < myBots.size(); i++) {
                    if (target[i] == -1 && graph[i][bi]) {
                        for (int j = i+1; j < myBots.size(); j++) {
                            if (target[j] == -1 && graph[j][bi]) {
                                for (int k = j+1; k < myBots.size(); k++) {
                                    if (target[k] == -1 && graph[k][bi]) {
                                        target[i] = bi;
                                        target[j] = bi;
                                        target[k] = bi;
                                        dmg[bi] += 3;
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0; i < myBots.size(); i++) {
            if (target[i] == -1) {
                for (int bi = 0; bi < enemyBots.size(); bi++) {
                    if (graph[i][bi] && enemyHp[bi] - dmg[bi] > 0) {
                        target[i] = bi;
                        dmg[bi]++;
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < myBots.size(); i++) {
            if (target[i] != -1) {
                Bot enemy = enemyBots.get(target[i]);
                Point point = new Point(enemy.x, enemy.y);
                fireMap.put(myBots.get(i).botName, point);
            }
        }
        log("Fire map: " + fireMap);
    }

    Point[] destPoints;
    final int destPointCount = 1;

    void makeMoveRandom(Bot bot) {
        char ch = 's';
        for (int j = 0; j < 100; j++) {
            int direction = rnd.nextInt(4);
            if (bot.canMove(direction)) {
                ch = dc[direction];
                break;
            }
        }
        moveMap.put(bot.botName, ch);
    }

    void makeMove() {
        Map<Point, Bot> pointMap = new HashMap<Point, Bot>();
        for (int i = 0; i < myBots.size(); i++) {
            Bot bot = myBots.get(i);
            //makeMoveRandom(bot);
            Point botPoint = new Point(bot.x, bot.y);
            Point destPoint = destPoints[i % destPointCount];
            int dir = whereNeedToGo(botPoint, destPoint);
            Point newPoint = new Point(botPoint.x + dx[dir], botPoint.y + dy[dir]);
            pointMap.put(newPoint, bot);
        }
        for (Entry<Point, Bot> entry : pointMap.entrySet()) {
            Point destPoint = entry.getKey();
            Bot bot = entry.getValue();
            Point curPoint = new Point(bot.x, bot.y);
            int dir = getDirection(curPoint, destPoint);
            moveMap.put(bot.botName, dc[dir]);
        }
    }

    int getDirection(Point curPoint, Point destPoint) {
        for (int i = 0; i < 4; i++) {
            Point newPoint = new Point(curPoint.x + dx[i], curPoint.y + dy[i]);
            if (newPoint.equals(destPoint)) {
                return i;
            }
        }
        throw new RuntimeException("error in getDirection()");
    }

    void work() throws Exception {
        receiveConnectionApprove();
        receiveConnectionSuccess();
        receiveFieldInfo();
        printArrayToLog();
        myBots = new ArrayList<Bot>();
        enemyBots = new ArrayList<Bot>();
        scores = new TreeMap<String, Integer>();
        playerNames = new ArrayList<String>();
        fireMap = new TreeMap<String, Point>();
        moveMap = new TreeMap<String, Character>();
        destPoints = new Point[destPointCount];
        for (int mv = 0; true; mv++) {
            long startTime = System.currentTimeMillis();

            rnd.setSeed(System.currentTimeMillis());
            myBots.clear();
            enemyBots.clear();
            scores.clear();
            playerNames.clear();
            fireMap.clear();
            moveMap.clear();

            receiveBotsInfo();
            removeDeadBots();
            generateDestinationPoints();

            /*Collections.sort(myBots, new Comparator<Bot>() {
                @Override
                public int compare(Bot o1, Bot o2) {
                    return o1.botName.compareTo(o2.botName);
                }
            });*/

            for (int i = 0; i < myBots.size(); i++) {
                Bot bot = myBots.get(i);
                int x = bot.x;
                int y = bot.y;
                a[x][y] = (char)('A' + i);
            }

            /*debug(myName);
            debug(playerNames);
            debug(scores);
            debug(moveNumber);
            debug(myBots);
            debug(enemyBots);*/

            makeFire();
            makeMove();
            checkDestinationPoints();

            sendData();

            long endTime = System.currentTimeMillis();
            log("Move " + moveNumber + " has been finished in " + (endTime - startTime) + "ms.");
            logScores();

            System.out.println();
            System.out.flush();
        }
    }

    void logScores() {
        Set<Entry<String, Integer>> set = scores.entrySet();
        String[] names = new String[set.size()];
        int[] points = new int[set.size()];
        int cnt = 0;
        for (Entry<String, Integer> e : set) {
            names[cnt] = e.getKey();
            points[cnt] = e.getValue();
            cnt++;
        }
        for (int i = 0; i < cnt-1; i++) {
            for (int j = 0; j < cnt-1; j++) {
                if (points[j] < points[j+1] || points[j] == points[j+1] && names[j].compareTo(names[j+1]) > 0) {
                    String tmp = names[j];
                    names[j] = names[j+1];
                    names[j+1] = tmp;
                    int zzz = points[j];
                    points[j] = points[j+1];
                    points[j+1] = zzz;
                }
            }
        }
        log("Scores");
        for (int i = 0; i < cnt; i++) {
            log(names[i] + ": " + points[i]);
        }
    }

    void checkDestinationPoints() {
        for (int pi = 0; pi < destPointCount; pi++) {
            Point p = destPoints[pi];
            boolean needNewPoint = false;
            botCycle: for (int i = pi; i < myBots.size(); i += destPointCount) {
                Bot bot = myBots.get(i);
                Point botP = new Point(bot.x, bot.y);
                /*for (Bot enemyBot : enemyBots) {
                    Point enemyPoint = new Point(enemyBot.x, enemyBot.y);
                    if (bot.canShoot.contains(enemyPoint)) {
                        destPoints[pi] = enemyPoint;
                        debug("bot" + bot.botName + " goes to point " + enemyBot);
                        needNewPoint = false;
                        break botCycle;
                    }
                }*/
                int dist = shortestPath(p, botP);
                if (dist <= 2) {
                    needNewPoint = true;
                    break;
                }
            }
            if (needNewPoint) {
                destPoints[pi] = null;
            }
        }
        debug(destPoints);
    }

    void generateDestinationPoints() {
        //log("enter into generateDestinationPoints()");
        goToEnemies();
        int criticalDist = (n + m) / 5 * 3;
        boolean needGenerate = false;
        for (int i = 0; i < destPointCount; i++) {
            if (destPoints[i] == null) {
                needGenerate = true;
                break;
            }
        }
        if (!needGenerate) {
            return;
        }
        while (true) {
            for (int i = 0; i < destPointCount; i++) {
                destPoints[i] = randomDestinationPoint(i);
            }
            if (destPointCount == 1) {
                break;
            }
            int maxDist = 0;
            for (int i = 0; i < destPointCount; i++) {
                for (int j = i+1; j < destPointCount; j++) {
                    int distance = shortestPath(destPoints[i], destPoints[j]);
                    //log(distance);
                    maxDist = max(maxDist, distance);
                }
            }
            if (maxDist >= criticalDist) {
                break;
            }
        }
    }

    void goToEnemies() {
        List<Point> enemyPoints = new ArrayList<Point>();
        for (Bot enemyBot : enemyBots) {
            enemyPoints.add(new Point(enemyBot.x, enemyBot.y));
        }
        for (int pi = 0; pi < destPointCount; pi++) {
            int bestEnemy = -1;
            int minDist = 7*INF;
            for (int bi = 0; bi < enemyPoints.size(); bi++) {
                int sumDist = 0;
                for (int i = pi; i < myBots.size(); i += destPointCount) {
                    Point botPoint = new Point(myBots.get(i).x, myBots.get(i).y);
                    sumDist += shortestPath(botPoint, enemyPoints.get(bi));
                }
                if (bestEnemy == -1 || minDist > sumDist) {
                    boolean was = false;
                    for (int k = 0; k < destPointCount; k++) {
                        if (destPoints[k] == null) {
                            continue;
                        }
                        int theDist = shortestPath(destPoints[k], enemyPoints.get(bi));
                        if (theDist < (n+m)/6) {
                            was = true;
                            break;
                        }
                    }
                    if (!was) {
                        bestEnemy = bi;
                        minDist = sumDist;
                    }
                }
            }
            if (bestEnemy != -1) {
                destPoints[pi] = enemyPoints.get(bestEnemy);
            }
        }
    }

    int shortestPath(Point start, Point finish) {
        int[][] d = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                d[i][j] = INF;
            }
        }
        d[start.x][start.y] = 0;
        Queue<Point> q = new ArrayDeque<Point>();
        q.add(start);
        while (!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.equals(finish)) {
                break;
            }
            int cx = cur.x;
            int cy = cur.y;
            for (int dir = 0; dir < 4; dir++) {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];
                if (good(nx, ny) && a[nx][ny] != '1') {
                    if (d[nx][ny] > d[cx][cy] + 1) {
                        d[nx][ny] = d[cx][cy] + 1;
                        q.add(new Point(nx, ny));
                    }
                }
            }
        }
        return d[finish.x][finish.y];
    }

    int whereNeedToGo(Point start, Point finish) {
        int[][] d = new int[n][m];
        int[][] p = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                d[i][j] = INF;
                p[i][j] = -1;
            }
        }
        d[start.x][start.y] = 0;
        Queue<Point> q = new ArrayDeque<Point>();
        q.add(start);
        while (!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.equals(finish)) {
                break;
            }
            int cx = cur.x;
            int cy = cur.y;
            for (int dir = 0; dir < 4; dir++) {
                int nx = cx + dx[dir];
                int ny = cy + dy[dir];
                if (good(nx, ny) && a[nx][ny] != '1') {
                    if (d[nx][ny] > d[cx][cy] + 1) {
                        d[nx][ny] = d[cx][cy] + 1;
                        p[nx][ny] = dir;
                        q.add(new Point(nx, ny));
                    }
                }
            }
        }
        if (start.equals(finish)) {
            return rnd.nextInt(4);
        }
        int x = finish.x;
        int y = finish.y;
        if (p[x][y] == -1) {
            return rnd.nextInt(4);
        }
        while (true) {
            int px = x - dx[p[x][y]];
            int py = y - dy[p[x][y]];
            if (px == start.x && py == start.y) {
                return p[x][y];
            }
            x = px;
            y = py;
        }
    }

    Point randomDestinationPoint(int pointIndex) {
        Point best = null;
        int oneBotNeedDist = (n + m) / 10 * 7;
        for (int it = 0; it < 100; it++) {
            int x = rnd.nextInt(n);
            int y = rnd.nextInt(m);
            if (!good(x, y)) {
                continue;
            }
            if (a[x][y] != '0') {
                continue;
            }
            Point p = new Point(x, y);
            int sumDist = 0;
            int botCount = 0;
            for (int i = pointIndex; i < myBots.size(); i += destPointCount) {
                botCount++;
                Bot bot = myBots.get(i);
                Point botPoint = new Point(bot.x, bot.y);
                int distance = shortestPath(botPoint, p);
                sumDist += distance;
            }
            if (best == null) {
                best = p;
            }
            if (sumDist >= oneBotNeedDist * botCount) {
                break;
            }
        }
        return best;
    }

    void printArrayToLog() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                textLog.print(a[i][j] + " ");
            }
            textLog.println();
        }
        textLog.println();
        textLog.flush();
    }

    void removeDeadBots() {
        List<Bot> myAliveBots = new ArrayList<Bot>();
        List<Bot> enemyAliveBots = new ArrayList<Bot>();
        for (Bot myBot : myBots) {
            if (myBot.alive) {
                myAliveBots.add(myBot);
            }
        }
        for (Bot enemyBot : enemyBots) {
            if (enemyBot.alive) {
                enemyAliveBots.add(enemyBot);
            }
        }
        myBots = myAliveBots;
        enemyBots = enemyAliveBots;
    }

    void sendData() throws Exception {
        JSONObject sent = new JSONObject();
        for (Bot bot : myBots) {
            if (!bot.alive) {
                continue;
            }
            String botName = bot.botName;
            Point firePoint = fireMap.get(botName);
            Character moveChar = moveMap.get(botName);
            JSONObject botJSONObject = new JSONObject();
            JSONArray botFireArray = new JSONArray();
            if (firePoint != null) {
                addPoint(firePoint, botFireArray);
            } else {
                //debug("Move number = " + moveNumber + ": bot '" + botName + "' doesn't shoot!");
            }
            botJSONObject.put("fire", botFireArray);
            if (moveChar != null) {
                if (Character.isUpperCase(moveChar)) {
                    moveChar = Character.toLowerCase(moveChar);
                }
                botJSONObject.put("move", Character.toString(moveChar));
            } else {
                botJSONObject.put("move", "s");
                //debug("Move number = " + moveNumber + ": bot '" + botName + "' doesn't move!");
            }
            sent.put(botName, botJSONObject);
        }
        out.println(sent);
        out.flush();
    }

    void receiveBotsInfo() throws Exception {
        JSONObject received = null;
        try {
            received = new JSONObject(in.readLine());
            debug("Bots info: " + received);
            moveNumber = received.getInt("turn_no");
            JSONObject playersInfo = received.getJSONObject("players");
            parsePlayersInfo(playersInfo);
            if (received.has("bots")) {
                JSONObject botsInfo = received.getJSONObject("bots");
                parseBotsInfo(botsInfo);
            }
            JSONArray emptyCellsArray = received.getJSONArray("empty");
            for (int i = 0; i < emptyCellsArray.length(); i++) {
                JSONArray pointArray = emptyCellsArray.getJSONArray(i);
                Point point = getPoint(pointArray);
                int x = point.x;
                int y = point.y;
                a[x][y] = '0';
            }
        } catch (Exception e) {
            errorsCount++;
            PrintWriter pw = new PrintWriter("error" + errorsCount + ".log");
            pw.println("Bots info: " + (received==null?"null":received.toString()));
            e.printStackTrace(pw);
            pw.close();
            throw e;
        }
    }

    static int errorsCount = 0;

    void parseBotsInfo(JSONObject botsInfo) throws Exception {
        if (botsInfo == null) {
            return;
        }
        if (botsInfo.length() == 0) {
            return;
        }
        String[] botNames = JSONObject.getNames(botsInfo);
        if (botNames == null) {
            return;
        }
        for (String botName : botNames) {
            JSONObject botInfo = botsInfo.getJSONObject(botName);
            parseSingleBot(botName, botInfo);
        }
    }

    Point getPoint(JSONArray pointArray) throws Exception {
        int x = pointArray.getInt(1);
        int y = pointArray.getInt(0);
        return new Point(x, y);
    }

    void addPoint(Point point, JSONArray pointArray) throws Exception {
        int x = point.x;
        int y = point.y;
        pointArray.put(0, y);
        pointArray.put(1, x);
    }

    void parseSingleBot(String botName, JSONObject botInfo) throws Exception {
        String playerName = botInfo.getString("player");
        JSONArray position = botInfo.getJSONArray("position");
        Point botPoint = getPoint(position);
        int x = botPoint.x;
        int y = botPoint.y;
        int hp = botInfo.getInt("health");
        int respawnTime = botInfo.getInt("time");
        JSONArray canShootArray = botInfo.getJSONArray("can_shoot");
        List<Point> canShootList = new ArrayList<Point>();
        for (int i = 0; i < canShootArray.length(); i++) {
            JSONArray pointArray = canShootArray.getJSONArray(i);
            Point canShootPoint = getPoint(pointArray);
            canShootList.add(canShootPoint);
        }
        Bot bot = new Bot(botName, playerName, x, y, hp, respawnTime, canShootList);
        if (bot.playerName.equals(myName)) {
            myBots.add(bot);
        } else {
            enemyBots.add(bot);
        }
    }

    void parsePlayersInfo(JSONObject playersInfo) throws Exception {
        String[] playerNamesArray = JSONObject.getNames(playersInfo);
        for (String playerName : playerNamesArray) {
            JSONObject playerData = playersInfo.getJSONObject(playerName);
            int score = playerData.getInt("score");
            scores.put(playerName, score);
            playerNames.add(playerName);
        }
    }

    void receiveFieldInfo() throws Exception {
        JSONObject received = new JSONObject(in.readLine());
        myName = received.getString("user_id");
        n = received.getInt("width");
        m = received.getInt("height");
        a = new char[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = '0';
            }
        }
        JSONArray bricksArray = received.getJSONArray("bricks");
        for (int i = 0; i < bricksArray.length(); i++) {
            JSONArray pointArray = bricksArray.getJSONArray(i);
            Point point = getPoint(pointArray);
            int x = point.x;
            int y = point.y;
            a[x][y] = '1';
        }
    }

    void receiveConnectionSuccess() throws Exception {
        JSONObject received = new JSONObject(in.readLine());
        if (!received.getString("status").equals("ok") || !received.getString("message").equals("logged in")) {
            throw new RuntimeException("Status = " + received.getString("status") + ", message = " + received.getString("message"));
        }
        log("Connection succeeded!");
    }

    void receiveConnectionApprove() throws Exception {
        JSONObject received = new JSONObject(in.readLine());
        if (!received.getString("status").equals("ok") || !received.getString("message").equals("ready for login")) {
            throw new RuntimeException("Status = " + received.getString("status") + ", message = " + received.getString("message"));
        }
        log("Connection approved!");
        JSONObject sent = new JSONObject();
        sent.put("message_type", "login");
        sent.put("game_token", GAME_TOKEN);
        sent.put("user_token", USER_TOKEN);
        out.println(sent);
        out.flush();
        log("Game data sent!");
    }

}