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);

            Dictionary<(int x, int y), int> positions = new Dictionary<(int x, int y), int>();
            foreach (var path in root.Possibilities)
            {
                TestResult(path, positions);
            }

            int max = positions.Max(p => p.Value);
            Console.WriteLine(max);
        }

        private static void TestResult(string str, Dictionary<(int x, int y), int> positions)
        {
            (int x, int y) pos = (0, 0);
            int dist = 0;

            positions.TryAdd(pos, 0);
            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;
                }

                dist++;
                if (positions.TryAdd(pos, dist) == false)
                    dist = Math.Min(dist + 1, positions[pos]);
                positions[pos] = dist;
            }
        }
    }
}