source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs @ 12815

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Authentication.ExtendedProtection.Configuration;
using System.Text;
using System.Text.RegularExpressions;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization
{
    // counts the number of times a symbol occurs in a sentence
    public class RoyalSymbolProblem : ISymbolicExpressionTreeProblem
    {
        private const string grammarString = @"
G(S):
S -> a | aS | b | bS
";

        private const string hlGrammarString = @"
G(S):
S -> a | b | SS
";

        // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s

        private readonly IGrammar grammar;
        public string Name { get { return "RoyalSymbol"; } }
        public RoyalSymbolProblem()
        {
            this.grammar = new Grammar(grammarString);
            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
            //TODO: allow configuration of the number of symbols
        }

        public double BestKnownQuality(int maxLen)
        {
            return maxLen;
        }

        public IGrammar Grammar
        {
            get { return grammar; }
        }

        private Regex regex = new Regex("a"); // count the number of "a"s
        public double Evaluate(string sentence)
        {
            // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
            Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
            return regex.Matches(sentence).Count;
        }
        public string CanonicalRepresentation(string phrase)
        {
            return phrase;
        }

        public IEnumerable<Feature> GetFeatures(string phrase)
        {
            throw new NotImplementedException();
        }

        public IGrammar TreeBasedGPGrammar { get; private set; }
        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
        {
            var sb = new StringBuilder();
            foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix())
            {
                if (s.Symbol.Name == "S") continue;
                sb.Append(s.Symbol.Name);
            }
            return sb.ToString();
        }

        private string solution = string.Empty;

        public void GenerateProblemSolutions(int maxLen)
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < maxLen; i++)
            {
                sb.Append('a');
            }
            solution = sb.ToString();
        }

        private readonly Regex isParentSolution = new Regex("a+S");
        public bool IsParentOfProblemSolution(string sentence, int maxLen)
        {
            if (sentence.Length < maxLen)
            {
                return isParentSolution.IsMatch(sentence);
            }
            else
            {
                return solution == sentence;
            }
        }
    }
}