1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Diagnostics;
|
---|
4 | using System.Linq;
|
---|
5 | using System.Text;
|
---|
6 | using HeuristicLab.Grammars;
|
---|
7 |
|
---|
8 | namespace CodeGenerator {
|
---|
9 | public class BruteForceCodeGen {
|
---|
10 |
|
---|
11 | private string solverTemplate = @"
|
---|
12 |
|
---|
13 | namespace ?PROBLEMNAME? {
|
---|
14 | public sealed class ?IDENT?BruteForceSolver {
|
---|
15 | private static int maxDepth = 20;
|
---|
16 |
|
---|
17 | private readonly ?IDENT?Problem problem;
|
---|
18 | private readonly Random random;
|
---|
19 |
|
---|
20 | private IEnumerable<Tree> GenerateTrees(int parentState, int depth) {
|
---|
21 | if(depth<=1) {
|
---|
22 | if(Grammar.subtreeCount[parentState] == 0)
|
---|
23 | foreach(var terminal in CreateTerminalNodes(parentState, problem))
|
---|
24 | yield return terminal;
|
---|
25 | } else if(Grammar.subtreeCount[parentState] == 1) {
|
---|
26 | for(int altIdx = 0; altIdx < Grammar.transition[parentState].Length; altIdx++) {
|
---|
27 | var targetState = Grammar.transition[parentState][altIdx];
|
---|
28 | foreach(var subtree in GenerateTrees(targetState, depth - 1)) {
|
---|
29 | var solution = new Tree(altIdx, new Tree[1] {subtree});
|
---|
30 | yield return solution;
|
---|
31 | }
|
---|
32 | }
|
---|
33 | } else if(Grammar.subtreeCount[parentState] > 1) {
|
---|
34 | var nums = Enumerable.Range(1, depth - 1);
|
---|
35 | var depthCombinations = CartesianProduct(Enumerable.Repeat(nums, Grammar.subtreeCount[parentState]))
|
---|
36 | .Where(comb => comb.Max() == depth - 1);
|
---|
37 | foreach(var depthCombination in depthCombinations) {
|
---|
38 | var trees = new IEnumerable<Tree>[Grammar.subtreeCount[parentState]];
|
---|
39 | var depthCombinationEnumerator = depthCombination.GetEnumerator();
|
---|
40 | depthCombinationEnumerator.MoveNext();
|
---|
41 | for(int subtreeIdx = 0; subtreeIdx < Grammar.subtreeCount[parentState]; subtreeIdx++) {
|
---|
42 | trees[subtreeIdx] = GenerateTrees(Grammar.transition[parentState][subtreeIdx], depthCombinationEnumerator.Current);
|
---|
43 | depthCombinationEnumerator.MoveNext();
|
---|
44 | }
|
---|
45 | foreach(var e in CartesianProduct(trees)) {
|
---|
46 | yield return new Tree(-1, e.ToArray()); // altIdx is ignored
|
---|
47 | }
|
---|
48 | }
|
---|
49 | }
|
---|
50 | }
|
---|
51 |
|
---|
52 | public IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sets) {
|
---|
53 | if(sets.Count() == 1) {
|
---|
54 | foreach(var e in sets.First()) {
|
---|
55 | yield return new T[] {e};
|
---|
56 | }
|
---|
57 | }
|
---|
58 | else {
|
---|
59 | var firstSet = sets.First();
|
---|
60 | foreach(var e in firstSet) {
|
---|
61 | foreach(var p in CartesianProduct(sets.Skip(1))) {
|
---|
62 | yield return new T[] {e}.Concat(p);
|
---|
63 | }
|
---|
64 | }
|
---|
65 | }
|
---|
66 | }
|
---|
67 |
|
---|
68 | private static IEnumerable<Tree> CreateTerminalNodes(int state, ?IDENT?Problem problem) {
|
---|
69 | switch(state) {
|
---|
70 | ?CREATETERMINALNODECODE?
|
---|
71 | default: { throw new ArgumentException(""Unknown state index"" + state); }
|
---|
72 | }
|
---|
73 | }
|
---|
74 |
|
---|
75 | private void ParseArguments(string[] args) {
|
---|
76 | var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)"");
|
---|
77 |
|
---|
78 | var helpRegex = new Regex(@""--help|/\?"");
|
---|
79 |
|
---|
80 | foreach(var arg in args) {
|
---|
81 | var maxDepthMatch = maxDepthRegex.Match(arg);
|
---|
82 | var helpMatch = helpRegex.Match(arg);
|
---|
83 | if(helpMatch.Success) {
|
---|
84 | PrintUsage(); Environment.Exit(0);
|
---|
85 | } else if(maxDepthMatch.Success) {
|
---|
86 | maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
|
---|
87 | if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]"");
|
---|
88 | } else {
|
---|
89 | Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0);
|
---|
90 | }
|
---|
91 | }
|
---|
92 | }
|
---|
93 | private void PrintUsage() {
|
---|
94 | Console.WriteLine(""Find a solution using brute force tree search."");
|
---|
95 | Console.WriteLine();
|
---|
96 | Console.WriteLine(""Parameters:"");
|
---|
97 | Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]"");
|
---|
98 | Console.WriteLine(""\t--help\tPrints this help text."");
|
---|
99 | }
|
---|
100 |
|
---|
101 |
|
---|
102 |
|
---|
103 | public ?IDENT?BruteForceSolver(?IDENT?Problem problem, string[] args) {
|
---|
104 | if(args.Length>1) ParseArguments(args);
|
---|
105 | this.problem = problem;
|
---|
106 | this.random = new Random();
|
---|
107 | }
|
---|
108 |
|
---|
109 | public void Start() {
|
---|
110 | var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
|
---|
111 | int n = 0;
|
---|
112 | long sumDepth = 0;
|
---|
113 | long sumSize = 0;
|
---|
114 | var sumF = 0.0;
|
---|
115 | var sw = new System.Diagnostics.Stopwatch();
|
---|
116 | sw.Start();
|
---|
117 | for(int depth = 1; depth < maxDepth; depth ++) {
|
---|
118 | Console.WriteLine(""Depth {0}:"", depth);
|
---|
119 | foreach(var t in GenerateTrees(0, depth)) {
|
---|
120 | var f = problem.Evaluate(t);
|
---|
121 | // t.PrintTree(0); Console.WriteLine();
|
---|
122 | var size = t.GetSize();
|
---|
123 | sumSize += size;
|
---|
124 | sumDepth += depth;
|
---|
125 | n++;
|
---|
126 | sumF += f;
|
---|
127 | if (problem.IsBetter(f, bestF)) {
|
---|
128 | bestF = f;
|
---|
129 | t.PrintTree(0); Console.WriteLine();
|
---|
130 | Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, size, depth);
|
---|
131 | }
|
---|
132 | if (n % 1000 == 0) {
|
---|
133 | sw.Stop();
|
---|
134 | Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"",
|
---|
135 | n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
|
---|
136 | sumSize = 0;
|
---|
137 | sumDepth = 0;
|
---|
138 | sumF = 0.0;
|
---|
139 | sw.Restart();
|
---|
140 | }
|
---|
141 | }
|
---|
142 | Console.WriteLine(""n={0}"",n);
|
---|
143 | }
|
---|
144 | }
|
---|
145 | }
|
---|
146 | }";
|
---|
147 |
|
---|
148 | public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
|
---|
149 | var solverSourceCode = new SourceBuilder();
|
---|
150 | solverSourceCode.Append(solverTemplate)
|
---|
151 | .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
|
---|
152 | .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
|
---|
153 | ;
|
---|
154 |
|
---|
155 | problemSourceCode.Append(solverSourceCode.ToString());
|
---|
156 | }
|
---|
157 |
|
---|
158 | private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable<TerminalNode> terminals) {
|
---|
159 | Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
|
---|
160 | var sb = new SourceBuilder();
|
---|
161 | var allSymbols = grammar.Symbols.ToList();
|
---|
162 | foreach (var s in grammar.Symbols) {
|
---|
163 | if (grammar.IsTerminal(s)) {
|
---|
164 | sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
|
---|
165 | var terminal = terminals.Single(t => t.Ident == s.Name);
|
---|
166 | if (terminal.Constraints.Any(c => c.Type == ConstraintNodeType.Range)) {
|
---|
167 | throw new NotSupportedException("Sorry the brute force solver does not support RANGE constraints");
|
---|
168 | }
|
---|
169 | sb.AppendFormat("{0}Tree t = null;", terminal.Ident).AppendLine();
|
---|
170 | // create nested loop to produce all combinations of values (only set constraints)
|
---|
171 | foreach (var constr in terminal.Constraints) {
|
---|
172 | sb.AppendFormat("foreach(var {1} in problem.GetAllowed{0}_{1}()) {{;", terminal.Ident, constr.Ident).BeginBlock();
|
---|
173 | }
|
---|
174 | sb.AppendFormat("t = new {0}Tree();", terminal.Ident).AppendLine();
|
---|
175 |
|
---|
176 | foreach (var constr in terminal.Constraints) {
|
---|
177 | sb.AppendFormat("t.{0} = {0};", constr.Ident);
|
---|
178 | }
|
---|
179 | sb.AppendLine("yield return t; ");
|
---|
180 |
|
---|
181 | foreach (var _ in terminal.Constraints) {
|
---|
182 | sb.AppendLine("}").EndBlock();
|
---|
183 | }
|
---|
184 |
|
---|
185 |
|
---|
186 | sb.AppendLine(" break; }");
|
---|
187 | }
|
---|
188 | }
|
---|
189 | return sb.ToString();
|
---|
190 | }
|
---|
191 | }
|
---|
192 | }
|
---|