Adv2018/D15.2/Program.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;

namespace D15._2
{
    abstract class Unit
    {
        private int MaxHP = 200;
        public int HP = 0;
        public (int X, int Y) Coord;
        private (int X, int Y) InitCoord;
        public bool IsHealthy = true;

        public Unit((int x, int y) coord)
        {
            HP = MaxHP;
            InitCoord = coord;
            Coord = InitCoord;
        }

        public abstract int GetAtk();

        public void Move((int mx, int my) mv) => Coord = (Coord.X + mv.mx, Coord.Y + mv.my);

        public void Attack(Unit target)
        {
            target.ReceiveAttack(GetAtk());
        }

        private void ReceiveAttack(int atk)
        {
            HP -= atk;
            if (HP <= 0) IsHealthy = false;
        }

        public void Wololo()
        {
            HP = MaxHP;
            IsHealthy = true;
            Coord = InitCoord;
        }
    }

    class Gob : Unit
    {
        public Gob((int x, int y) coord) : base(coord) { }

        public override int GetAtk()
        {
            return 3;
        }
    }
    class Elf : Unit
    {
        public Elf((int x, int y) coord) : base(coord) { }

        public override int GetAtk()
        {
            return Program.ElfAtk;
        }
    }

    class Map : HashSet<(int x, int y)> { }
    class Units : List<Unit> { }

    class Program
    {
        public static int ElfAtk = 4;

        static readonly (int mx, int my)[] MoveSequence = new[] { (0, -1), (-1, 0), (1, 0), (0, 1) };
        static int round = 0;

        //static bool PRINT = false;

        static void Main(string[] args)
        {
            if (args.Length < 1) return;
            if (File.Exists(args[0]) == false) return;
            var file = File.OpenText(args[0]);

            var map = new Map();
            var strMap = new List<string>();
            var units = new Units();

            FillMap(file, map, strMap, units);

            while (true)
            {
                Console.WriteLine($"Testing atk power of : {ElfAtk}");

                round = 0;
                bool continueCombat = true;
                foreach (var unit in units) unit.Wololo();

                do
                {
                    continueCombat = Tick(map, units);
                    if (continueCombat) round++;

                } while (continueCombat);

                var deadElf = 0;
                foreach (var unit in units)
                    if (unit is Elf && unit.IsHealthy == false) deadElf++;
                if (deadElf == 0) break;

                ElfAtk++;
                Console.WriteLine($"Elves suffered heavy losses...\n");
            }

            Console.WriteLine($"Elves win !");
            TheAnswerIs(units, round);
        }

        private static void TheAnswerIs(Units units, int round)
        {
            var hitPoints = 0;
            foreach (var unit in units)
            {
                Console.WriteLine($"Fighter {unit.GetType().Name} : { (unit.IsHealthy ? $"{unit.HP}HP" : $" - DEAD - ({unit.HP})") }");
                if (unit.IsHealthy) hitPoints += unit.HP;
            }

            Console.WriteLine($"\nCombat ends after { round } rounds with { hitPoints } remaining HP");

            Console.WriteLine($"The answer is : { hitPoints * round }\n");
        }

        private static bool Tick(Map map, Units units)
        {
            units.Sort((a, b) =>
            {
                if (a.Coord.Y == b.Coord.Y) return a.Coord.X - b.Coord.X;
                return a.Coord.Y - b.Coord.Y;
            });

            for (int i = 0; i < units.Count; ++i)
            {
                var unit = units[i];
                if (unit.IsHealthy == false) continue;

                List<Unit> filtered = FilterOnHealthyFoes(units, unit);
                if (filtered == null || filtered.Count == 0) return false;

                var inRange = new Map();

                var unitNeedsToMove = GetTilesInRange(map, inRange, unit, filtered);
                if (unitNeedsToMove) MoveUnit(map, units, unit, inRange);

                var targetHasDied = AttackNearestTarget(unit, filtered);

                // If last target has died we end up the simulation
                if (targetHasDied && filtered.Count == 1)
                {
                    bool isFullRound = true;
                    for (var j = i + 1; j < units.Count; ++j)
                    {
                        if (units[j].IsHealthy == false) continue;
                        isFullRound = false;
                        break;
                    }
                    return isFullRound;
                }
            }

            return true;
        }

        private static bool AttackNearestTarget(Unit unit, List<Unit> filtered)
        {
            var target = GetTarget(unit, filtered);
            if (target != null)
            {
                unit.Attack(target);

                if (target.IsHealthy == false)
                    return true;
            }
            return false;
        }

        private static Unit GetTarget(Unit unit, List<Unit> filtered)
        {
            Unit minHpTarget = null;

            foreach (var mv in MoveSequence)
            {
                (int x, int y) targetc = (unit.Coord.X + mv.mx, unit.Coord.Y + mv.my);
                var target = filtered.FirstOrDefault(f => f.Coord == targetc);
                if (target != default && (minHpTarget == null || target.HP < minHpTarget.HP))
                    minHpTarget = target;
            }

            return minHpTarget;
        }

        private static void MoveUnit(Map map, Units units, Unit unit, Map inRange)
        {
            var inRangeActions = new Dictionary<(int x, int y), List<(int x, int y)>>();

            Parallel.ForEach(inRange, (r) =>
            {
                GetBreadthFirstSearch(unit, map, units, inRangeActions, r);
            });

            if (inRangeActions.Count == 0)
                return;

            var shortest = inRangeActions
                .OrderBy(ir => ir.Value.Count)
                .FirstOrDefault();

            unit.Move(shortest.Value.First());
        }

        // https://en.wikipedia.org/wiki/Breadth-first_search
        private static void GetBreadthFirstSearch(Unit unit, Map map, Units units, Dictionary<(int x, int y), List<(int x, int y)>> inRangeActions, (int x, int y) root)
        {
            var nodesToVisit = new Queue<(int x, int y)>();
            var visitedNodes = new HashSet<(int x, int y)>();
            var meta = new Dictionary<(int x, int y), (int x, int y)>()
                    {
                        { unit.Coord, (0, 0) }
                    };

            nodesToVisit.Enqueue(unit.Coord);

            while (nodesToVisit.Count > 0)
            {
                var node = nodesToVisit.Dequeue();

                // Found it!
                if (node == root)
                {
                    GetActionList(inRangeActions, root, meta, node);
                    break;
                }

                foreach (var mv in MoveSequence)
                {
                    (int x, int y) successor = (node.x + mv.mx, node.y + mv.my);

                    // Continue if successor is not a valid tile
                    if (map.Contains(successor) == false) continue;
                    if (units.FirstOrDefault(u => u.IsHealthy && u.Coord == successor) != default) continue;

                    if (visitedNodes.Contains(successor)) continue;

                    if (nodesToVisit.Contains(successor) == false)
                    {
                        meta.TryAdd(successor, mv);
                        nodesToVisit.Enqueue(successor);
                    }
                }

                visitedNodes.Add(node);
            }
        }

        private static readonly object rangeLock = new object();
        private static void GetActionList(Dictionary<(int x, int y), List<(int x, int y)>> inRangeActions, (int x, int y) root, Dictionary<(int x, int y), (int x, int y)> meta, (int x, int y) node)
        {
            var actionList = new List<(int x, int y)>();

            while (meta[node] != (0, 0))
            {
                var action = meta[node];
                node = (node.x - action.x, node.y - action.y);
                actionList.Add(action);
            }

            actionList.Reverse();

            lock (rangeLock) inRangeActions.Add(root, actionList);
        }

        private static bool GetTilesInRange(Map map, Map inRange, Unit unit, List<Unit> filtered)
        {
            foreach (var foe in filtered)
            {
                foreach (var move in MoveSequence)
                {
                    (int x, int y) nc = (foe.Coord.X + move.mx, foe.Coord.Y + move.my);

                    // Unit has no need to move
                    if (nc.x == unit.Coord.X && nc.y == unit.Coord.Y)
                        return false;

                    if (map.Contains(nc)) inRange.Add(nc);
                }
            }

            return inRange.Count > 0;
        }

        private static List<Unit> FilterOnHealthyFoes(Units units, Unit unit)
        {
            List<Unit> filtered = null;
            switch (unit)
            {
                case var un when un is Gob: filtered = units.Where(u => u is Elf && u.IsHealthy).ToList(); break;
                case var un when un is Elf: filtered = units.Where(u => u is Gob && u.IsHealthy).ToList(); break;
            }

            return filtered;
        }

        private static void FillMap(StreamReader file, Map map, List<string> strMap, Units units)
        {
            int y = 0;
            do
            {
                var line = file.ReadLine();
                if (line == null) break;

                strMap.Add(line);

                for (int x = 0; x < line.Length; ++x)
                {
                    (int x, int y) coord = (x, y);

                    if (line[x] == 'G') units.Add(new Gob(coord));
                    if (line[x] == 'E') units.Add(new Elf(coord));

                    if (line[x] != '#') map.Add(coord);
                }

                y++;

            } while (true);
        }
    }
}