Bandas

bandas.ts

/**
 * Try to survive by not falling off
 **/

 enum Side {
    UP = "UP",
    RIGHT = "RIGHT",
    DOWN = "DOWN",
    LEFT = "LEFT",
}

const opposites: Record<Side, Side> = {
    [Side.UP]: Side.DOWN,
    [Side.DOWN]: Side.UP,
    [Side.LEFT]: Side.RIGHT,
    [Side.RIGHT]: Side.LEFT,
};

enum Cell {
    PLAYER_0 = "0",
    PLAYER_1 = "1",
    EMPTY = "-",
    HOLE = "x",
}

type PlayerCell = Cell.PLAYER_0 | Cell.PLAYER_1;

const opponents: Record<PlayerCell, PlayerCell> = {
    [Cell.PLAYER_0]: Cell.PLAYER_1,
    [Cell.PLAYER_1]: Cell.PLAYER_0,
};

type Board = Cell[][];

const myCell = readline() as Cell.PLAYER_0 | Cell.PLAYER_1; // Your id, 0 or 1
const height: number = parseInt(readline()); // height of the grid
const width: number = parseInt(readline()); // width of the grid

const opponentCell = opponents[myCell];

// game loop
while (true) {
    const timeStart = Date.now();
    const rawBoard = Array.from({ length: height }, () => readline().split(" ") as Cell[]);
    const board = cropBoard(rawBoard);
    debugBoard(board);

    let [bestSide, bestDifference] = weightBoard(board, myCell, 4);

    // Write an action using console.log()
    // To debug: console.error('Debug messages...');

    console.log(bestSide);
    console.error({ time: Date.now() - timeStart });
}

function debugBoard(board: Board) {
    console.error(board.map((row) => row.join(" ")).join("\n"));
}

function weightBoard(board: Board, player: PlayerCell, depth: number, log = true): [Side, number] {
    if (board.every((row) => row.indexOf(opponents[player]) === -1)) {
        // 10 points if we win
        return [Side.UP, 10];
    }
    if (board.every((row) => row.indexOf(player) === -1)) {
        // -10 points if we lose
        return [Side.UP, -10];
    }
    let bestSide = Side.UP;
    let bestDifference = -Infinity;
    for (const side of Object.values(Side)) {
        const count = countSide(board, side, player);
        const difference = count[1] - count[0];

        let totalDifference = difference;
        if (depth > 1) {
            const nextBoard = cropBoard(evaluatePush(board, player, side));
            if (log) console.error("Next board after", side);
            if (log) debugBoard(nextBoard);
            const [_, nextDifference] = weightBoard(nextBoard, opponents[player], depth - 1, false);
            totalDifference = difference - nextDifference;
        }

        if (log)
            console.error({
                side,
                count,
                difference,
                totalDifference,
            });
        if (totalDifference > bestDifference) {
            bestSide = side;
            bestDifference = totalDifference;
        }
    }
    return [bestSide, bestDifference];
}

function cropBoard(board: Board): Board {
    const rowRange = () => Array.from(board, (_, i) => i);
    const colRange = () => Array.from(board[0], (_, i) => i);

    const isPlayer = (cell: Cell) => cell === Cell.PLAYER_0 || cell === Cell.PLAYER_1;

    const startRow = rowRange().find((i) => colRange().some((j) => isPlayer(board[i][j])));
    const endRow = rowRange()
        .reverse()
        .find((i) => colRange().some((j) => isPlayer(board[i][j])));
    const startCol = colRange().find((j) => rowRange().some((i) => isPlayer(board[i][j])));
    const endCol = colRange()
        .reverse()
        .find((j) => rowRange().some((i) => isPlayer(board[i][j])));

    return board.slice(startRow, endRow + 1).map((row) => row.slice(startCol, endCol + 1));
}

function countSide(board: Board, side: Side, player: PlayerCell): [number, number] {
    const height = board.length;
    const width = board[0].length;
    switch (side) {
        case Side.UP:
            return [
                board[0].filter((cell) => cell === player).length,
                board[0].filter((_, i) =>
                    willBePushed(
                        player,
                        board.map((row) => row[i]),
                    ),
                ).length,
            ];
        case Side.DOWN:
            return [
                board[height - 1].filter((cell) => cell === player).length,
                board[height - 1].filter((_, i) =>
                    willBePushed(player, board.map((row) => row[i]).reverse()),
                ).length,
            ];
        case Side.LEFT:
            return [
                board.filter((row) => row[0] === player).length,
                board.filter((row) => willBePushed(player, row)).length,
            ];
        case Side.RIGHT:
            return [
                board.filter((row) => row[width - 1] === player).length,
                board.filter((row) => willBePushed(player, row.slice().reverse())).length,
            ];
    }
}

function willBePushed(player: PlayerCell, row: Cell[]) {
    if (row[0] !== opponents[player]) return false;
    const meIndex = row.indexOf(player);
    const blankIndex = row.indexOf(Cell.EMPTY);
    if (meIndex === -1) return false;
    if (blankIndex === -1) return true;
    return meIndex < blankIndex;
}

function* eachLine(board: Board, side: Side): Generator<[i: number, j: number, newPush: boolean]> {
    switch (side) {
        case Side.UP:
            for (let j = 0; j < board[0].length; j++) {
                for (let i = board.length - 1; i >= 0; i--) {
                    yield [i, j, i === board.length - 1];
                }
            }
            return;
        case Side.DOWN:
            for (let j = 0; j < board[0].length; j++) {
                for (let i = 0; i < board.length; i++) {
                    yield [i, j, i === 0];
                }
            }
            return;
        case Side.LEFT:
            for (let i = 0; i < board.length; i++) {
                for (let j = board[0].length - 1; j >= 0; j--) {
                    yield [i, j, j === board[0].length - 1];
                }
            }
            return;
        case Side.RIGHT:
            for (let i = 0; i < board.length; i++) {
                for (let j = 0; j < board[0].length; j++) {
                    yield [i, j, j === 0];
                }
            }
            return;
    }
}

function evaluatePush(board: Board, player: Cell, side: Side) {
    const nextBoard = board.map((row) => row.slice());
    let carry: Cell = Cell.EMPTY;
    for (const [i, j, newPush] of eachLine(nextBoard, side)) {
        if (newPush) carry = Cell.EMPTY;
        const cell = nextBoard[i][j];
        const willPush = carry !== Cell.EMPTY || cell === player;
        if (willPush) {
            nextBoard[i][j] = carry;
            carry = cell;
        } else {
            carry = Cell.EMPTY;
        }
    }
    return nextBoard;
}