Adv2016/D24.1/Program.cs

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

namespace D24._1
{
    public class Program
    {
        public static int Solve(bool[][] map, (int, int) start, (int, int) goal)
        {
            var queue = new Queue<((int x, int y) coord, int steps)>();
            HashSet<(int, int)> visited = new HashSet<(int, int)>();

            queue.Enqueue((start, 0));

            while (queue.Count > 0)
            {
                var (coord, steps) = queue.Dequeue();

                if (coord == goal)
                    return steps;

                foreach ((int mx, int my) in Move)
                {
                    (int x, int y) ncoord = (coord.x + mx, coord.y + my);
                    if (map[ncoord.y][ncoord.x]) continue;

                    if (visited.Contains(ncoord)) continue;
                    visited.Add(ncoord);

                    queue.Enqueue((ncoord, steps + 1));
                }
            }

            throw new Exception();
        }

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

        static void Main(string[] args)
        {

            var file = File.ReadAllText(args[0]).Split(new[] { "\n", "\r\n" }, StringSplitOptions.RemoveEmptyEntries);

            var poi = new Dictionary<int, (int x, int y)>();

            var map = ParseMap(file, poi);

            var perm = GetPermutations(poi.Keys.OrderBy(p => p).Skip(1), poi.Count - 1);

            int minStep = int.MaxValue;
            foreach (var p in perm)
            {
                var current = 0;
                int step = 0;
                foreach (var destination in p)
                {
                    step += Solve(map, poi[current], poi[destination]);
                    current = destination;
                }

                if (step < minStep) minStep = step;
            }

            Console.WriteLine($"The answer is : {minStep}");
        }

        public static bool[][] ParseMap(string[] file, Dictionary<int, (int x, int y)> poi)
        {
            bool[][] map = new bool[file.Length][];

            int l = 0;
            foreach (string line in file)
            {
                map[l] = new bool[line.Length];
                for (var i = 0; i < line.Length; ++i)
                {
                    if (line[i] >= '0' && line[i] <= '9') poi.Add(line[i] - '0', (i, l));
                    map[l][i] = line[i] == '#';
                }
                l++;
            }

            return map;
        }

        public static IEnumerable<IEnumerable<int>> GetPermutations(IEnumerable<int> list, int length)
        {
            if (length == 1) return list.Select(t => new [] { t });

            return GetPermutations(list, length - 1).SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new [] { t2 }));
        }
    }
}