Adv2018/D23.2/Program.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;

namespace D23._2
{
    class Program
    {
        static int Manhattan((int x, int y, int z) a, (int x, int y, int z) b)
        {
            return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y) + Math.Abs(a.z - b.z);
        }

        static int InRange(List<(int x, int y, int z, int r)> nanoList, (int x, int y, int z) coord)
        {
            int count = 0;
            foreach (var n in nanoList)
            {
                int m = Manhattan(coord, (n.x, n.y, n.z));
                if (m <= n.r) count++;
            }
            return count;
        }

        static HashSet<(int x, int y, int z)> tested = new HashSet<(int x, int y, int z)>();
        static (int, (int, int, int)) Test(List<(int x, int y, int z, int r)> nanoList, (int x, int y, int z) coord, int i)
        {
            var point = coord;
            var stack = new List<((int x, int y, int z) pos, int count)>();

            int maxCount = 0;
            (int x, int y, int z) bestPosition = coord;
            int manhattanBest = 0;

            stack.Add((point, 0));

            while (stack.Count > 0)
            {
                stack.Sort((a, b) => b.count.CompareTo(a.count));

                var first = stack.First();
                point = first.pos;
                stack.Remove(first);

                tested.Add(point);

                var count = InRange(nanoList, point);
                if (count > maxCount)
                {
                    maxCount = count;
                    bestPosition = point;
                    manhattanBest = Manhattan(point, (0, 0, 0));
                    stack.RemoveAll(s => s.count < maxCount);
                    Console.Write($"Best is {maxCount} - Manhattan {manhattanBest}                 \r");
                }
                else if (count == maxCount)
                {
                    var pmanhattan = Manhattan(point, (0, 0, 0));
                    if (pmanhattan < manhattanBest)
                    {
                        bestPosition = point;
                        manhattanBest = pmanhattan;
                        stack.RemoveAll(s => s.count < maxCount);
                        Console.Write($"Best is {maxCount} - Manhattan {manhattanBest}                 \r");
                    }
                }
                else continue;

                foreach (var (mx, my, mz) in MovementList)
                {
                    var mpoint = (point.x + mx * i, point.y + my * i, point.z + mz * i);
                    if (tested.Contains(mpoint)) continue;
                    if (stack.Contains((mpoint, count))) continue;
                    stack.Add((mpoint, count));
                }
            }

            return (manhattanBest, bestPosition);
        }

        static (int mx, int my, int mz)[] MovementList = new[] { (0, -1, 0), (0, 1, 0), (-1, 0, 0), (1, 0, 0), (0, 0, -1), (0, 0, 1) };
        static void Main(string[] args)
        {
            if (args.Length < 1) return;
            if (File.Exists(args[0]) == false) return;

            var file = File.OpenText(args[0]);

            var reg = new Regex(@"pos=<([\d-,]+)>, r=(\d+)");

            var nanoList = new List<(int x, int y, int z, int r)>();

            do
            {
                var line = file.ReadLine();
                if (line == null) break;

                var res = reg.Match(line);

                var xyz = res.Groups[1].Value.Split(",").Select(s => int.Parse(s)).ToArray();
                var r = int.Parse(res.Groups[2].Value);

                nanoList.Add((xyz[0], xyz[1], xyz[2], r));
            } while (true);

            file.Close();

            int inRange = 0;
            (int, int, int) best = (0, 0, 0);
            foreach (var n in nanoList)
            {
                int m = InRange(nanoList, (n.x, n.y, n.z));
                if (m > inRange)
                {
                    inRange = m;
                    best = (n.x, n.y, n.z);
                }
            }

            int bestManhattant = 0;
            for (var i = (int) Math.Pow(2, 16); i >= 1; i /= 2)
            {
                Console.Clear();
                Console.WriteLine($"Testing with i = {i}");

                (var manhattan, var nbest) = Test(nanoList, best, i);
                best = nbest;
                bestManhattant = manhattan;
            }

            Console.WriteLine($"\nAnswer is : {bestManhattant}");
        }
    }
}