Adv2018/D22.2/Program.cs

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

namespace D22._2
{
    class Program
    {
        enum EnumTool
        {
            Neither,
            Torch,
            Climbing
        }

        enum EnumTerrain
        {
            Rocky  = 0,
            Wet    = 1,
            Narrow = 2
        }

        static readonly Dictionary<EnumTerrain, EnumTool[]> AuthTool = new Dictionary<EnumTerrain, EnumTool[]>
        {
            { EnumTerrain.Rocky, new [] { EnumTool.Torch, EnumTool.Climbing } },
            { EnumTerrain.Wet, new [] { EnumTool.Climbing, EnumTool.Neither } },
            { EnumTerrain.Narrow, new [] { EnumTool.Torch, EnumTool.Neither } },
        };

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

        static int Manhattan((int x, int y) a, (int x, int y) b)
        {
            return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y);
        }

        static int UniformCostSearch((int x, int y) start, (int x, int y) goal, int depth)
        {
            var node = start;
            EnumTool tool = EnumTool.Torch;
            int cost = 0;
            var frontier = new List<((int x, int y) node, int cost, EnumTool tool)>();
            var explored = new HashSet<((int x, int y), EnumTool tool)>();

            frontier.Add((node, cost, tool));

            while (frontier.Count > 0)
            {
                frontier.Sort((a, b) => a.cost.CompareTo(b.cost));

                var q = frontier.First();
                frontier.RemoveAt(0);

                cost = q.cost;
                node = q.node;
                tool = q.tool;

                var terrain = graph[node];

                if (node == goal && tool == EnumTool.Torch) return cost;

                explored.Add((node, tool));

                foreach (var ntool in AuthTool[terrain])
                {
                    if (ntool == tool) continue;
                    if (explored.Contains((node, ntool)) == true) continue;

                    frontier.Add((node, cost + 7, ntool));
                }

                foreach (var (mx, my) in MoveSequence)
                {
                    (int x, int y) n = (node.x + mx, node.y + my);
                    if (n.x < 0 || n.y < 0 || n.x > goal.x + 15 || n.y > goal.y + 50) continue;

                    if (explored.Contains((n, tool)) == true) continue;

                    if (graph.ContainsKey(n) == false)
                        ExtendMap(depth, goal, n);

                    var nterrain = graph[n];
                    if (AuthTool[nterrain].Contains(tool) == false) continue;

                    if (frontier.Contains((n, cost + 1, tool)) == false)
                    {
                        frontier.RemoveAll(f => f.node == n && f.cost > cost + 1);
                        frontier.Add((n, cost + 1, tool));
                    }
                }
            }

            return -1;
        }

        static Dictionary<(int, int), int> erosionLevels = new Dictionary<(int, int), int>();
        static Dictionary<(int, int), EnumTerrain> graph = new Dictionary<(int, int), EnumTerrain>();

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

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

            int depth = int.Parse(file.ReadLine().Substring("depth: ".Length));
            int[] arrayCoord = file.ReadLine().Substring("target: ".Length).Split(",").Select(s => int.Parse(s)).ToArray();
            (int x, int y) coord = (arrayCoord[0], arrayCoord[1]);
            file.Close();

            ExtendMap(depth, (0, 0), (0, 0));

            var sw = Stopwatch.StartNew();

            var cost = UniformCostSearch((0, 0), coord, depth);

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);

            Console.WriteLine($"Shortest path costs {cost} minutes");
        }

        private static void ExtendMap(int depth, (int x, int y) coord, (int x, int y) extension)
        {
            ComputeRisk(coord, extension, depth);
        }

        private static void ComputeRisk((int x, int y) coord, (int x, int y) pos, int depth)
        {
            int geo = 0;
            if (pos != (0, 0) && pos != coord)
            {
                if (pos.x == 0) geo = pos.y * 48271;
                else if (pos.y == 0) geo = pos.x * 16807;
                else
                {
                    if (erosionLevels.ContainsKey((pos.x - 1, pos.y)) == false) ComputeRisk(coord, (pos.x - 1, pos.y), depth);
                    if (erosionLevels.ContainsKey((pos.x, pos.y - 1)) == false) ComputeRisk(coord, (pos.x, pos.y - 1), depth);
                    geo = erosionLevels[(pos.x - 1, pos.y)] * erosionLevels[(pos.x, pos.y - 1)];
                }
            }

            int ero = (geo + depth) % 20183;
            EnumTerrain type = (EnumTerrain) (ero % 3);

            erosionLevels.Add(pos, ero);
            graph.Add(pos, type);
        }
    }
}