Adv2018/D20.1/Program.cs

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

namespace D20._1
{
    class Program
    {
        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 = @"^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$";

            List<int> result = new List<int>();
            Stack<string> queue = new Stack<string>();

            queue.Push(regex.TrimStart('^').TrimEnd('$'));

            while (queue.Count > 0)
            {
                bool hasParenthesis = false;
                int minLength = 0, minIndex = 0;

                var str = queue.Pop();

                int par = 0, index = 0;
                List<int> pipes = new List<int>();
                foreach (var c in str)
                {
                    if (c == '(') par++;
                    if (c == ')')
                    {
                        par--;
                        if (par == 0) break;
                    }

                    if (par == 1 && c == '|')
                    {
                        pipes.Add(index);
                    }

                    if (hasParenthesis == false && par == 1)
                    {
                        minIndex = index;
                        hasParenthesis = true;
                    }

                    if (par != 0) minLength++;

                    index++;
                }

                if (hasParenthesis == false)
                {
                    (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));
                    }

                    result.Add(GetBreadthFirstSearch(doors, pos));
                    continue;
                }

                var possibilitiesStr = str.Substring(minIndex + 1, minLength - 1);
                List<string> possibilities = new List<string>();

                int beforePipe = minIndex;
                for (var i = 0; i < pipes.Count; ++i)
                {
                    possibilities.Add(possibilitiesStr.Substring(beforePipe - minIndex, pipes[i] - beforePipe - 1));
                    beforePipe = pipes[0];
                }
                possibilities.Add(possibilitiesStr.Substring(beforePipe - minIndex));

                foreach (var possibility in possibilities)
                {
                    var nr = str.Substring(0, minIndex) + possibility + str.Substring(minIndex + minLength + 1);
                    queue.Push(nr);
                }
            }
            Console.WriteLine(result.Max());
        }


        // 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;
        }
    }
}