15.ts

import * as fs from 'fs';

interface Player {
  label: 'G' | 'E';
  hp: number;
  power: number;
  coord: Coord;
}

type Coord = [number, number];

type PlayingMap = Array<Array<string>>;

function coordToString(coord: Coord) {
  const [x, y] = coord;
  return [x, y].join('x');
}

function readingOrder(from: Coord) {
  return (a: Coord, b: Coord) => {
    if (a[1] > from[1] && b[1] < from[1]) return 1;
    if (b[1] > from[1] && a[1] < from[1]) return -1;
    if (a[1] === from[1] && b[1] === from[1]) {
      if (a[0] > from[0] && b[0] < from[0]) return -1;
      if (b[0] > from[0] && a[0] < from[0]) return 1;
    }
    if (a[1] === b[1]) return a[0] - b[0];
    return a[1] - b[1];
  };
}

function d(a: number, b: number) {
  return Math.max(a, b) - Math.min(a, b);
}

function distance(a: Coord, b: Coord) {
  return d(a[0], b[0]) + d(a[1], b[1]);
}

type EachCellCallback = (c: Coord, char: string) => void;
function eachCell(map: PlayingMap, fn: EachCellCallback) {
  map.forEach((line, y) => {
    line.forEach((char, x) => {
      fn([x, y], char);
    });
  });
}

let playersByCoord = new Map<string, Player>();
let players: Player[] = [];
let playerOrder: Coord[] = [];
let tracing = false;
let defaultInPlayCondition = () => {
  const labels = players.map(p => p.label);
  return labels.includes('E') && labels.includes('G');
};
let stillInPlay: () => boolean;

function configureMap(elfPower = 3, inPlayCondition = defaultInPlayCondition) {
  playersByCoord = new Map<string, Player>();
  players = [];
  playerOrder = [];
  stillInPlay = inPlayCondition;

  eachCell(map, ([x, y], char) => {
    if (char === 'E' || char === 'G') {
      const c = coordToString([x, y]);
      const p: Player = {
        coord: [x, y],
        hp: 200,
        power: char === 'E' ? elfPower : 3,
        label: char,
      };
      playersByCoord.set(c, p);
      playerOrder.push([x, y]);
      players.push(p);
      map[y][x] = '.';
    }
  });
}

function cLeft([x, y]: Coord): Coord {
  return [x - 1, y];
}
function cRight([x, y]: Coord): Coord {
  return [x + 1, y];
}
function cUp([x, y]: Coord): Coord {
  return [x, y - 1];
}
function cDown([x, y]: Coord): Coord {
  return [x, y + 1];
}
function around(c: Coord): Coord[] {
  return [cUp(c), cLeft(c), cRight(c), cDown(c)];
}

const enemyFilter = (player: Player) => (other: Player) =>
  other && other.label !== player.label;

function removePlayer(player: Player) {
  const c = coordToString(player.coord);
  playersByCoord.delete(c);
  players = players.filter(p => p !== player);
}

function isFloor(c: Coord): boolean {
  const [x, y] = c;
  const line = map[y];
  if (!line) return false;
  return line[x] === '.' && !playersByCoord.has(coordToString(c));
}

function sortLowestHp(a: Player, b: Player) {
  return a.hp - b.hp;
}

function attack(player: Player): boolean {
  const target = around(player.coord)
    .map(coordToString)
    .map(c => playersByCoord.get(c))
    .filter(enemyFilter(player))
    .sort((a, b) => readingOrder([1, 1])(a.coord, b.coord))
    .sort(sortLowestHp)[0];
  if (!target) return false;
  if (tracing) console.log('Attack!', player.coord, target.coord);
  target.hp -= player.power;
  if (target.hp <= 0) removePlayer(target);
  return true;
}

function movePlayer(player: Player, c: Coord) {
  if (tracing) console.log('Move', player.coord, c);
  const newStr = coordToString(c);
  playersByCoord.delete(coordToString(player.coord));
  player.coord = c;
  playersByCoord.set(newStr, player);
}

function nextTo(a: Coord) {
  return (b: Coord) => distance(a, b) === 1;
}

function calcPath(from: Coord, to: Coord[]): Coord[] {
  const foundTos: Coord[] = [];
  let currentCoords: Coord[] = around(from).filter(isFloor);
  let prevCoords: Array<Coord[]> = [[from]];

  const prevCoordSet = new Set<string>(
    currentCoords.concat([from]).map(coordToString)
  );

  while (true) {
    currentCoords.forEach(c => {
      to.forEach(t => {
        if (nextTo(c)(t)) {
          foundTos.push(c);
        }
      });
    });

    if (foundTos.length > 0) {
      break;
    }

    currentCoords.forEach(c => prevCoordSet.add(coordToString(c)));
    const nextCoords = currentCoords.reduce((acc: Coord[], c) => {
      const cc = around(c).filter(
        a => !prevCoordSet.has(coordToString(a)) && isFloor(a)
      );
      cc.forEach(a => prevCoordSet.add(coordToString(a)));
      return acc.concat(cc);
    }, []);
    if (nextCoords.length === 0) break;
    prevCoords.unshift(currentCoords);
    currentCoords = nextCoords;
  }

  if (foundTos.length > 0) {
    const foundTo = foundTos.sort(readingOrder(from))[0];

    // reverse
    const path: Coord[] = [foundTo];
    while (prevCoords.length > 0) {
      const nextCoords = prevCoords.shift();
      const nextCoord = nextCoords
        .filter(nextTo(path[0]))
        .sort(readingOrder(from))[0];
      path.unshift(nextCoord);
    }

    return path;
  }

  return null;
}

function playerTurn(player: Player) {
  if (attack(player)) return;

  const moveToPositions = players.filter(enemyFilter(player)).map(p => p.coord);
  const movePath = calcPath(player.coord, moveToPositions);

  if (movePath) {
    movePlayer(player, movePath[1]);
    attack(player);
  }
}

function turn() {
  let returning = true;

  const po = playerOrder.slice();
  po.forEach((coord, idx) => {
    const player = playersByCoord.get(coordToString(coord));
    if (player) playerTurn(player);
    if (idx < po.length - 1 && !stillInPlay()) {
      returning = false;
      if (tracing) console.log('ended before full turn');
    }
  });

  playerOrder = players
    .map(p => p.coord)
    .sort((a, b) => {
      if (a[1] === b[1]) return a[0] - b[0];
      return a[1] - b[1];
    });

  if (tracing) {
    playerOrder.slice().forEach((coord, idx) => {
      const player = playersByCoord.get(coordToString(coord));
      console.log('Player', idx + 1, `(${player.label})`, coord, player.hp);
    });
  }

  return returning;
}

function draw() {
  map.forEach((line, y) => {
    line.forEach((char, x) => {
      const c = coordToString([x, y]);
      const player = playersByCoord.get(c);
      if (player) {
        process.stdout.write(player.label);
      } else {
        process.stdout.write(char);
      }
    });
    process.stdout.write('\n');
  });
}

let map: PlayingMap;

function loadMap(file: string) {
  map = fs
    .readFileSync(file)
    .toString()
    .split('\n')
    .map(line => line.split(''));
}

function score(turns: number): number {
  return players.reduce((s, p) => s + p.hp, 0) * turns;
}

function play(file: string): number {
  loadMap(file);
  configureMap();

  if (tracing) draw();

  let turns = 0;

  while (stillInPlay()) {
    if (tracing) console.log('Turn', turns);
    if (turn()) {
      turns++;
    }
    if (tracing) draw();
  }

  console.log('Finished after', turns, 'turns');
  if (tracing)
    console.log(
      'HPs:',
      players.map(p => p.hp),
      'or',
      players.reduce((s, p) => s + p.hp, 0)
    );
  return score(turns);
}

function playWithoutElfLosses(file: string): number {
  loadMap(file);
  configureMap();
  const elfCount = players.filter(p => p.label === 'E').length;

  let elfPower = 3;
  while (true) {
    console.log('Trying with elfPower =', elfPower);
    loadMap(file);
    configureMap(elfPower);

    let turns = 0;
    while (stillInPlay()) {
      turn();
      turns++;
    }

    if (players.filter(p => p.label === 'E').length === elfCount) {
      return score(turns);
    } else {
      console.log(
        'Failed, lost',
        elfCount - players.filter(p => p.label === 'E').length,
        'elves',
        'and',
        players.filter(p => p.label === 'G').length,
        'goblins left'
      );
    }

    elfPower++;
  }
}

console.log(27730, play('15test4.txt'));
console.log(36334, play('15test6.txt'));
console.log(39514, play('15test7.txt'));
console.log(27755, play('15test8.txt'));
console.log(28944, play('15test9.txt'));
console.log(18740, play('15test10.txt'));

// Part 1
console.log(play('15.txt'));

// Part 2
console.log(playWithoutElfLosses('15.txt'));