Line | |
---|
1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Linq;
|
---|
4 | using System.Text;
|
---|
5 |
|
---|
6 | namespace 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 = @"
|
---|
10 | G(S):
|
---|
11 | S -> T | TS
|
---|
12 | T -> 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.