Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11742 was 11742, checked in by gkronber, 9 years ago

#2283 refactoring

File size: 1.4 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5
6namespace HeuristicLab.Problems.GrammaticalOptimization {
7  public class HardPalindromeProblem : IProblem {
8    // length of the longest palindrome in the sentence + number of different symbols occurring in the palindrome
9    private const string grammarString = @"
10G(S):
11S -> T | TS
12T -> a .. z
13";
14
15    private readonly IGrammar grammar;
16    public HardPalindromeProblem() {
17      this.grammar = new Grammar(grammarString);
18    }
19
20    public double BestKnownQuality(int maxLen) {
21      // the whole sentence is a palindrome + each symbol occurs only once or twice
22      // for odd total length the number of different characters can be larger than len/2 (aba)
23      // the second part is limited to 26 different characters
24      return maxLen + Math.Min(26, (maxLen + 1) / 2);
25    }
26
27    public IGrammar Grammar {
28      get { return grammar; }
29    }
30
31    public double Evaluate(string sentence) {
32      var palindrome = PalindromeProblem.LongestPalindromicSubstring(sentence);
33      var palindromeBytes = ASCIIEncoding.ASCII.GetBytes(palindrome);
34      var chrCount = new int[256];
35      foreach (var b in palindromeBytes) {
36        chrCount[b]++;
37      }
38      return palindrome.Length + chrCount.Count(c => c > 0);
39    }
40
41    public string CanonicalRepresentation(string terminalPhrase) {
42      return terminalPhrase;
43    }
44  }
45}
Note: See TracBrowser for help on using the repository browser.