using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Runtime.Remoting.Messaging;
using System.Text;
using System.Text.RegularExpressions;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization
{
    public class SantaFeAntProblem : ISymbolicExpressionTreeProblem
    {
        private const string grammarString = @"
G(A):
A -> l | r | m | ?(A)(A) | ?(A)(A)A | lA | rA | mA
";
        // for tree-based GP in HL we need a different grammar for the same language
        // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
        private const string hlGrammarString = @"
    G(A):
    A -> l | r | m | P | I
    P -> AA | AAA
    I -> AA
    ";


        // original koza grammar
        // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
        // 
        // here we use a modified grammar which has only one syntax tree for each sentence


        private readonly IGrammar grammar;
        public string Name { get { return "SantaFeAnt"; } }

        public SantaFeAntProblem()
        {
            this.grammar = new Grammar(grammarString);
            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
        }

        public double BestKnownQuality(int maxLen)
        {
            // for now only an upper bound is returned, ideally all food pellets are discovered
            return 89;
        }

        public IGrammar Grammar
        {
            get { return grammar; }
        }

        public double Evaluate(string sentence)
        {
            var ant = new Ant();
            int p = 0;
            Run(ant, sentence, ref p);
            return ant.FoodEaten;
        }

        private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false)
        {
            while (!ant.Done())
            {
                if (p >= sentence.Length)
                {
                    if (stopAfterFirst) return;
                    p = 0; // restart
                }
                switch (sentence[p])
                {
                    case 'r':
                        {
                            ant.TurnRight();
                            p++;
                            break;
                        }
                    case 'l':
                        {
                            ant.TurnLeft();
                            p++;
                            break;
                        }
                    case 'm':
                        {
                            ant.Move();
                            p++;
                            break;
                        }
                    case '?':
                        {
                            p++; // skip p
                            if (ant.IsFoodAhead())
                            {
                                if (sentence[p] != '(') throw new ArgumentException();
                                p++;
                                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
                                if (ant.Done()) return;
                                if (sentence[p] != '(') throw new ArgumentException();
                                p++;
                                Skip(sentence, ref p);
                            }
                            else
                            {
                                if (sentence[p] != '(') throw new ArgumentException();
                                p++;
                                Skip(sentence, ref p);
                                if (sentence[p] != '(') throw new ArgumentException();
                                p++;
                                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
                            }
                            break;
                        }
                    case '.':
                        {
                            // nop
                            p++;
                            ant.Nop();
                            break;
                        }
                    case ')':
                        {
                            p++; // skip
                            return;     // caller must continue processing
                        }
                    default:
                        {
                            throw new ArgumentException();
                        }
                }
            }
        }

        private static void Skip(string sentence, ref int p)
        {
            int openCount = 1;
            while (openCount > 0)
            {
                if (sentence[p] == '(') openCount++;
                else if (sentence[p] == ')') openCount--;
                p++;
            }
        }

        public string CanonicalRepresentation(string phrase)
        {
            //phrase = phrase.Replace("A", ".");
            var sb = new StringBuilder(phrase);
            string canonicalPhrase = phrase;
            string oldPhrase;
            do
            {
                oldPhrase = canonicalPhrase;
                sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
                //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
                canonicalPhrase = sb.ToString();
            } while (canonicalPhrase != oldPhrase);
            return canonicalPhrase;
        }

        public IEnumerable<Feature> GetFeatures(string phrase)
        {
            phrase = CanonicalRepresentation(phrase);
            var isTerminal = grammar.IsTerminal(phrase);

            yield return new Feature(isTerminal + ToString(), 1.0);

            yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
            if (!isTerminal)
            {
                for (int i = 4; i < phrase.Length; i++)
                {
                    if (!grammar.IsTerminal(phrase[i]))
                    {
                        yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
                        break;
                    }
                }
            }

            yield return new Feature(phrase, 1.0);
        }

        public IGrammar TreeBasedGPGrammar { get; private set; }
        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
        {
            var sb = new StringBuilder();
            ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
            return sb.ToString();
        }
        private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb)
        {
            if (node.SubtreeCount == 0)
            {
                // terminal
                sb.Append(node.Symbol.Name);
            }
            else if (node.Symbol.Name == "I")
            {
                Debug.Assert(node.SubtreeCount == 2);
                sb.Append("?(");
                ConvertTreeToSentence(node.GetSubtree(0), sb);
                sb.Append(")(");
                ConvertTreeToSentence(node.GetSubtree(1), sb);
                sb.Append(")");
            }
            else
            {
                foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
            }
        }

        private string[] solutions;

        public void GenerateProblemSolutions(int maxLen)
        {
            solutions = new string[12];
            solutions[0] = "?(m)(ll?(m)(r))mr";
            solutions[1] = "?(m)(rr?(m)(l))ml";
            solutions[2] = "r?(m)(ll?(m)(r))m";
            solutions[3] = "l?(m)(rr?(m)(l))m";
            solutions[4] = "mr?(m)(ll?(m)(r))";
            solutions[5] = "ml?(m)(rr?(m)(l))";
            solutions[6] = "?(m)(ll?(m)(l))ml";
            solutions[7] = "?(m)(rr?(m)(r))mr";
            solutions[8] = "l?(m)(ll?(m)(l))m";
            solutions[9] = "r?(m)(rr?(m)(r))m";
            solutions[10] = "ml?(m)(ll?(m)(l))";
            solutions[11] = "mr?(m)(rr?(m)(r))";

            // A
            // rA
            // lA
            // mA
            // mlA
            // mrA
            // ?(A)(A)A
            // mr?(m)(ll?(A)(A))
            // ?(A)(A)?(A)(A)
        }

        private readonly List<string> validStarts3 = new List<string> { "A", "rA", "lA", "mA", "mlA", "mrA" };


        public bool IsParentOfProblemSolution(string sentence, int maxLen)
        {
            //INFO: only works with maxlen 17!!

            // eliminate wrong parents..
            if (sentence.Length < 17 && !sentence.Contains('A'))
            {
                return false;
            }
            if (sentence.Length > 3 && !sentence.Contains('?'))
            {
                return false;
            }
            if (sentence.Length <= 3)
            {
                return validStarts3.Contains(sentence);
            }
            if (sentence.Contains("m?"))
            {
                return false;
            }

            if (sentence.Length <= 17 && sentence.Contains('A'))
            {
                // check front part of solutions..
                // contains A, contains ?(x)(x), length > 3
                int index = sentence.IndexOf('?');
                if (index > 2) return false;

                int firstCloseBracket = sentence.IndexOf(')');
                // only one item in bracket
                if ((firstCloseBracket - index) != 3) return false;
                // must be m or A
                if (sentence[firstCloseBracket - 1] != 'm' && sentence[firstCloseBracket - 1] != 'A') return false;

                // check back and front part of solutions..
                int lastCloseBracket = sentence.LastIndexOf(')');
                // before first ? and after last ) either 1 left one right, or only two left (also A), or only two right (also A)
                int diff;
                if (index == 0)
                {
                    // must end with mr, ml, mA, A
                    diff = sentence.Length - 1 - lastCloseBracket;
                    if (diff == 0 || diff > 2) return false;
                    if (diff == 1 && sentence[sentence.Length - 1] != 'A') return false;
                    if (diff == 2 && (sentence[sentence.Length - 2] != 'm' || sentence[sentence.Length - 1] == 'm'))
                        return false;
                }
                else if (index == 1 && (sentence[0] == 'm' || (sentence[sentence.Length - 1] != 'm' && sentence[sentence.Length - 1] != 'A'))) return false;
                else if (index == 2)
                {
                    // must start with ml, mr, mA
                    // must end with )
                    if (sentence[sentence.Length - 1] != ')') return false;
                    if (sentence[0] != 'm' || sentence[1] == 'm') return false;
                }

                // check middle part of solutions ..(ll?(m)(l))..
                int index2 = sentence.IndexOf('?', index + 1);
                if (index2 == -1)
                {
                    // no second ? so far..
                    // allowed within second (..): A, lA, llA, rA, rrA
                    int lastOpenBracket = sentence.LastIndexOf('(', lastCloseBracket);
                    diff = lastCloseBracket - lastOpenBracket;
                    if (diff > 4) return false;
                    // last item must be A
                    if (sentence[lastCloseBracket - 1] != 'A') return false;
                    // first item must not be m
                    if (sentence[lastOpenBracket + 1] == 'm') return false;
                    // ll or rr
                    if (diff == 4 && sentence[lastOpenBracket + 1] != sentence[lastOpenBracket + 2]) return false;
                }
                else
                {
                    // second ? there..
                    // ?(x)(..?(x)(x))
                    int secondLastCloseBracket = sentence.LastIndexOf(')', lastCloseBracket - 1);
                    // has to end with '))'
                    if (lastCloseBracket - secondLastCloseBracket != 1) return false;
                    // only one item within second brackets
                    if (sentence[secondLastCloseBracket - 2] != '(') return false;
                    // the one item can be A, l or r
                    if (sentence[secondLastCloseBracket - 1] == 'm') return false;
                    // only one item in first brackets
                    if (sentence[index2 + 3] != ')') return false;
                    // only m or A allowed
                    if (sentence[index2 + 2] == 'l' || sentence[index2 + 2] == 'r') return false;
                    // ll or rr before second ? must already be there..
                    if (sentence[index2 - 1] != 'l' && sentence[index2 - 1] != 'r') return false;
                    if (sentence[index2 - 1] != sentence[index2 - 2]) return false;
                }
            }
            else
            {
                // has to be solution or false..
                return solutions.Any(solution => solution == sentence);
            }

            return true;
        }
    }

    public class Ant
    {
        private int maxSteps = 600;
        public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
        public enum HeadingEnum { North, East, South, West };
        public int FoodEaten { get; private set; }
        private readonly char[][] world = new char[32][];
        private int posX;
        private int posY;
        private int steps;
        private HeadingEnum heading;
        public int PosX { get { return posX; } }
        public int PosY { get { return posY; } }
        public HeadingEnum Heading { get { return heading; } }
        private bool recordTrail = false;
        private StringBuilder trailBuilder;

        public string Trail
        {
            get
            {
                if (!recordTrail) throw new NotSupportedException();
                else return trailBuilder.ToString() + heading; // add final heading as state
            }
        }

        public Ant(bool recordTrail = false)
        {
            world[00] = " ###                            ".ToCharArray();
            world[01] = "   #                            ".ToCharArray();
            world[02] = "   #                    .###..  ".ToCharArray();
            world[03] = "   #                    #    #  ".ToCharArray();
            world[04] = "   #                    #    #  ".ToCharArray();
            world[05] = "   ####.#####       .##..    .  ".ToCharArray();
            world[06] = "            #       .        #  ".ToCharArray();
            world[07] = "            #       #        .  ".ToCharArray();
            world[08] = "            #       #        .  ".ToCharArray();
            world[09] = "            #       #        #  ".ToCharArray();
            world[10] = "            .       #        .  ".ToCharArray();
            world[11] = "            #       .        .  ".ToCharArray();
            world[12] = "            #       .        #  ".ToCharArray();
            world[13] = "            #       #        .  ".ToCharArray();
            world[14] = "            #       #  ...###.  ".ToCharArray();
            world[15] = "            .   .#...  #        ".ToCharArray();
            world[16] = "            .   .      .        ".ToCharArray();
            world[17] = "            #   .      .        ".ToCharArray();
            world[18] = "            #   #      .#...    ".ToCharArray();
            world[19] = "            #   #          #    ".ToCharArray();
            world[20] = "            #   #          .    ".ToCharArray();
            world[21] = "            #   #          .    ".ToCharArray();
            world[22] = "            #   .      ...#.    ".ToCharArray();
            world[23] = "            #   .      #        ".ToCharArray();
            world[24] = " ..##..#####.   #               ".ToCharArray();
            world[25] = " #              #               ".ToCharArray();
            world[26] = " #              #               ".ToCharArray();
            world[27] = " #     .#######..               ".ToCharArray();
            world[28] = " #     #                        ".ToCharArray();
            world[29] = " .     #                        ".ToCharArray();
            world[30] = " .####..                        ".ToCharArray();
            world[31] = "                                ".ToCharArray();

            posX = 0;
            posY = 0;
            heading = HeadingEnum.East;
            FoodEaten = 0;
            steps = 0;

            this.recordTrail = recordTrail;
            if (this.recordTrail) trailBuilder = new StringBuilder();
        }

        public bool Done()
        {
            return steps > maxSteps;
        }

        public void TurnRight()
        {
            if (steps <= maxSteps)
            {
                steps++;
                if (heading == HeadingEnum.West) heading = HeadingEnum.North;
                else heading++;
            }
        }

        public void TurnLeft()
        {
            if (steps <= maxSteps)
            {
                steps++;
                if (heading == HeadingEnum.North) heading = HeadingEnum.West;
                else heading--;
            }
        }

        public void Move()
        {
            if (steps <= maxSteps)
            {
                steps++;
                MoveInternal(ref posX, ref posY);
                if (world[posY][posX] == '#')
                {
                    FoodEaten++;
                    world[posY][posX] = '.';
                }
                if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
            }
        }

        public void Nop()
        {
            // wait one time step
            if (steps <= maxSteps)
            {
                steps++;
            }
        }

        private void MoveInternal(ref int posX, ref int posY)
        {
            switch (heading)
            {
                case HeadingEnum.North:
                    posY = (posY + 31) % 32;
                    break;
                case HeadingEnum.East:
                    posX = (posX + 1) % 32;
                    break;
                case HeadingEnum.South:
                    posY = (posY + 1) % 32;
                    break;
                case HeadingEnum.West:
                    posX = (posX + 31) % 32;
                    break;
            }
        }

        public bool IsFoodAhead()
        {
            int nextPosX = posX;
            int nextPosY = posY;
            MoveInternal(ref nextPosX, ref nextPosY);

            if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check

            return world[nextPosY][nextPosX] == '#';
        }
    }
}