Aoc2018Day15.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Priority_Queue;

internal class Program
{
    private const int infinity = 999;

    public static readonly Point[] offsets =
    {
        new Point(0, -1),
        new Point(-1, 0),
        new Point(1, 0),
        new Point(0, 1)
    };

    public static readonly Dictionary<char, UnitType> unitTypes = new Dictionary<char, UnitType>
    {
        ['E'] = UnitType.Elf,
        ['G'] = UnitType.Goblin
    };

    private static readonly HashSet<Unit> units = new HashSet<Unit>();
    public static int width, height;
    public static Cell[,] cells;
    public static SimplePriorityQueue<Cell> queue = new SimplePriorityQueue<Cell>();
    public static List<Cell> path = new List<Cell>();

    public static bool Simulate(int elfPower)
    {
        var lines = File.ReadAllLines("input.txt");
        height = lines.Length;
        width = lines[0].Length;
        cells = new Cell[height, width];
        units.Clear();

        for (var y = 0; y < height; y++)
        {
            for (var x = 0; x < width; x++)
            {
                var position = new Point(x, y);
                cells[y, x] = new Cell
                {
                    position = position,
                    walkable = lines[y][x] != '#'
                };
                if (unitTypes.TryGetValue(lines[y][x], out var unitType))
                {
                    units.Add(new Unit
                    {
                        cell = cells[y, x],
                        type = unitType
                    });
                }
            }
        }

        //ShowMap();

        for (var round = 0;; round++)
        {
            foreach (var unit in units.OrderBy(u => u.cell.position.y).ThenBy(u => u.cell.position.x).ToList())
            {
                if (unit.hp <= 0)
                {
                    continue;
                }

                Traverse(unit.cell);

                var attackCell = units
                    .Where(u => u.type != unit.type)
                    .SelectMany(u => Neighbors(u.cell, unit.cell))
                    .Distinct()
                    .OrderBy(c => c.distance)
                    .ThenBy(c => c.position.y)
                    .ThenBy(c => c.position.x)
                    .FirstOrDefault();

                if (attackCell == null)
                {
                    continue;
                }

                if (unit.cell != attackCell && ReconstructPath(attackCell))
                {
                    unit.cell = path[0];
                }

                var enemy = units
                    .Where(u => u.type != unit.type && (u.cell.position - unit.cell.position).Length == 1)
                    .OrderBy(u => u.hp)
                    .ThenBy(u => u.cell.position.y)
                    .ThenBy(u => u.cell.position.x)
                    .FirstOrDefault();
                if (enemy != null)
                {
                    var damage = unit.type == UnitType.Goblin ? 3 : elfPower;
                    enemy.hp = Math.Max(0, enemy.hp - damage);
                    if (enemy.hp <= 0)
                    {
                        if (enemy.type == UnitType.Elf)
                        {
                            return false;
                        }

                        units.Remove(enemy);
                    }
                }
            }

            //Console.WriteLine($"after {round} rounds");
            //ShowMap();
            //Console.ReadKey();

            if (units.Count(u => u.type == UnitType.Goblin) == 0)
            {
                ShowMap();
                Console.WriteLine(elfPower);
                //Console.WriteLine(round);
                var sum = units.Sum(u => u.hp);
                Console.WriteLine($"{round * sum} or {(round + 1) * sum}");
                return true;
            }
        }
    }

    public static void Main(string[] args)
    {
        for (var elfPower = 4;; elfPower++)
        {
            if (Simulate(elfPower))
            {
                break;
            }
        }
    }

    public static void ShowMap()
    {
        var rowUnits = new List<Unit>();
        for (var y = 0; y < height; y++)
        {
            rowUnits.Clear();
            for (var x = 0; x < width; x++)
            {
                var point = new Point(x, y);
                var unit = units.FirstOrDefault(u => u.cell == At(point));
                if (unit != null)
                {
                    rowUnits.Add(unit);
                    Console.Write(unit.type == UnitType.Elf ? 'E' : 'G');
                }
                else
                {
                    Console.Write(At(point).walkable ? "." : "#");
                }
            }

            Console.WriteLine("   " + string.Join(", ", rowUnits));
        }

        Console.WriteLine();
    }

    public static Cell At(Point position)
    {
        return cells[position.y, position.x];
    }

    public static IEnumerable<Cell> Neighbors(Cell cell, params Cell[] allowedCells)
    {
        return offsets
            .Select(o => o + cell.position)
            .Where(p => 0 <= p.y && p.y < height && 0 <= p.x && p.x < width)
            .Select(At)
            .Where(c => c.walkable && (allowedCells.Contains(c) || units.All(u => u.cell != c)));
    }

    public static void Traverse(Cell from)
    {
        queue.Clear();
        foreach (var cell in cells)
        {
            if (cell.walkable && units.All(u => u.cell != cell))
            {
                cell.distance = infinity;
                queue.Enqueue(cell, cell.distance);
            }
        }

        from.distance = 0;
        queue.Enqueue(from, 0);

        while (queue.TryDequeue(out var cell))
        {
            foreach (var neighbor in Neighbors(cell).Where(n => n.distance > cell.distance + 1))
            {
                neighbor.distance = cell.distance + 1;
                queue.UpdatePriority(neighbor, neighbor.distance);
            }
        }
    }

    public static bool ReconstructPath(Cell to)
    {
        path.Clear();
        if (to.distance >= infinity)
        {
            return false;
        }

        for (var cell = to; cell != null;)
        {
            path.Insert(0, cell);
            cell = Neighbors(cell).FirstOrDefault(n => n.distance == cell.distance - 1);
        }

        return true;
    }
}

public class Cell
{
    public int distance;
    public Point position;
    public bool walkable;
}

public enum UnitType
{
    Elf,
    Goblin
}

public class Unit
{
    public Cell cell;
    public int hp = 200;
    public UnitType type;

    public override string ToString()
    {
        return (type == UnitType.Elf ? 'E' : 'G') + $"({hp})";
    }
}

public struct Point : IEquatable<Point>
{
    public readonly int x, y;

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

    public bool Equals(Point other)
    {
        return x == other.x && y == other.y;
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }

        return obj is Point other && Equals(other);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (x * 397) ^ y;
        }
    }

    public static Point operator +(Point a, Point b)
    {
        return new Point(a.x + b.x, a.y + b.y);
    }

    public static Point operator -(Point a, Point b)
    {
        return new Point(a.x - b.x, a.y - b.y);
    }

    public int Length => Math.Abs(x) + Math.Abs(y);

    public override string ToString()
    {
        return $"({x}, {y})";
    }
}