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) | lA | rA | mA |?(A)(A)A
";
    // 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

    public IEnumerable<string> OptimalSentences {
      get {
        return new string[]
        {
          "?(m)(ll?(m)(r))mr",
          "?(m)(rr?(m)(l))ml",
          "r?(m)(ll?(m)(r))m",
          "l?(m)(rr?(m)(l))m",
          "mr?(m)(ll?(m)(r))",
          "ml?(m)(rr?(m)(l))",
          "?(m)(ll?(m)(l))ml",
          "?(m)(rr?(m)(r))mr",
          "l?(m)(ll?(m)(l))m",
          "r?(m)(rr?(m)(r))m",
          "ml?(m)(ll?(m)(l))",
          "mr?(m)(rr?(m)(r))",
        };
      }
    }

    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) {
      for (int idx = 0; idx < 15; idx++) {
        foreach (var t in Grammar.TerminalSymbols)
          yield return new Feature(t.ToString(), phrase.Length > idx ? phrase[idx] == t ? 1 : 0 : 0);
      }
      //var ant = new Ant(false);
      //int p = 0;
      //Run(ant, phrase.Replace('A', '.'), ref p, true);
      //yield return new Feature(ant.PosX + "x" + ant.PosY + "-" + ant.Heading, 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); }
      }
    }
    public bool IsOptimalPhrase(string phrase) {
      var firstNonTerminalIdx = new Sequence(phrase).FirstNonTerminalIndex;
      if (firstNonTerminalIdx == -1) firstNonTerminalIdx = phrase.Length;
      return OptimalSentences.Any(s => s.Substring(0, firstNonTerminalIdx) == phrase.Substring(0, firstNonTerminalIdx));
    }

  }

  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] == '#';
    }
  }
}