source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs @ 12893

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class HardPalindromeProblem : ISymbolicExpressionTreeProblem {
    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
    private const string grammarString = @"
G(S):
S -> T | TS
T -> a .. z
";
    private const string hlGrammarString = @"
G(S):
S -> a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z | SS
";

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

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

    public double BestKnownQuality(int maxLen) {
      // the whole sentence is a palindrome + each symbol occurs only once or twice
      // for odd total length the number of different characters can be larger than len/2 (aba)
      // the second part is limited to 26 different characters
      return maxLen + Math.Min(26, (maxLen + 1) / 2);
    }

    public IGrammar Grammar {
      get { return grammar; }
    }

    public double Evaluate(string sentence) {
      var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence);
      var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome);
      var chrCount = new int[256];
      foreach (var b in palindromeBytes) {
        chrCount[b]++;
      }
      return palindrome.Length + chrCount.Count(c => c > 0);
    }

    public string CanonicalRepresentation(string phrase) {
      return phrase;
    }

    public IEnumerable<Feature> GetFeatures(string phrase)
    {
      throw new NotImplementedException();
    }
    public bool IsOptimalPhrase(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();
    }
  }
}