AOC2018 Day15

day15

const bool ShowSteps = false;
static readonly string[] Input = @"
################################
#########...####################
#########...###########.########
#########G..##########....######
##########..###########...######
#########G...##########...######
#########..G.###########..######
########...#.##########..#######
#######G#..###E######....#######
#######G.....#.######....#######
######...G......##E......#######
####...##.#..G..G.........######
###..........G#####.......####.#
####........G#######...........#
####..G.....#########......#...#
###.........#########........###
##.....G.G..#########......#####
#...G.......#########.........##
#.G.........#########.E.##...###
##.....G.....#######....G#.E...#
##............#####...E.......##
#.G...........E.......#E...##.##
#....G........###########.....##
#......##...#.##################
#.#.........E..##.##############
#.#.......G.......##############
#.###........E....##############
#.####.....###....##############
#.#####......E..################
#######..........###############
#########..####.################
################################
".Split("\r\n".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);

struct Position : IEquatable<Position>, IComparable<Position> {
	public int X { get; set; }
	public int Y { get; set; }
    public Position(int x, int y) => (X, Y) = (x, y);
    public List<Position> Neighbors() => new List<Position> {
        new Position(X, Y - 1),
        new Position(X - 1, Y),
        new Position(X + 1, Y),
        new Position(X, Y + 1),
    };
    
    public static bool operator ==(Position a, Position b) => a.X == b.X && a.Y == b.Y;
    public static bool operator !=(Position a, Position b) => !(a == b);
    public bool Equals(Position other) => this == other;
    public override bool Equals(object other) => other is Position p && Equals(p);
    public override int GetHashCode() => X << 16 | Y;

    public int CompareTo(Position other) => Y == other.Y ? X.CompareTo(other.X) : Y.CompareTo(other.Y);
    public static bool operator <(Position a, Position b) => a.CompareTo(b) < 0;
    public static bool operator >(Position a, Position b) => a.CompareTo(b) > 0;
}
abstract class Piece : IComparable<Piece> {
    public Position Position { get; set; }
	public int X => Position.X;
	public int Y => Position.Y;
	public Piece(int x, int y) => Position = new Position(x, y);
	public int CompareTo(Piece other) => Position.CompareTo(other.Position);
}
class Wall : Piece {
	public override string ToString() => "#";
	public Wall(int x, int y) : base(x, y) { }
}
class Combatant : Piece { 
	public int HP { get; set; } = 200;
	public int ATK { get; }
	public char Team { get; }
	public override string ToString() => this.Team.ToString();
	public bool IsEnemy(Piece? other) => (other is Combatant unit) && unit.Team != Team && unit.HP > 0;
	public Combatant(int x, int y, char team, int atk) : base(x, y) => (Team, ATK) = (team, atk);
}

class Battle {
	public Piece?[,] Board { get; }
	public int Height { get; }
	public int Width { get; }
	public int RoundsComplete { get; private set; } = 0;
	public bool Ended { get; private set; }
	public List<Combatant> Combatants { get; } = new List<Combatant>();

	public Battle(string[] input, IReadOnlyDictionary<char, int> attacks) {
		Board = new Piece?[Height = input.Length, Width = input.Max(i => i.Length)];
		for (int y = 0; y < Height; y++) {
			for (int x = 0; x < Width; x++) {
				char cell = input[y][x];
				if (cell == '#') Board[y,x] = new Wall(x, y);
				else if (char.IsLetter(cell)) {
					var unit = new Combatant(x, y, cell, attacks[cell]);
					Board[y,x] = unit;
					Combatants.Add(unit);
				}
			}
		}
	}

	private void DoMove(Combatant unit) {
		Position dest = unit.Position;
        Position? bestattackpos = null;
		int? bestdist = null;

		var frontier = new Queue<(Position cur, Position prev, Position first, int dist)>();
        foreach (var n in dest.Neighbors()) frontier.Enqueue((n, dest, n, 1));
		var seen = new HashSet<Position> { dest };
		
		while (frontier.Count > 0) {
			var (cur, prev, first, dist) = frontier.Dequeue();
			if (dist > bestdist) break;
			if (seen.Contains(cur)) continue;
			seen.Add(cur);

			if (Board[cur.Y, cur.X] == null) {
                foreach (var n in cur.Neighbors()) frontier.Enqueue((n, cur, first, dist + 1));
			}
			else if (unit.IsEnemy(Board[cur.Y, cur.X])) {
				if (cur == first) break; // already next to an enemy
				if (bestdist == null || prev < bestattackpos) {
					(dest, bestattackpos, bestdist) = (first, prev, dist);
				}
			}
		}

		Board[unit.Y, unit.X] = null;
        unit.Position = dest;
		Board[unit.Y, unit.X] = unit;
	}
	
	private void DoAttack(Combatant unit) {
		var neigbors = unit.Position.Neighbors().Select(p => Board[p.Y, p.X]);
		
		var targets = neigbors.Where(unit.IsEnemy).Cast<Combatant>();
		if (!targets.Any()) return;
		int lowest = targets.Min(t => t.HP);
		var target = targets.First(t => t.HP == lowest);
		
		target.HP -= unit.ATK;
		if (target.HP <= 0) {
			Board[target.Y, target.X] = null;
		}
	}

	public void DoRound() {
		Combatants.Sort();
		try {
			foreach (var unit in Combatants) {
				if (unit.HP <= 0) continue;
				if (!Combatants.Any(unit.IsEnemy)) {
					Ended = true;
					return;
				}
				DoMove(unit);
				DoAttack(unit);
			}
		}
		finally {
			Combatants.RemoveAll(c => c.HP <= 0);
		}
		this.RoundsComplete += 1;
	}
	
	public void Dump() {
		Console.WriteLine("{0} rounds complete {1}", RoundsComplete, Ended ? "(ended)" : "");
		var hps = new List<int>();
		for (int y = 0; y < Height; y++) {
			hps.Clear();
			for (int x = 0; x < Width; x++) {
				if (Board[y, x] is Combatant c) hps.Add(c.HP);
				Console.Write(Board[y, x]?.ToString() ?? ".");
			}
			Console.WriteLine("  " + string.Join(" ", hps));
		}
        if (Ended) {
        	int totalhp = Combatants.Sum(c => c.HP), outcome = totalhp * RoundsComplete;
        	Console.WriteLine("Total HP: {0}, Rounds Complete: {1}, Outcome: {2}", totalhp, RoundsComplete, outcome);
        }
		Console.WriteLine();
	}
}

void Main() {
    var attacks = "GE".ToDictionary(team => team, _ => 3);

	var battle = new Battle(Input, attacks);
	while (!battle.Ended) {
		if (ShowSteps) battle.Dump();
		battle.DoRound();
	}
	battle.Dump();
    
    int elves = Input.Sum(i => i.Count(c => c == 'E'));
    while (true) {
        attacks['E'] += 1;
    	battle = new Battle(Input, attacks);
    	while (!battle.Ended) battle.DoRound();
        if (elves == battle.Combatants.Count(c => c.Team == 'E')) {
            battle.Dump();
            break;
        }
    }
}