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 Level { get; set; }
            public string Str { get; set; }
            public List<Group> Groups { get; set; }
            public Group() => Groups = new List<Group>();
        }

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

            var prevStr = prev[depth];

            foreach (var prevPos in prevStr.Item2)
                foreach (var t in CombinePossibilities(Str.Replace(prevStr.Item1, prevPos), prev, depth + 1))
                    yield return t;
        }

        static Group Test(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 = Test(level + 1, priority, regex, index);
                    if (childGroup != null) 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 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 = @"^E(N|S(E|N)(W|S)SE)ES$";
            //regex = @"^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$";

            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 tt = Test(0, priority, regex, 0);

            Stack<(int, Group)> groups = new Stack<(int, Group)>();
            groups.Push((0, new Group() { Level = 0, Str = regex }));

            for (var level = 1; level <= maxpar; ++level)
            {
                Group cur = new Group() { Level = level, Str = "" };
                for (var i = 1; i < regex.Length; ++i)
                {
                    if (priority[i] >= level) cur.Str += regex[i];

                    if (priority[i] < level && priority[i - 1] >= level)
                    {
                        cur.Str += regex[i];
                        groups.Push((level, cur));
                        cur = new Group() { Level = level, Str = "" };
                    }
                }
            }

            var prevm1 = new List<(string, IEnumerable<string>)>();

            var sw = Stopwatch.StartNew();

            for (var level = maxpar; level >= 0; --level)
            {
                HashSet<string> all = new HashSet<string>();
                while (groups.Count > 0 && groups.Peek().Item1 == level)
                    all.Add(groups.Pop().Item2.Str);

                var prev = new List<(string, IEnumerable<string>)>(prevm1);

                prevm1.Clear();
                foreach (var a in all)
                {
                    var possibilities = new HashSet<string>();

                    var list = prev.Where(p => a.Contains(p.Item1)).ToList();

                    var res = CombinePossibilities(a, list);

                    foreach (var pp in res)
                    {
                        var ppp = pp.TrimStart('(').TrimEnd(')').Split("|");
                        foreach (var pppp in ppp) possibilities.Add(pppp);
                    }

                    prevm1.Add((a, possibilities));
                }
            }

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);

            List<int> result = new List<int>();
            
            int max = 0;
            foreach (var path in prevm1.First().Item2)
            {
                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;
        }
    }
}