Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestInstances.cs @ 11727

Last change on this file since 11727 was 11659, checked in by gkronber, 10 years ago

#2283 initial import of implementation of grammatical optimization problem instances
File size: 9.2 KB
Line 
1using System;
2using System.Diagnostics;
3using System.Linq;
4using Microsoft.VisualStudio.TestTools.UnitTesting;
5
6namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
7  [TestClass]
8  public class TestInstances {
9    [TestMethod]
10    public void TestGrammarFromString() {
11      {
12        var g = Grammar.FromString(@"
13
14G(S):
15  S -> aA | bB
16  A -> a | aA
17  B -> Bb | b
18");
19        Assert.AreEqual('S', g.SentenceSymbol);
20        Assert.AreEqual(2, g.TerminalSymbols.Count());
21        Assert.AreEqual(3, g.NonTerminalSymbols.Count());
22        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 'a', 'b' }.Contains(s)));
23        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'A', 'B' }.Contains(s)));
24
25        Assert.AreEqual(2, g.GetAlternatives('S').Count());
26        Assert.AreEqual(2, g.GetAlternatives('A').Count());
27        Assert.AreEqual(2, g.GetAlternatives('B').Count());
28
29        Assert.IsTrue(g.GetAlternatives('S').Contains("aA"));
30        Assert.IsTrue(g.GetAlternatives('S').Contains("bB"));
31        Assert.IsTrue(g.GetAlternatives('A').Contains("aA"));
32        Assert.IsTrue(g.GetAlternatives('A').Contains("a"));
33        Assert.IsTrue(g.GetAlternatives('B').Contains("Bb"));
34        Assert.IsTrue(g.GetAlternatives('B').Contains("b"));
35
36        Assert.AreEqual(2, g.MinPhraseLength("S"));
37        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
38        Assert.AreEqual(1, g.MinPhraseLength("A"));
39        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("A"));
40        Assert.AreEqual(1, g.MinPhraseLength("B"));
41        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("B"));
42      }
43
44      {
45        var g = Grammar.FromString(@"
46
47G(S):
48  S -> sS
49");
50        Assert.AreEqual('S', g.SentenceSymbol);
51        Assert.AreEqual(1, g.TerminalSymbols.Count());
52        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
53        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
54        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
55
56        Assert.AreEqual(1, g.GetAlternatives('S').Count());
57
58        Assert.IsTrue(g.GetAlternatives('S').Contains("sS"));
59
60        Assert.AreEqual(short.MaxValue, g.MinPhraseLength("S"));
61        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
62      }
63
64      {
65        var g = Grammar.FromString(@"
66
67G(S):
68S->sss|sS");
69        Assert.AreEqual('S', g.SentenceSymbol);
70        Assert.AreEqual(1, g.TerminalSymbols.Count());
71        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
72        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
73        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
74
75        Assert.AreEqual(2, g.GetAlternatives('S').Count());
76
77        Assert.IsTrue(g.GetAlternatives('S').Contains("sss"));
78        Assert.IsTrue(g.GetAlternatives('S').Contains("sS"));
79
80        Assert.AreEqual(3, g.MinPhraseLength("S"));
81        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
82        Assert.AreEqual(4, g.MinPhraseLength("sS"));
83        Assert.AreEqual(7, g.MinPhraseLength("sSS"));
84        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("sSS"));
85        Assert.AreEqual(3, g.MaxPhraseLength("sss"));
86        Assert.AreEqual(3, g.MinPhraseLength("sss"));
87      }
88
89      {
90        var g = Grammar.FromString(@"
91
92G(S):
93S->T|TS
94T-> a..z
95");
96        Assert.AreEqual('S', g.SentenceSymbol);
97        Assert.AreEqual(26, g.TerminalSymbols.Count());
98        Assert.AreEqual(2, g.NonTerminalSymbols.Count());
99        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'T' }.Contains(s)));
100
101        Assert.AreEqual(2, g.GetAlternatives('S').Count());
102
103        Assert.IsTrue(g.GetAlternatives('S').Contains("T"));
104        Assert.IsTrue(g.GetAlternatives('S').Contains("TS"));
105
106        Assert.AreEqual(1, g.MinPhraseLength("S"));
107        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength("S"));
108        Assert.AreEqual(1, g.MinPhraseLength("T"));
109        Assert.AreEqual(1, g.MaxPhraseLength("T"));
110      }
111
112    }
113
114    [TestMethod]
115    public void TestRoyalSymbolProblem() {
116      var p = new RoyalSymbolProblem();
117      Console.WriteLine(p.Grammar);
118
119      Assert.AreEqual(1, p.Evaluate("ab"));
120      Assert.AreEqual(0, p.Evaluate("bb"));
121      Assert.AreEqual(2, p.Evaluate("aa"));
122      Assert.AreEqual(3, p.Evaluate("aaa"));
123    }
124
125
126    [TestMethod]
127    public void TestRoyalPairProblem() {
128      var p = new RoyalPairProblem();
129      Console.WriteLine(p.Grammar);
130
131      Assert.AreEqual(1, p.Evaluate("ab"));
132      Assert.AreEqual(0, p.Evaluate("bb"));
133      Assert.AreEqual(0, p.Evaluate("aa"));
134      Assert.AreEqual(0, p.Evaluate("aaa"));
135      Assert.AreEqual(2, p.Evaluate("aba"));
136      Assert.AreEqual(2, p.Evaluate("abba"));
137      Assert.AreEqual(3, p.Evaluate("abab"));
138    }
139
140    [TestMethod]
141    public void TestSantaFeAntProblem() {
142      var p = new SantaFeAntProblem();
143      Console.WriteLine(p.Grammar);
144
145      // one possible optimal solution: if-food-ahead (move) ( left left if-food-ahead (move) (right)) move right
146      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
147    }
148    [TestMethod]
149    public void TestRoyalTreeProblem() {
150      var p = new RoyalTreeProblem();
151      Console.WriteLine(p.Grammar);
152
153    }
154    [TestMethod]
155    public void TestRoyalRoadProblem() {
156      var p = new RoyalRoadProblem();
157      Console.WriteLine(p.Grammar);
158
159    }
160    [TestMethod]
161    public void TestPalindromeProblem() {
162      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
163      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
164      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
165      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
166      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
167      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
168
169
170      var p = new PalindromeProblem();
171      Console.WriteLine(p.Grammar);
172
173      Assert.AreEqual(1, p.Evaluate("a"));
174      Assert.AreEqual(2, p.Evaluate("aa"));
175      Assert.AreEqual(3, p.Evaluate("aaa"));
176      Assert.AreEqual(3, p.Evaluate("aba"));
177      Assert.AreEqual(3, p.Evaluate("baba"));
178      Assert.AreEqual(3, p.Evaluate("abab"));
179      Assert.AreEqual(5, p.Evaluate("babab"));
180    }
181    [TestMethod]
182    public void TestHardPalindromeProblem() {
183      var p = new HardPalindromeProblem();
184      Console.WriteLine(p.Grammar);
185
186      Assert.AreEqual(1 + 1, p.Evaluate("a"));
187      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
188      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
189      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
190      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
191      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
192      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
193      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
194    }
195
196    [TestMethod]
197    public void TestEvenParityProblem() {
198      var p = new EvenParityProblem();
199      Console.WriteLine(p.Grammar);
200
201      // a | b | c | d | res
202      // 0 | 0 | 0 | 0 | 1
203      // 0 | 0 | 0 | 1 | 0
204      // 0 | 0 | 1 | 0 | 0
205      // 0 | 0 | 1 | 1 | 1
206      // 0 | 1 | 0 | 0 | 0
207      // 0 | 1 | 0 | 1 | 1
208      // 0 | 1 | 1 | 0 | 1
209      // 0 | 1 | 1 | 1 | 0
210      // 1 | 0 | 0 | 0 | 0
211      // 1 | 0 | 0 | 1 | 1
212      // 1 | 0 | 1 | 0 | 1
213      // 1 | 0 | 1 | 1 | 0
214      // 1 | 1 | 0 | 0 | 1
215      // 1 | 1 | 0 | 1 | 0
216      // 1 | 1 | 1 | 0 | 0
217      // 1 | 1 | 1 | 1 | 1
218
219
220      Assert.AreEqual(8, p.Evaluate("a"));
221      Assert.AreEqual(8, p.Evaluate("b"));
222      Assert.AreEqual(8, p.Evaluate("c"));
223      Assert.AreEqual(8, p.Evaluate("d"));
224
225      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
226      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
227      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
228      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
229      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
230    }
231
232    [TestMethod]
233    public void TestSymbolicRegressionPoly10Problem() {
234      var p = new SymbolicRegressionPoly10Problem();
235      Console.WriteLine(p.Grammar);
236
237      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
238      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
239      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
240      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
241      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
242      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
243      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
244      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
245      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
246      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
247
248      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
249      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
250      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
251
252      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
253    }
254  }
255}
Note: See TracBrowser for help on using the repository browser.