source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs @ 11832

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

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class HardPalindromeProblem : IProblem {
    // 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 readonly IGrammar grammar;
    public HardPalindromeProblem() {
      this.grammar = new Grammar(grammarString);
    }

    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();
    }
  }
}