Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs @ 17639

Last change on this file since 17639 was 10426, checked in by gkronber, 11 years ago

#2026 generate code for all solvers

File size: 7.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using System.Text;
6using HeuristicLab.Grammars;
7
8namespace CodeGenerator {
9  public class BruteForceCodeGen {
10
11    private string solverTemplate = @"
12
13namespace ?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}
Note: See TracBrowser for help on using the repository browser.