Adv2018/D20.1/Program.cs

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

namespace D20._1
{
    class Program
    {
        public class Group
        {
            public int Id { get; set; }
            public int Level { get; set; }
            public string Str { get; set; }
            public List<Group> Groups { get; set; }
            public SortedSet<string> Possibilities { get; set; }
            public Group()
            {
                Groups = new List<Group>();
                Possibilities = new SortedSet<string>(new PC());
                Str = "";
                Id = 1;
            }
        }

        class PC : IComparer<string>
        {
            public int Compare(string x, string y) => y.Length.CompareTo(x.Length);
        }

        static IEnumerable<string> CombinePossibilities(string Str, List<Group> children, int depth = 0)
        {
            if (depth == children.Count) { yield return Str; yield break; }

            var child = children[depth];

            foreach (var prevchildPossibility in child.Possibilities)
                foreach (var t in CombinePossibilities(Str.Replace(("(" + (char)child.Id + ")").ToString(), prevchildPossibility), children, depth + 1))
                {
                    if (Str.Contains(((char)child.Id).ToString()) == false) throw new Exception();
                    yield return t;
                }
        }

        static Group BuildGroups(int level, string priority, string regex, int index)
        {
            if (index >= regex.Length) return null;

            var group = new Group() { Level = level, Str = "" };

            bool capture = true;

            while (
                index < regex.Length &&
                priority[index] >= level)
            {
                if (priority[index] > level && capture)
                {
                    capture = false;
                    var childGroup = BuildGroups(level + 1, priority, regex, index);
                    if (childGroup != null)
                    {
                        childGroup.Id = group.Groups.Count + 1;

                        group.Str += "(" + (char)childGroup.Id;
                        group.Groups.Add(childGroup);

                    }
                }
                else if (priority[index] == level)
                {
                    capture = true;
                    group.Str += regex[index];
                }

                index++;
            }

            if (index < regex.Length) group.Str += regex[index];

            return group;
        }

        static void Test(Group root)
        {
            IEnumerable<string> possibilities;
            if (root.Groups.Count == 0)
            {
                var splittedPossibilities = root.Str.TrimStart('(').TrimEnd(')').Split("|");
                foreach (var splittedPossibility in splittedPossibilities) root.Possibilities.Add(splittedPossibility);
                return;
            }

            foreach (var group in root.Groups) Test(group);

            possibilities = CombinePossibilities(root.Str, root.Groups);
            foreach (var possibility in possibilities)
            {
                var splittedPossibilities = possibility.TrimStart('(').TrimEnd(')').Split("|");
                foreach (var splittedPossibility in splittedPossibilities) root.Possibilities.Add(splittedPossibility);
            }
        }

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

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

            //regex = @"^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$";
            regex = @"^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$";
            //regex = @"^N(EEENWWW|N)$";

            regex = regex.TrimStart('^').TrimEnd('$');
            int par = 0, maxpar = 0;
            var priority = "";
            for (var i = 0; i < regex.Length; ++i)
            {
                if (regex[i] == '(')
                {
                    par++;
                    if (par > maxpar) maxpar = par;
                }
                if (regex[i] == ')') par--;
                priority += (char)par;
            }

            var root = BuildGroups(0, priority, regex, 0);

            var sw = Stopwatch.StartNew();

            Test(root);

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);

            int max = 0;
            foreach (var path in root.Possibilities)
            {
                var r = GetResult(path);
                if (r > max) max = r;
            }

            Console.WriteLine(max);
        }

        private static int GetResult(string str)
        {
            (int x, int y) pos = (0, 0);
            HashSet<((int x, int y) from, (int x, int y) to)> doors = new HashSet<((int x, int y) from, (int x, int y) to)>();
            foreach (var c in str)
            {
                var bpos = pos;
                switch (c)
                {
                    case 'N': pos.y -= 1; break;
                    case 'S': pos.y += 1; break;
                    case 'W': pos.x -= 1; break;
                    case 'E': pos.x += 1; break;
                }

                doors.Add((bpos, pos));
                doors.Add((pos, bpos));
            }

            return GetBreadthFirstSearch(doors, pos);
        }


        // https://en.wikipedia.org/wiki/Breadth-first_search
        private static int GetBreadthFirstSearch(HashSet<((int x, int y) from, (int x, int y) to)> doors, (int x, int y) togo)
        {
            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)>()
                    {
                        { (0, 0), (0, 0) }
                    };

            nodesToVisit.Enqueue((0, 0));

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

                // Found it!
                if (node == togo)
                {
                    var count = GetActionList(togo, meta, node);
                    return count;
                }

                foreach ((int mx, int my) mv in new []{ (0, -1), (1, 0), (0, 1), (-1, 0) })
                {
                    (int x, int y) successor = (node.x + mv.mx, node.y + mv.my);

                    // Continue if no door exist
                    if (doors.Contains((node, successor)) == false) continue;

                    if (visitedNodes.Contains(successor)) continue;

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

                visitedNodes.Add(node);
            }

            return -1;
        }

        private static int GetActionList((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);
            }

            return actionList.Count;
        }
    }
}