codingame

gistfile1.js

'use strict';

var inputs = readline().split(' ');

var players = {
    list: [],

    meId: parseInt(inputs[3]), // id of my player (0 = 1st player, 1 = 2nd player, ...)
    me: {},

    playerCount: parseInt(inputs[2]), // number of players (2,3, or 4), still presente when of board.

    isBlocked: function() {
        var block = false;

        for (var i = 0; i < players.list.length; i++) {
            if(players.list[i].excapeIndex === -1) { // A user is blocked
                block = true;
                break;
            }
        }

        return block;
    },

    getEnemy: function(playerMe) {
        var output = [];

        for (var i = 0; i < players.list.length; i++) {
            var current = players.list[i];

            if (current.id !== playerMe.id) {
                output.push(current);
            }
        }

        output.sort(function(a, b) { // ASC
            return a.excapeDistance - b.excapeDistance;
        });

        return output;
    },

    updateBestPath: function() {
        for (var i = 0; i < players.list.length; i++) {
            var player = players.list[i];
            var excapeXY = getExcapeXY(player.id);
            var bfs = getBFS(board.indexLength, player.index, excapeXY.x, excapeXY.y);

            player.previousNode = bfs[1];
            player.excapeIndex = bfs[0];
            player.excapeDistance = players.getNextIndex(player)[1];
        }
    },

    updateActionsWallBlock: function() {
        var i;
        var player;

        for (i = 0; i < players.list.length; i++) {
            player = players.list[i];

            var actions = getActionsWallBlockMove(player);
            player.actionsWallBlock = actions.filter(function (action) {
                return board.canAddWall(action.x, action.y, action.D);
            });
        }

        for (i = 0; i < players.list.length; i++) {
            player = players.list[i];

            var slotAvailable = 3;

            player.actionsWallBlock = player.actionsWallBlock.filter(function (action) {
                if(slotAvailable > 0) {
                    board.setAction(false, action, true);
                    board.removeAction(false, action);

                    if(!players.isBlocked()) {
                        slotAvailable--;
                        return true;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            });
        }

        players.updateBestPath(); // Reset state players
    },

    getNextIndex: function(player) {
        var nextIndex = player.excapeIndex;
        var excapeDistance = -1;

        if(nextIndex !== -1) {
            excapeDistance = 0;

            if(nextIndex !== player.index) {
                while(true) {
                    excapeDistance++;

                    if(player.index !== player.previousNode[nextIndex]) {
                        nextIndex = player.previousNode[nextIndex];
                    } else {
                        break;
                    }

                    if(excapeDistance > 200) {
                        printErr('too much ' + player.id + ' ' + player.index + ' ' + nextIndex + ' ' + player.excapeIndex);
                        nextIndex = -1;
                        break;
                    }
                }
            }
        }

        return [nextIndex, excapeDistance];
    },
};

var board = {
    walls: {},

    width: parseInt(inputs[0]), // width of the board
    height: parseInt(inputs[1]), // height of the board
    indexLength: parseInt(inputs[0]) * parseInt(inputs[1]),

    // The assumption is that for each node the evaluation function returns a vector
    // H of n values where hiestimates the merit of player i.
    // An evaluation function returns an estimate of the expected utility of the game
    // from a given position. Should be strongly correlated with the actual chances of winning
    getEval: function() {
        var vector = [];

        for (var i = 0; i < players.list.length; i++) {
            var player = players.list[i];
            var gain = 0;
            var playersEnemy = players.getEnemy(player);

            var distance = 0;
            var block = 0;
            var wallsLeft = 0;

            for (var j = 0; j < playersEnemy.length; j++) {
                var playerCurrent = playersEnemy[j];
                distance += playerCurrent.excapeDistance;
                block += playerCurrent.actionsWallBlock.length;
                wallsLeft += playerCurrent.wallsLeft;
            }

            if(player.excapeDistance === 0) { // We arrived
                gain = 10;
            } else if(player.actionsWallBlock.length === 0 && player.excapeDistance < playersEnemy[0].excapeDistance) {
                gain = 10;
            } else if(wallsLeft === 0 && player.excapeDistance < playersEnemy[0].excapeDistance) {
                gain = 10;
            } else {
                distance -= player.excapeDistance;
                block -= player.actionsWallBlock.length;
                wallsLeft = player.wallsLeft - wallsLeft;

                distance /= 81;
                block /= 4;
                wallsLeft /= 20;

                gain = 5 * distance + 1 * block + wallsLeft * 3;
            }

            vector.push(Math.round(gain * 1e5) / 1e5);
        }

        return vector;
    },

    resetWalls: function() {
        for (var i = 0; i < board.indexLength; i++) {
            board.walls[i] = {
                V: false,
                H: false,
            };
        }       
    },

    setAction: function(playerBy, action, updateBestPath) {
        if(action.type === 'wall') {
            board.walls[action.x + board.width * action.y][action.D] = true;
            
            if(playerBy) {
                playerBy.wallsLeft--;
            }

            if(updateBestPath) {
                players.updateBestPath();
            }
        } else { // move
            if(playerBy) {
                playerBy.index = action.to;

                if(updateBestPath) {
                    playerBy.excapeDistance--;
                }
            }
        }
    },

    removeAction: function(playerBy, action, updateBestPath) {
        if(action.type === 'wall') {
            board.walls[action.x + board.width * action.y][action.D] = false;
            
            if(playerBy) {
                playerBy.wallsLeft++;
            }

            if(updateBestPath) {
                players.updateBestPath();
            }
        } else { // move
            if(playerBy) {
                playerBy.index = action.from;

                if(updateBestPath) {
                    playerBy.excapeDistance++;
                }
            }
        }
    },

    isWallExist: function(index, direction) {
        var wall = board.walls[index];

        if(wall && wall[direction]) {
            return true;
        } else {
            return false;
        }
    },

    canAddWall: function(x, y, D) {
        var output = true;

        if (D === 'V') {
            if(x < 0 || x > board.width - 1 || y < 0 || y >= board.height - 1 ||
            board.isWallExist(x - 1 + board.width * (y + 1), 'H') ||
            board.isWallExist(x + board.width * (y - 1), 'V') ||
            board.isWallExist(x + board.width * (y + 1), 'V')) {
                output = false;
            }
        } else { // H
            if(x < 0 || x >= board.width - 1 || y < 0 || y > board.height - 1 ||
            board.isWallExist(x + 1 + board.width * (y - 1), 'V') ||
            board.isWallExist(x - 1 + board.width * y, 'H') ||
            board.isWallExist(x + 1 + board.width * y, 'H')) {
                output = false;
            }
        }

        return output;
    },

    canMove: function(index, direction) {
        var output = true;

        switch(direction) {
            case 'UP':
                if (index < board.width ||
                board.isWallExist(index - 1, 'H') ||
                board.isWallExist(index, 'H')) {
                   output = false;
                }

                break;
            case 'DOWN':
                if (index + board.width >= board.indexLength ||
                board.isWallExist(index + board.width, 'H') ||
                board.isWallExist(index + board.width - 1, 'H')) {
                   output = false;
                }
                break;
            case 'LEFT':
                if (index % board.width === 0 ||
                board.isWallExist(index, 'V') ||
                board.isWallExist(index - board.width, 'V')) {
                   output = false;
                }
                break;
            case 'RIGHT':
                if (index % board.width === board.width - 1 ||
                board.isWallExist(index + 1, 'V') ||
                board.isWallExist(index + 1 - board.width, 'V')) {
                   output = false;
                }
                break;
        }

        return output;
    },
};

var pathCount = 0;

function getBFS(N, source, exitX, exitY) {
    pathCount++;

    //An array of all the nodes at the same depth
    var nodes = [source];
    var previousNode = {};
    var u;
    var x;
    var y;

    //While the array is not empty
    while(nodes.length > 0) {
        u = nodes.shift();
        x = u % board.width;
        y = (u - x) / board.width;

        if(x === exitX || y === exitY) {
            return [u, previousNode];
        }

        var next;

        next = u - 1;
        if (!(next in previousNode) && board.canMove(u, 'LEFT')) {
            nodes.push(next);
            previousNode[next] = u;
        }

        next = u + board.width;
        if (!(next in previousNode) && board.canMove(u, 'DOWN')) {
            nodes.push(next);
            previousNode[next] = u;
        }

        next = u + 1;
        if (!(next in previousNode) && board.canMove(u, 'RIGHT')) {
            nodes.push(next);
            previousNode[next] = u;
        }

        next = u - board.width;
        if (!(next in previousNode) && board.canMove(u, 'UP')) {
            nodes.push(next);
            previousNode[next] = u;
        }
    }

    return [-1, {}];
}

function getDirectionFromIndexs(nextIndex, index) {
    var output;
    var diffIndex = nextIndex - index;

    if(diffIndex > 0) {
        if(diffIndex === 1) {
            output = 'RIGHT';
        } else {
            output = 'DOWN';
        }
    } else {
        if(diffIndex === -1) {
            output = 'LEFT';
        } else {
            output = 'UP';
        }
    }

    return output;
}

function getExcapeXY(id) {
    var excapeXY = {};

    switch(id) {
        case 0:
            excapeXY.x = 8;
            excapeXY.y = false;
            break;
        case 1:
            excapeXY.x = 0;
            excapeXY.y = false;
            break;
        case 2:
            excapeXY.x = false;
            excapeXY.y = 8;
            break;
    }

    return excapeXY;
}

function getActionWallDefense(playerBy, playersEnemy) {
    var actionsDefense = [];

    var i;
    var wallsEnemy = 0;

    for (i = 0; i < playersEnemy.length; i++) {
        wallsEnemy += playersEnemy[i].wallsLeft;
    }

    var actions = playerBy.actionsWallBlock;

    if (playerBy.wallsLeft >= 1 && wallsEnemy >= 1 && actions.length > 0) { // We can and should
        actions = getActionsWallBlockWall(actions);

        actions = actions.filter(function (action) {
            return board.canAddWall(action.x, action.y, action.D);
        });

        var slotAvailable = 1;

        actions = actions.filter(function (action) {
            var keep = false;

            if(slotAvailable > 0) {
                var excapeBefore = playerBy.excapeDistance;
                board.setAction(false, action, true);
                var excapeAfter = playerBy.excapeDistance;

                if(excapeBefore >= excapeAfter && !players.isBlocked()) {
                    actionsDefense.push(action);
                    // printErr('WallDefense ' + playerBy.id + ' ' + action.x + ' ' + action.y + ' ' + action.D);
                    slotAvailable--;
                    keep = true;
                }
    
                board.removeAction(false, action, true);
            }

            return keep;
        });

        // board.setAction(false, actionsToBlock, true);

        // actions = getActionsWallBlockMove(playerBy);
        // actions = actions.filter(function (action) {
        //     return board.canAddWall(action.x, action.y, action.D);
        // });

        // for (i = 0; i < actions.length; i++) {
        //     var action = actions[i];

        //     board.setAction(false, action, true);

        //     if(playerBy.excapeIndex === -1) {
        //         board.removeAction(false, actionsToBlock, true);

        //         if(!players.isBlocked()) {
        //             actionDefense = action;
        //             break;
        //         }

        //         board.setAction(false, actionsToBlock);
        //     }

        //     board.removeAction(false, actionsToBlock);
        // }

        // board.removeAction(false, actionsToBlock, true);
     
        // if(actionsDefense.length > 0) {
        //     printErr('WallDefense ' + playerBy.id + ' in ' + actionsToBlock.x + ' ' + actionsToBlock.y + ' ' + actionsToBlock.D + ' out ' + actionDefense.x + ' ' + actionDefense.y + ' ' + actionDefense.D);
        // } else {
        //     printErr('WallDefense no');
        // }
    }

    return actionsDefense;
}

function getActionsWallBlockWall(actionsToBlock) {
    var actions = [];

    for(var i = 0; i < actionsToBlock.length; i++) {
        var actionToBlock = actionsToBlock[i];
        var x = actionToBlock.x;
        var y = actionToBlock.y;

        if(actionToBlock.D === 'H') {
            actions.push({type: 'wall', x: x + 1, y: y - 1, D: 'V'});
            actions.push({type: 'wall', x: x - 1, y: y, D: 'H'});
            actions.push({type: 'wall', x: x + 1, y: y, D: 'H'});
        } else { // V
            actions.push({type: 'wall', x: x - 1, y: y + 1, D: 'H'});
            actions.push({type: 'wall', x: x, y: y - 1, D: 'V'});
            actions.push({type: 'wall', x: x, y: y + 1, D: 'V'});
        }
    }

    return actions;
}

function getActionsWallBlockMove(player) {
    var actions = [];
    var indexStart = player.index;

    while (player.index !== player.excapeIndex) {
        var x = player.index % board.width;
        var y = (player.index - x) / board.width;

        var nextIndex = players.getNextIndex(player)[0];
        var direction = getDirectionFromIndexs(nextIndex, player.index);

        switch(direction) {
            case 'UP':
                actions.push({type: 'wall', x: x - 1, y: y, D: 'H'});
                actions.push({type: 'wall', x: x, y: y, D: 'H'});
                break;
            case 'DOWN':
                actions.push({type: 'wall', x: x - 1, y: y + 1, D: 'H'});
                actions.push({type: 'wall', x: x, y: y + 1, D: 'H'});
                break;
            case 'LEFT':
                actions.push({type: 'wall', x: x, y: y - 1, D: 'V'});
                actions.push({type: 'wall', x: x, y: y, D: 'V'});
                break;
            case 'RIGHT':
                actions.push({type: 'wall', x: x + 1, y: y - 1, D: 'V'});
                actions.push({type: 'wall', x: x + 1, y: y, D: 'V'});
                break;
        }

        player.index = nextIndex;
    }

    player.index = indexStart;

    return actions;
}

// Wall to block enemy
function getActionsToTry(playerBy) {
    var playersEnemy = players.getEnemy(playerBy);

    var actions = [];

    var actionMove = {
        type: 'move',
        from: playerBy.index,
        to: players.getNextIndex(playerBy)[0],
    };

    if(playerBy.wallsLeft >= 1) {
        actions = actions.concat(playersEnemy[0].actionsWallBlock);

        if (playersEnemy.length === 2) {
            actions = actions.concat(playersEnemy[1].actionsWallBlock); 
        }

        actions = actions.concat(getActionWallDefense(playerBy, playersEnemy));
    }

    actions.unshift(actionMove); // At the beginning

    return actions;
}

function toStringAction(playerBy, action) {
    var output = '';

    if(action) {
        if(action.type === 'move') {
            output = playerBy.id + ' : ' + getDirectionFromIndexs(action.to, action.from);
        } else {
            output = playerBy.id + ' : ' + action.x + ' ' + action.y + ' ' + action.D;
        }
    } else {
        output = playerBy.id + ' : no';
    }

    return output;
}

function dotProduct(vector1, vector2) {
    var value = 0;

    for (var i = 0; i < vector2.length; i++) {
        value += vector1[i] * vector2[i];
    }

    return value;
}

function dot(matrix, vector) {
    var output = [];

    for (var i = 0; i < vector.length; i++) {
        output.push(dotProduct(matrix[i], vector));
    }

    return output;
}

// Players paths and block should be up to date when arriving here.
function SOS(depth, player) {
    var tree = {
        player: player.id,
        depth: depth,
        childs: [],
    };

    if(depth === 0) {
        return [false, dot(social, board.getEval())]; // Perceived evaluation
    }

    var bestEvaluation = [-1000, -1000, -1000];
    var bestAction = false;

    var playerIndex = players.list.indexOf(player);
    var playerNext = players.list[(playerIndex + 1) % players.list.length];

    var actionsChild = getActionsToTry(player);

    // printErr('playerIndex ' + playerIndex + ' depth ' + depth + ' actionsChild ' + actionsChild.length);

    if (actionsChild.length > 0) {
        for(var i = 0; i < actionsChild.length; i++) {
            var action = actionsChild[i];

            board.setAction(player, action, true);

            var child = {
                action: toStringAction(player, action),
                excape: player.excapeDistance,
            };

            if(player.excapeDistance === 0) { // We arrived
                bestEvaluation = dot(social, board.getEval());
                bestAction = action;

                board.removeAction(player, action);
                break;
            }

            players.updateActionsWallBlock();
            var sos = SOS(depth - 1, playerNext);

            child.eval = sos[1];
            child.childs = sos[2];

            if (sos[1][playerIndex] > bestEvaluation[playerIndex]) {
                var oneEnemyEscape = false;

                for(var j = 0; j < sos.length; j++) {
                    if (j !== playerIndex && sos[1][j] >= 10) {
                        oneEnemyEscape = true;
                        break;
                    }
                }

                if(!oneEnemyEscape) {
                    bestEvaluation = sos[1];
                    bestAction = action;
                }
            }

            board.removeAction(player, action);

            tree.childs.push(child);
        }

        if(actionsChild.length > 0 && bestAction === false) { // We have to use on even if it not optimume
            bestEvaluation = sos[1];
            bestAction = action;
        }
    }

    // printErr('playerIndex ' + playerIndex + ' depth ' + depth + ' bestEvaluation ' + JSON.stringify(bestEvaluation));

    return [bestAction, bestEvaluation, tree];
}


var i;
var start;

// game loop
while (true) {   
    // Set players infos
    players.list = [];

    for (i = 0; i < players.playerCount; i++) {
        var inputs = readline().split(' ');
        var x = parseInt(inputs[0]);
        var y = parseInt(inputs[1]);

        if(x > -1) {
            var player = {
                id: i,
                x: x,
                y: y,
                wallsLeft: parseInt(inputs[2]), // number of walls available for the player
                index: x + board.width * y,
            };

            players.list.push(player);

            if(i === players.meId) {
                players.me = player;
            }
        }
    }

    start = new Date();

    // Set walls infos
    board.resetWalls();

    var wallCount = parseInt(readline()); // Number of walls on the board
    for (i = 0; i < wallCount; i++) {
        // x-coordinate of the wall, y-coordinate of the wall, wall orientation ('H' or 'V')
        var inputs = readline().split(' ');

        board.walls[parseInt(inputs[0]) + board.width * parseInt(inputs[1])][inputs[2]] = true;
    }

    pathCount = 0;

    var depth;
    var social;

    if(players.list.length > 2) {
        depth = 2;

        social = [
            [1, -1, -1],
            [-1, 1, -1],
            [-1, -1, 1],
        ];
    } else {
        depth = 3;

        social = [
            [1, 0],
            [0, 1],
        ];
    }

    players.updateBestPath();
    players.updateActionsWallBlock();
    var sos = SOS(depth, players.me);

    printErr('sos vector ' + JSON.stringify(sos[1]));
    // printErr(JSON.stringify(sos[2].childs.length));

    var action = sos[0];

    var end = new Date();
    printErr('Number of pathCount ' + pathCount);
    printErr('Duration of computation ' + (end - start) + ' ms');

    if(action.type === 'move') {
        print(getDirectionFromIndexs(action.to, action.from));
    } else {
        print(action.x + ' ' + action.y + ' ' + action.D);
    }
}